A059458 -id:A059458 - cp's OEIS frontend

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.

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

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 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
a(130) is equal to a(129) + 2^400092. - Giovanni Resta, Jul 19 2017

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

Cf. A059458 (for this sequence written in binary), A059471. A strictly ascending analog: A059661, positions of the flipped bits: A059663.

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);

maxBits = 2^11; ClearAll[a]; a[1] = 2; 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, 129}] (* Jean-François Alcover, Jan 17 2012 *)
f[lst_List] := Block[{db2 = IntegerDigits[lst[[-1]], 2]}, exp = Length@ db2; While[pp = db2; pp[[exp]] = If[OddQ@db2[[exp]], 0, 1]; pp = FromDigits[pp, 2]; !PrimeQ[pp] || MemberQ[lst, pp], exp--; If[exp == 0, exp++; PrependTo[db2, 0]]]; Append[lst, pp]]; Nest[f, {2}, 128] (* Robert G. Wilson v, Jul 17 2017 *)

step(n)=my(k,t); while(vecsearch(v, t=bitxor(n,1<Charles R Greathouse IV, Jan 02 2014

from sympy import isprime
from itertools import islice
def agen():
    seen, cand = set(), 2
    while True:
        an = cand; bit = 1; seen.add(an); yield an
        while cand in seen or not isprime(cand):
            cand = an-bit if an&bit else an+bit
            bit <<= 1
print(list(islice(agen(), 51))) # Michael S. Branicky, Oct 01 2022

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 bit-flip-limit 128.

A059471 a(1) = 2; a(n+1) is obtained by trying to change just one digit of a(n), starting with the least significant digit, until a new prime is reached.

Original entry on oeis.org

2, 3, 5, 7, 17, 11, 13, 19, 29, 23, 43, 41, 47, 37, 31, 61, 67, 97, 197, 191, 193, 199, 109, 101, 103, 107, 127, 137, 131, 139, 149, 179, 173, 113, 163, 167, 157, 151, 181, 281, 283, 223, 227, 229, 239, 233, 263, 269, 569, 563, 503, 509, 599, 593, 523, 521, 541, 547, 557

Offset: 1

N. J. A. Sloane, Feb 03 2001

Take the lexicographically earliest sequence, subject to the rules that the leftmost digit must be replaced by a nonzero digit, the other digits by any digit.
It is not known if the sequence is infinite.
The sequence is finite with last term a(17115) = 3377464733, see links for illustration. - Reinhard Zumkeller, Apr 20 2011
Zumkeller's demonstration of finiteness is false if some other leading 0 rather than the immediate leading 0 can be replaced, otherwise a(17116) = 203377464733 (cf. also A059498). - Sean A. Irvine, Sep 25 2022

Reinhard Zumkeller, Table of n, a(n) for n = 1..17115 (full sequence)
Reinhard Zumkeller, Why 3377464733 is the last term
Reinhard Zumkeller, A Haskell program for A059471

Decimal analog of A059458. See also A059472 for primes that are missed.

Cf. A059496, A059497, A059498.

More terms from David W. Wilson, Feb 05 2001

Keyword fini added by Reinhard Zumkeller, Apr 20 2011

A059496 a(1) = 2; a(n+1) is obtained by and trying to change just one digit of a(n), starting with the least significant digit, until a new prime is reached. Take the lexicographically earliest sequence. Digits may be replaced by any nonzero digit.

Original entry on oeis.org

2, 3, 5, 7, 17, 11, 13, 19, 29, 23, 43, 41, 47, 37, 31, 61, 67, 97, 197, 191, 193, 199, 139, 131, 137, 127, 157, 151, 181, 281, 283, 223, 227, 229, 239, 233, 263, 269, 569, 563, 523, 521, 541, 547, 557, 577, 571, 271, 277, 257, 251, 211, 241, 641, 643, 647, 617, 613, 619

Offset: 1

David W. Wilson, Feb 05 2001

The sequence is finite with last term a(114) = 149, see link and b-file. - Reinhard Zumkeller, Jan 06 2014

Reinhard Zumkeller, Table of n, a(n) for n = 1..114
Reinhard Zumkeller, Proof of finiteness

Another decimal analog of A059458. See A059497 for primes that are missed. Cf. A059471, A059498.

Cf. A010051.

a059496 n = a059496_list !! (n-1)
a059496_list = 2 : f [2] [2] where
   f qs xs = g candidates where
     g [] = []
     g (ys:yss) | a010051 q == 0 || q `elem` qs = g yss
                | otherwise = q : f (q:qs) ys
                where q = foldr (\d r -> 10 * r + d) 0 ys
     candidates = [us ++ [z] ++ vs | i <- [0 .. length xs - 1],
                         let (us, (_:vs)) = splitAt i xs, z <- [1..9]] ++
                  [xs ++ [z] | z <- [1..9]]
-- Reinhard Zumkeller, Jan 06 2014

A059498 a(1) = 2; a(n+1) is obtained by trying to change just one digit of a(n), starting with the least significant digit, until a new prime is reached. Take the lexicographically earliest sequence. Digits may be replaced by any larger digit.

Original entry on oeis.org

2, 3, 5, 7, 17, 19, 29, 59, 79, 89, 389, 2389, 2399, 2699, 2999, 4999, 8999, 98999, 298999, 598999, 599999, 799999, 1799999, 4799999, 4999999, 904999999, 974999999, 60974999999, 68974999999, 68975999999, 3000068975999999, 3000568975999999

Offset: 1

David W. Wilson, Feb 05 2001

It is not known if the sequence is infinite.

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

Another decimal analog of A059458. Cf. A059471, A059497.

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Extensions

A059471 a(1) = 2; a(n+1) is obtained by trying to change just one digit of a(n), starting with the least significant digit, until a new prime is reached.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A059496 a(1) = 2; a(n+1) is obtained by and trying to change just one digit of a(n), starting with the least significant digit, until a new prime is reached. Take the lexicographically earliest sequence. Digits may be replaced by any nonzero digit.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

A059498 a(1) = 2; a(n+1) is obtained by trying to change just one digit of a(n), starting with the least significant digit, until a new prime is reached. Take the lexicographically earliest sequence. Digits may be replaced by any larger digit.

Views

Author

Keywords

Comments

Links

Crossrefs