A059459 -id:A059459 - cp's OEIS frontend

A059661 Like A059459, but each term must be greater than the previous ones.

2, 3, 7, 23, 31, 4127, 4159, 20543, 134238271, 134238527, 167792959, 1241534783, 3389018431, 72108495167, 72108503359, 72108765503, 2722258935367507707706996859526254457151, 2722258935367507707708149781030861304127, 13611294676837538538536137218847444070719

Offset: 1

Antti Karttunen, Feb 03 2001

N. J. A. Sloane, Maple implementations of XORnos and DIFF

Cf. A033875, A059459, A059662.

flip_primes_asc_search := proc(a,upto_bit,upto_length) local i,n,t; if(nops(a) >= upto_length) then RETURN(a); fi; t := a[nops(a)]; for i from 0 to upto_bit do n := XORnos(t,(2^i)); if(isprime(n) and (n > t)) then print([op(a), n]); RETURN(flip_primes_asc_search([op(a), n],upto_bit,upto_length)); fi; od; RETURN([op(a),`and no more`]); end;
flip_primes_asc_search([2],512,21);

uptobit = 512; uptolength = 17; Clear[f]; f[a_] := f[a] = Module[{n, i, t}, If[Length[a] >= uptolength, Return[a]]; t = a[[-1]]; For[i = 0, i <= uptobit, i++, n = BitXor[t, 2^i]; If[PrimeQ[n] && n > t, Return[f[Append[ a, n]]]]]]; A059661 = f[{2}] (* Jean-François Alcover, Mar 07 2016, adapted from Maple *)

from sympy import isprime
from itertools import islice
def agen():
    an, bit = 2, 1
    while True:
        yield an
        while an&bit or not isprime(an+bit): bit <<= 1
        an += bit; bit = 1
print(list(islice(agen(), 17))) # Michael S. Branicky, Oct 01 2022

a(n) = 2 + Sum_{k=1..n-1} 2^A059662(k). - Pontus von Brömssen, Jan 07 2023

A059663 Positions of the flipped bits in the sequence A059459.

Original entry on oeis.org

0, 2, 1, 3, 4, 1, 3, 2, 1, 13, 6, 11, 13, 1, 11, 4, 2, 3, 10, 6, 3, 5, 1, 3, 18, 2, 3, 11, 6, 10, 14, 3, 4, 1, 2, 6, 5, 2, 8, 4, 10, 14, 6, 5, 3, 9, 1, 3, 2, 6, 14, 2, 5, 10, 2, 18, 9, 13, 10, 1, 6, 7, 1, 9, 7, 6, 38, 23, 3, 27, 4, 8, 12, 1, 6, 2, 13, 14, 24, 12, 9, 3, 11, 17, 32, 37, 12, 33

Offset: 1

Antti Karttunen, Feb 03 2001

nonn

E.g. starting from A059459[1] = 2, flip (set) bit 0, gives A059459[2] = 3 (= 2+2^0), then flip (set) bit 2, gives A059459[3] = 7 (3+2^2), then flip (clear) bit 1, gives A059459[4] = 5 (7-2^1), etc.

Cf. A054429, A059459.

map(floor_log_2,map(abs,DIFF(A059459))); # For floor_log_2, see A054429

A359664 Prime Maze Room 11, opposite parity of A059459 starting from prime room 11.

Original entry on oeis.org

11, 43, 41, 2089, 2081, 2083, 2087, 10889035741470030830827987437816582768679, 10889035741470030830827987437816582768647

Offset: 1

Gregory Allen, Jan 10 2023

This is the opposite parity sequence of A059459 and lexicographically least of this sequence.
It is currently not known whether both of these sequences are infinite.
I was able to calculate 40 terms; a(40) is a 3261-digit prime.
a(1) = 11; a(n+1) is obtained by writing a(n) in binary and trying to complement just one bit, starting with the least significant bit, until a new prime is reached. (Terms 2 and 3 are excluded values from the main sequence.)
Conjecture: Room 2 and Room 11 are unlinked, i.e., two separate mazes or branches/trees, as they are of opposite parities.

Gregory Allen, Table of n, a(n) for n = 1..40
William Paulsen, Prime Maze, See Prime room 11.
Carlos Rivera, Problem 25. William Paulsen's Prime Numbers Maze, The Prime Puzzles and Problems Connection.

Cf. A059459.

maxBits = 2^14;
ClearAll[a];
a[1] = 3;
a[2] = 2;
a[3] = 11;
n = 4;
a[n_] :=
 a[n] = If[PrimeQ[a[n - 1]],
   bits = PadLeft[IntegerDigits[a[n - 1], 2], maxBits];
   For[i = 1, i <= maxBits, i++, bits2 = bits;
    bits2[[-i]] = 1 - bits[[-i]];
    If[i == maxBits, Print["maxBits reached"]; Break[],
     If[PrimeQ[an = FromDigits[bits2, 2]] &&
       FreeQ[Table[a[k], {k, 1, n - 1}], an], Return[an]]]],
   0]; Table[a[n], {n, 42}]

A059873 The lexicographically earliest sequence of binary encodings of solutions satisfying the equation given in A059871.

Original entry on oeis.org

1, 3, 5, 13, 21, 46, 78, 175, 303, 639, 1143, 2539, 4542, 9214, 17406, 36735, 69374, 139254, 270327, 556031, 1079294, 2162678, 4259819, 8642558, 17022974, 34078590, 67632893, 136249338, 270401534, 541064701, 1077935867, 2162163707

Offset: 1

Antti Karttunen, Feb 05 2001

nonn

The encoding is explained in A059872. Apply bin_prime_sum (see A059876) to this sequence and you get A000040, the prime numbers.

Sean A. Irvine, Table of n, a(n) for n = 1..50

Cf. A059459, A059874, A059875.

primesums_primes_search(16); primesums_primes_search := (upto_n) -> primesums_primes_search_aux([],1,upto_n); primesums_primes_search_aux := proc(a,n,upto_n) local i,p,t; if(n > upto_n) then RETURN(a); fi; p := ithprime(n); for i from (2^(n-1)) to ((2^n)-1) do t := bin_prime_sum(i); if(t = p) then print([op(a),i]); RETURN(primesums_primes_search_aux([op(a),i],n+1,upto_n)); fi; od; RETURN([op(a),`and no more found`]); end;

More terms from Naohiro Nomoto, Sep 12 2001

More terms from Larry Reeves (larryr(AT)acm.org), Nov 20 2003

A059458 A binary sequence: a(1) = 10 (2 in decimal) and a(n+1) is obtained by trying to complement just one bit of a(n), starting with the least significant bit, until a new prime is reached.

Original entry on oeis.org

10, 11, 111, 101, 1101, 11101, 11111, 10111, 10011, 10001, 10000000010001, 10000001010001, 10100001010001, 100001010001, 100001010011, 1010011, 1000011, 1000111, 1001111, 10001001111, 10000001111, 10000000111, 10000100111

Offset: 1

Gregory Allen, Feb 02 2001

This is the lexicographically least (in positions of the flipped bits) such sequence.

It is not known if the sequence is infinite.

The decimal sequence is given in A059459. A base-ten analog is in A059471.

Maple
```
See A059459 for Maple program.
```

More terms from David W. Wilson, Feb 05 2001. For many further terms (but written in base 10) see A059459.

A059662 Positions of the flipped bits (here they are always set from 0 to 1) in the sequence A059661.

Original entry on oeis.org

0, 2, 4, 3, 12, 5, 14, 27, 8, 25, 30, 31, 36, 13, 18, 131, 60, 133, 458, 247, 1040, 21, 618, 283, 300, 209, 6282, 19107, 11792, 3401, 30214, 1211, 3044, 15989, 30194

Offset: 1

Antti Karttunen, Feb 03 2001

Question: If A059661 could be extended infinitely, would all the natural numbers > 1 eventually appear here once?

a(31) > 27000. - Michael S. Branicky, Oct 02 2022

			Starting from A059661(1) = 2, flip (set) bit 0, gives A059661(2) = 3 (= 2+2^0), set bit 2, gives A059661(3) = 7 (3+2^2), set bit 4, gives A059661(4) = 23 (7+2^4), etc.

Cf. A054429, A059459, A059661, A139803.

map(floor_log_2,map(abs,DIFF(A059661))); # For floor_log_2, which essentially computes log[2](x) here, see A054429

from sympy import isprime
from itertools import islice
def agen():
    an, bit, p = 2, 1, 0
    while True:
        while an&bit or not isprime(an+bit): bit <<= 1; p += 1
        yield p
        an, bit, p = an+bit, 1, 0
print(list(islice(agen(), 26))) # Michael S. Branicky, Oct 01 2022

2^a(n) = A059661(n+1) - A059661(n). - Pontus von Brömssen, Jan 08 2023

a(21)-a(27) from Sean A. Irvine, Oct 01 2022
a(28)-a(30) from Michael S. Branicky, Oct 02 2022
a(31)-a(35) from Michael S. Branicky, May 29 2023

A065047 Primes which when written in base 2 and prepended with a 1 produce a prime.

Original entry on oeis.org

3, 5, 13, 29, 37, 43, 71, 83, 101, 113, 163, 193, 211, 223, 257, 311, 317, 347, 479, 509, 547, 577, 613, 643, 673, 709, 787, 823, 853, 877, 883, 907, 1031, 1061, 1181, 1223, 1259, 1283, 1409, 1451, 1481, 1493, 1499, 1511, 1523, 1559, 1583, 1721, 1871, 1973

Offset: 1

Robert G. Wilson v, Nov 05 2001

Primes p such that p and 2^k + p (where k is the smallest power of 2 such that 2^k > p) are primes. - Davide Rotondo, Nov 06 2024

			13 is in the sequence because 13_10 = 1101_2 and prepending a 1 gives 11101_2 = 29_10, which is a prime.

Harry J. Smith, Table of n, a(n) for n = 1..1000

Cf. A004755, A059459.

Do[p = Prime[n]; d = IntegerDigits[p, 2]; If[ PrimeQ[ FromDigits[ Prepend[d, 1], 2]], Print[p]], {n, 1, 350} ]
Select[Prime[Range[300]],PrimeQ[FromDigits[Join[{1},IntegerDigits[#,2]],2]]&] (* Harvey P. Dale, Apr 10 2023 *)

{ n=0; t=log(2); for (m=1, 10^9, p=prime(m); if (isprime(p + 2^(1 + log(p)\t)), write("b065047.txt", n++, " ", p); if (n==1000, return)) ) } \\ Harry J. Smith, Oct 05 2009

A292205 A sequence of primes beginning with 2, with each prime after that being the smallest prime not present differing by the least number of contiguous bits.

Original entry on oeis.org

2, 3, 5, 7, 11, 13, 29, 31, 23, 19, 17, 37, 53, 61, 59, 43, 41, 47, 79, 71, 67, 83, 107, 103, 101, 97, 113, 73, 89, 179, 163, 131, 139, 137, 233, 229, 197, 193, 199, 167, 151, 149, 157, 173, 109, 397, 269, 271, 263, 257

Offset: 1

Robert G. Wilson v, Sep 11 2017

Least prime not already present, formed from the previous prime by first flipping or inverting a single binary bit and if no such prime exists, then two contiguous bits, then three, etc., and if no such prime exists then by inserting increasing binary bits starting with "0", "1", "00", "01", "10", "11", etc. resulting in the least prime so created. Leading zeros are forbidden.

Inspired by A059459.

			a(1) =  2 =     10_2, by definition, there are no single binary digit primes and this is the least 2-bit prime;
a(2) =  3 =     11_2, the least significant bit was "flipped"; all 2-bit primes are now present;
a(3) =  5 =    101_2, since the next prime is formed by inserting a 0;
a(4) =  7 =    111_2, since it is obtained by "flipping" the twos bit; all 3-bit primes are now present;
a(5) = 11 =   1011_2, since it is the least prime formed by inserting a 0;
a(6) = 13 =   1101_2, since it is the least prime formed by flipping two contiguous bits; all 4-bit primes are now present;
a(7) = 29 =  11101_2, since it is the least prime formed by inserting a 1; no prime is generated by the insertion of a 0, i.e.; from 1101 (13_10) -> 10101 (21_10) or 11001 (25_10);
a(8) = 31 =  11111_2, since it is the least prime formed by flipping the twos bit;
a(9) = 23 =  10111_2, since it is the least prime formed by flipping one bits;
a(10) = 19 =  10011_2; flip 1 digit;
a(11) = 17 =  10001_2; flip 1 digit, all 5-bit primes are now present;
a(12) = 37 = 100101_2; insert the single digit 1, inserting the single digit 0 yields the composite 100001_2 = 33.
a(13) = 53 = 110101_2; flip a single digit; etc.

Cf. A000040, A036378, A059459, A292203, A292204.

A294205 a(1) = 2; for n > 1, a(n) is the least prime p not already in the sequence such that the Hamming distance between p and a(n-1) is 1.

Original entry on oeis.org

2, 3, 7, 5, 13, 29, 31, 23, 19, 17, 8209, 8273, 10321, 2129, 2113, 3137, 3169, 19553, 19489, 19457, 18433, 83969, 84481, 84737, 2181889, 2181953, 2706241, 2704193, 2687809, 590657, 590593, 590609, 590641, 590129, 524593, 274878431537, 274878431521, 274879480097, 1573153, 1573217, 1704289, 5898593

Offset: 1

Robert G. Wilson v, Oct 24 2017

Conjecture: this sequence is infinite.
First differs from A059459 at a(15).
By definition of a Hamming distance of 1, the first forward absolute difference between a(n-1) and a(n) is a power of two (A000079).
The exponent of two in those differences is 0, 2, 1, 3, 4, 1, 3, 2, 1, 13, 6, 11, 13, 4, 10, 5, 14, 6, 5, 10, 16, 9, 8, 21, 6, 19, 11, 14, 21, 6, 4, 5, 9, 16, 38, 4, 20, 38, 6, 17, 22, 20, 14, 22, 10, 14, 2, 10, 46, 1, 28, 3, 56, 75, 3, 8, 16, 27, 75, 3, 20, 25, 606, 807, 2052, 2177, 886, 759, 796, 5357, 966, 399, etc.
Note that it is not true that for every prime m there is some k such that m+2^k is prime: see comments and links at A094076. Thus it is quite conceivable that the sequence is finite. - Robert Israel, Nov 15 2017

Robert G. Wilson v, Table of n, a(n) for n = 1..70

Cf. A000040, A000079, A059459, A094076.

A[1]:= 2: S:= {2}:
L:= [1]:
for n from 2 to 50 do
  found:= false;
  for i from 1 to nops(L) while not found do
    cand:= A[n-1] - 2^L[-i];
    if not member(cand,S) and isprime(cand) then
      found:= true; L:= subsop(-i=NULL,L) fi;
  od;
  for k from 0 while not found do
    if not member(k,L) then
      cand:= A[n-1] + 2^k;
      if not member(cand,S) and isprime(cand) then
        found:= true; L:= sort([op(L),k]);
      fi
    fi
  od;
  A[n]:= cand;
  S:= S union {cand};
od:
seq(A[i],i=1..50); # Robert Israel, Nov 15 2017

hammingDistance[a_, b_] := Count[ IntegerDigits[ BitXor[a, b], 2], 1]; f[s_List] := Block[{p = s[[-1]], q = 3}, While[MemberQ[s, q] || hammingDistance[p, q] > 1, q = NextPrime@q]; Append[s, q]]; s = {2}; Nest[f, s, 26] (* or *)
f[s_List] := Block[{k = -Floor[RealExponent[s[[-1]], 2]], p = s[[-1]]}, While[q = If[k < 0, p - 2^-k, p + 2^k]; MemberQ[s, q] || !PrimeQ[q] || hammingDistance[p, q] > 1, k++]; Append[s, q]]; s = {2}; Nest[f, s, 67]

A343765 Lexicographically earliest sequence of distinct nonprime numbers such that for any n > 0, a(n+1) = a(n) XOR 2^k for some k >= 0 as small as possible (where XOR denotes the bitwise XOR operator).

Original entry on oeis.org

1, 9, 8, 10, 14, 15, 143, 142, 140, 141, 133, 132, 134, 135, 391, 390, 388, 384, 385, 387, 386, 394, 395, 393, 392, 396, 398, 399, 415, 414, 412, 413, 405, 404, 406, 407, 403, 402, 400, 408, 410, 411, 475, 474, 472, 473, 477, 476, 478, 470, 471, 469, 468, 464

Offset: 1

Rémy Sigrist, Apr 28 2021

This sequence is similar to A003188 and to A059459; here we deal with nonprime numbers, there with integers and prime numbers, respectively.

Will the value 4 ever appear?

			The first terms, alongside their binary expansion, are:
  n   a(n)  bin(a(n))
  --  ----  ---------
   1     1          1
   2     9       1001
   3     8       1000
   4    10       1010
   5    14       1110
   6    15       1111
   7   143   10001111
   8   142   10001110
   9   140   10001100
  10   141   10001101
  11   133   10000101
  12   132   10000100
  13   134   10000110
  14   135   10000111
  15   391  110000111
  16   390  110000110
  17   388  110000100
  18   384  110000000
  19   385  110000001
  20   387  110000011

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Index entries for sequences related to binary expansion of n

Cf. A003188, A018252, A059459.

s=2^0; v=1; for (n=1, 54, print1 (v", "); s+=2^v; for (x=0, oo, if (!bittest(s, w=bitxor(v, 2^x)) && !isprime(w), v=w; break)))

cp's OEIS Frontend

A059661 Like A059459, but each term must be greater than the previous ones.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A059663 Positions of the flipped bits in the sequence A059459.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

A359664 Prime Maze Room 11, opposite parity of A059459 starting from prime room 11.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A059873 The lexicographically earliest sequence of binary encodings of solutions satisfying the equation given in A059871.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Extensions

A059458 A binary sequence: a(1) = 10 (2 in decimal) and a(n+1) is obtained by trying to complement just one bit of a(n), starting with the least significant bit, until a new prime is reached.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Extensions

A059662 Positions of the flipped bits (here they are always set from 0 to 1) in the sequence A059661.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Python

Formula

Extensions

A065047 Primes which when written in base 2 and prepended with a 1 produce a prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A292205 A sequence of primes beginning with 2, with each prime after that being the smallest prime not present differing by the least number of contiguous bits.

Views

Author

Keywords

Comments

Examples

Crossrefs

A294205 a(1) = 2; for n > 1, a(n) is the least prime p not already in the sequence such that the Hamming distance between p and a(n-1) is 1.

Views