

A059459


a(1) = 2; 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.


6



2, 3, 7, 5, 13, 29, 31, 23, 19, 17, 8209, 8273, 10321, 2129, 2131, 83, 67, 71, 79, 1103, 1039, 1031, 1063, 1061, 1069, 263213, 263209, 263201, 265249, 265313, 264289, 280673, 280681, 280697, 280699, 280703, 280639, 280607, 280603, 280859, 280843, 281867, 265483, 265547, 265579, 265571, 266083, 266081, 266089, 266093, 266029
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

This is the lexicographically least (in positions of the flipped bits) such sequence.
It is not known if the sequence is infinite.
"The prime maze  consider the prime numbers in base 2, starting with the smallest prime (10)2. One can move to another prime number by either changing only one digit of the number, or adding a 1 to the front of the number. Can we reach 11 = (1011)2.? 3331? The Mersennes?" (See 'Prime Links + +'.) If we start at 11 and exclude terms 2 and 3 we get terms 11, 43, 41, and so on. This is the opposite parity sequence.
a(130), if it exists, is greater than 2^130000.  Charles R Greathouse IV, Jan 02 2014


LINKS

T. D. Noe and Charles R Greathouse IV, Table of n, a(n) for n = 1..129 (first 104 terms from Noe)
Chris K. Caldwell, Prime Links + +
W. Paulsen, The Prime Maze, Fib. Quart., 40 (2002), 272279.
Carlos Rivera, Problem 25. William Paulsen's Prime Numbers Maze


MAPLE

A059459search := 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 (not member(n, a))) then print([op(a), n]); RETURN(A059459search([op(a), n], upto_bit, upto_length)); fi; od; RETURN([op(a), `and no more`]); end;
E.g., call as: A059459search([2], 128, 200);


MATHEMATICA

maxBits = 32; ClearAll[a]; a[1] = 2; a[n_] := a[n] = If[ PrimeQ[ a[n1] ], bits = PadLeft[ IntegerDigits[ a[n1], 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, n1}], an], Return[an] ] ] ], 0]; Table[ a[n], {n, 1, 51}] (* From JeanFrançois Alcover, Jan 17 2012 *)


PROG

(PARI) step(n)=my(k, t); while(vecsearch(v, t=bitxor(n, 1<<k))  !ispseudoprime(t=bitxor(n, 1<<k)), k++); v=Set(concat(v, t)); t
u=v=[2]; u=concat(u, step(2)); for(i=3, 129, u=concat(u, step(u[#u])); print(#u" "u[#u])) \\ Charles R Greathouse IV, Jan 02 2014


CROSSREFS

Cf. A059458 (for this sequence written in binary), A059471. A strictly ascending analog: A059661, positions of the flipped bits: A059663.
Sequence in context: A064011 A050367 A192175 * A124440 A067363 A083188
Adjacent sequences: A059456 A059457 A059458 * A059460 A059461 A059462


KEYWORD

nonn,base,nice


AUTHOR

Gregory Allen, Feb 02 2001


EXTENSIONS

More terms and Maple program from Antti Karttunen, Feb 03 2001, who remarks that he was able to extend the sequence to the 104th term 151115727453207491916143 using the bitfliplimit 128.


STATUS

approved



