A052333 -id:A052333 - cp's OEIS frontend

A108129 Riesel problem: let k=2n-1; then a(n)=smallest m >= 1 such that k*2^m-1 is prime, or -1 if no such prime exists.

2, 1, 2, 1, 1, 2, 3, 1, 2, 1, 1, 4, 3, 1, 4, 1, 2, 2, 1, 3, 2, 7, 1, 4, 1, 1, 2, 1, 1, 12, 3, 2, 4, 5, 1, 2, 7, 1, 2, 1, 3, 2, 5, 1, 4, 1, 3, 2, 1, 1, 10, 3, 2, 10, 9, 2, 8, 1, 1, 12, 1, 2, 2, 25, 1, 2, 3, 1, 2, 1, 1, 2, 5, 1, 4, 5, 3, 2, 1, 1, 2, 3, 2, 4, 1, 2, 2, 1, 1, 8, 3, 4, 2, 1, 3, 226, 3, 1, 2, 1, 1, 2

Offset: 1

Jorge Coveiro, Jun 04 2005

nonn

It is conjectured that the integer k = 509203 is the smallest Riesel number, that is, the first n such that a(n) = -1 is 254602.
Browkin & Schinzel, having proved that 509203*2^k - 1 is composite for all k > 0, ask for the first such number with this property, noting that the question is implicit in Aigner 1961. - Charles R Greathouse IV, Jan 12 2018
Record values begin a(1) = 2, a(7) = 3, a(12) = 4, a(22) = 7, a(30) = 12, a(64) = 25, a(96) = 226, a(330) = 800516; the next record appears to be a(1147), unless a(1147) = -1. (The value for a(330), i.e., for k = 659, is from the Ballinger & Keller link, which also lists k = 2293, i.e., n = (k+1)/2 = (2293+1)/2 = 1147, as the smallest of 50 values of k < 509203 for which no prime of the form k*2^m-1 had yet been found.) - Jon E. Schoenfield, Jan 13 2018
Same as A046069 except for a(2) = 1. - Georg Fischer, Nov 03 2018

Hans Riesel, Några stora primtal, Elementa 39 (1956), pp. 258-260.

Jon E. Schoenfield, Table of n, a(n) for n = 1..329
A. Aigner, Folgen der Art ar^n + b, welche nur teilbare Zahlen liefern, Math. Nachr. 23 (1961), pp. 259-264. (Cited in Browkin & Schinzel)
R. Ballinger & W. Keller, The Riesel Problem: Definition and Status.
J. Browkin and A. Schinzel, On integers not of the form n-phi(n), Colloq. Math., 68 (1995), pp. 55-58.
Wilfrid Keller, List of primes k.2^n - 1 for k < 300 .
Hans Riesel, Some large prime numbers. Translated from the Swedish original (Några stora primtal, Elementa 39 (1956), pp. 258-260) by Lars Blomberg.

Main sequences for Riesel problem: A038699, A040081, A046069, A050412, A052333, A076337, A101036, A108129.

Cf. A040081, A046069.

Array[Function[k, SelectFirst[Range@300, PrimeQ[k 2^# - 1] &]][2 # - 1] &, 102] (* Michael De Vlieger, Jan 12 2018 *)
smk[n_]:=Module[{m=1,k=2n-1},While[!PrimeQ[k 2^m-1],m++];m]; Array[smk,120] (* Harvey P. Dale, Dec 26 2023 *)

forstep(k=1,301,2,n=1;while(!isprime(k*2^n-1),n++);print1(n,","))

Edited by Herman Jamke (hermanjamke(AT)fastmail.fm), Oct 25 2006

Name corrected by T. D. Noe, Feb 13 2011

A374965 a(n) = 2*a(n-1) + 1 for a(n-1) not prime, otherwise a(n) = prime(n) - 1; with a(1)=1.

Original entry on oeis.org

1, 3, 4, 9, 19, 12, 25, 51, 103, 28, 57, 115, 231, 463, 46, 93, 187, 375, 751, 70, 141, 283, 82, 165, 331, 100, 201, 403, 807, 1615, 3231, 6463, 12927, 25855, 51711, 103423, 156, 313, 166, 333, 667, 1335, 2671, 192, 385, 771, 1543, 222, 445, 891, 1783, 238, 477

Offset: 1

Bill McEachen, Jul 25 2024

Sequence is clearly infinite and not monotonic. Primes are sparse.
When is the next prime after n=10016 ? [Answer from N. J. A. Sloane, Aug 01 2024: The point of Bill's question is that a(10016) is the prime 838951, which is in fact the 289th prime in this sequence, as can be seen from A375028 and A373799. Thanks to the work of Lucas A. Brown (see A050412), we now know that the answer to Bill's question is that the 290th prime is the 102410-digit prime 104917*2^340181 - 1 = 5079...8783, which is a(350198). It was a very good question!]
It appears that the trajectories for different initial conditions a(1) converge to a few attractors. For all prime values and most nonprime values of a(1), the trajectories converge to the same attractor with prime 838951 at n=10016. For a(1) = 147, 295, 591, 1183, ... the trajectories converge to prime 85796863 at n=4390. For a(1) = 658, the trajectory reaches a prime with 240983 digits after 800516 steps. For a(1) = 509202, the trajectory never reaches a prime (see A050412, A052333). - Chai Wah Wu, Jul 29 2024

			a(1) = 1 is not a prime, so a(2) = 2*1+1 = 3. a(2) is a prime, so a(3) = prime(3)-1 = 4. a(4) = 2*4+1 = 9.

Harvey P. Dale, Table of n, a(n) for n = 1..1000
N. J. A. Sloane, A Nasty Surprise in a Sequence and Other OEIS Stories, Experimental Mathematics Seminar, Rutgers University, Oct 10 2024, Youtube video; Slides [Mentions this sequence]

The primes are listed in A375028 (see also A373798 and A373804).

Cf. A050412 and A052333.

a[n_] := a[n] = If[!PrimeQ[a[n-1]], 2*a[n-1] + 1, Prime[n]-1]; a[1] = 1; Array[a, 60] (* Amiram Eldar, Jul 25 2024 *)
nxt[{n_,a_}]:={n+1,If[!PrimeQ[a],2a+1,Prime[n+1]-1]}; NestList[nxt,{1,1},60][[;;,2]] (* Harvey P. Dale, Jul 28 2024 *)

from itertools import islice
from sympy import isprime, nextprime
def A374965_gen(): # generator of terms
    a, p = 1, 3
    while True:
        yield a
        a, p = p-1 if isprime(a) else (a<<1)+1, nextprime(p)
A374965_list = list(islice(A374965_gen(),30)) # Chai Wah Wu, Jul 29 2024

A051914 Values of n at which record values in A052334 are reached.

Original entry on oeis.org

1, 2, 3, 4, 7, 10, 12, 13, 22, 28, 42, 43, 73

Offset: 1

Donald S. McDonald

			43 leads to composites 87, 175 etc. and eventually to the prime 738197503.

Posting to sci.math in Dec 1999, New Question?

Cf. A050412, A052333, A052334, A052339, A052340.

Corrected and clarified by Christian G. Bower, Dec 19 1999

a(13)=73 confirmed by Warut Roonguthai

A052339 Values of n at which record values in A052340 are reached.

Original entry on oeis.org

1, 4, 12, 13, 42, 43, 73, 658

Offset: 1

Christian G. Bower, Dec 23 1999

A subsequence of A050412.

Cf. A050412, A051914, A052333, A052334, A052340.

659*2^n-1 is composite for n<2^17.

One more term supplied by David Broadhurst, Jan 02 2000

A052340 Record numbers of iterations reached in A050412.

Original entry on oeis.org

1, 2, 3, 4, 7, 24, 2552, 800516

Offset: 1

Christian G. Bower, Dec 23 1999

Cf. A050412, A051914, A052333, A052334, A052339.

a(n) = A050412(A052339(n)). - Amiram Eldar, Jul 25 2019

a(8) from the b-file at A050412 added by Amiram Eldar, Jul 25 2019

A375028 Primes in A374965 in order of their occurrence.

Original entry on oeis.org

3, 19, 103, 463, 751, 283, 331, 103423, 313, 2671, 1543, 1783, 3823, 68863, 20287, 733, 757, 407896063, 2083, 1093, 2251, 1153, 2371, 1213, 2467, 41023, 2707, 2803, 1453, 119909605576788675546376149602926591, 98238463, 25903, 3405823, 3590143, 3733, 14983, 7603, 7723, 15607, 65306623, 537343, 69151, 3859801644442622798122887215978426484283282692686288680974641672159756287

Offset: 1

Harvey P. Dale and N. J. A. Sloane_, Jul 28 2024

nonn

Sequences A050412 and A052333 suggest that it is possible that the present sequence has only finitely many terms. - N. J. A. Sloane, Jul 29 2024

Harvey P. Dale, Table of n, a(n) for n = 1..289 [This b-file ends with a(289) = 838951. Thanks to the work of _Lucas A. Brown_ (see A050412), we can now say that the next term a(290) is the 102410-digit prime 104917*2^340181 - 1. Of course this is too large to include in a b-file. - _N. J. A. Sloane_, Jul 31 2024]
N. J. A. Sloane, A Nasty Surprise in a Sequence and Other OEIS Stories, Experimental Mathematics Seminar, Rutgers University, Oct 10 2024, Youtube video; Slides [Mentions this sequence]

Cf. A374965; A050412, A052333.
A373799 gives the indices where the primes appear in A374965.
A373804 gives the primes sorted into increasing or5der.

nxt[{n_,a_}]:={n+1,If[!PrimeQ[a],2a+1,Prime[n+1]-1]}; Select[NestList[nxt, {1, 1}, 999][[;; , 2]], PrimeQ]

from itertools import islice
from sympy import isprime, nextprime
def A375028_gen(): # generator of terms
    a, p = 1, 3
    while True:
        if isprime(a):
            yield a
            a = p-1
        else:
            a = (a<<1)+1
        p = nextprime(p)
A375028_list = list(islice(A375028_gen(),30)) # Chai Wah Wu, Jul 29 2024

A051919 Start with n, apply k->2k+1 until reach new record prime; sequence gives record primes.

Original entry on oeis.org

3, 7, 11, 31, 79, 191, 223, 8191, 73727, 81919, 738197503, 51539607551, 3232601036663613174009984612954335460652964980182760163363015849805536730581466940964863

Offset: 0

N. J. A. Sloane, Dec 18 1999

			0->1->3, new record prime 3 in 2 steps; 1->3->7, new record prime 7 in 2 steps; 2->5->11, new record prime 11 in 2 steps; 3->7->15->31, new record prime 31 in 3 steps; ...

Cf. A051918, A052333.

f[0] = {start=0, k=3, steps=2}; f[n_] := f[n] = (k=start=f[n-1][[1]]+1; steps=0; While[!PrimeQ[k] || k <= f[n-1][[2]], k=2k+1; steps++]; {start, k, steps}); A051919 = Table[Print[f[n] // Last]; f[n], {n, 0, 12}][[All, 2]] (* Jean-François Alcover, Dec 10 2014 *)

More terms from Naohiro Nomoto, May 21 2001, who reports that the next term is > 10^130.

A051918 Start with n, apply k->2k+1 until reach new record prime; sequence gives number of steps needed.

Original entry on oeis.org

2, 2, 2, 3, 4, 5, 5, 10, 13, 13, 26, 32, 287, 18380, 21727, 23205, 24828, 35646, 48819, 51476

Offset: 0

N. J. A. Sloane, Dec 18 1999

a(20) > 60000. [From Donovan Johnson, May 23 2010]

			0->1->3, new record prime 3 in 2 steps; 1->3->7, new record prime 7 in 2 steps; 2->5->11, new record prime 11 in 2 steps; 3->7->15->31, new record prime 31 in 3 steps.
For the next few terms we have: 4->9->19->39->79; 5->11->23->47->95->191; 6->13->27->55->111->223; 7->15->31->63->127->255->511->1023->2047->4095->8191; etc.

Cf. A051919, A052333.

f[0] = {start=0, k=3, steps=2}; f[n_] := f[n] = (k=start=f[n-1][[1]]+1; steps=0; While[!PrimeQ[k] || k <= f[n-1][[2]], k=2k+1; steps++]; {start, k, steps}); A051918 = Table[Print[f[n] // Last]; f[n], {n, 0, 13}][[All, 3]] (* Jean-François Alcover, Dec 10 2014 *)

More terms from Naohiro Nomoto, May 21 2001

a(13)-a(19) from Donovan Johnson, May 23 2010

A354748 a(n) is the prime reached after A354747(n) steps when repeatedly applying the map x -> 3x+2 to 2n-1, or 0 if no prime is ever reached.

Original entry on oeis.org

5, 11, 17, 23, 29, 107, 41, 47, 53, 59, 197, 71, 233, 83, 89, 863, 101, 107, 113, 359, 2480057, 131, 137, 431, 149, 467, 4373, 167, 173, 179, 557, 191, 197, 5507, 1889, 647, 1997, 227, 233, 239, 2213, 251, 257, 263, 269, 827, 281, 863, 293, 2699, 2753, 311, 317

Offset: 1

Felix Fröhlich, Jun 06 2022

nonn

Is a(100943) = 0?

If not 0, a(100943) >= 10^10000. - Michael S. Branicky, Jun 07 2022

Cf. A052333, A354747.

a(n) = my(x=2*n-1); while(1, x=3*x+2; if(ispseudoprime(x), return(x)))

from sympy import isprime
def f(x): return 3*x + 2
def a(n):
    fn, c = f(2*n-1), 1
    while not isprime(fn): fn, c = f(fn), c+1
    return fn
print([a(n) for n in range(1, 54)]) # Michael S. Branicky, Jun 07 2022

A225721 Starting with x = n, the number of iterations of x := 2x - 1 until x is prime, or -1 if no prime exists.

Original entry on oeis.org

-1, 0, 0, 1, 0, 1, 0, 2, 1, 1, 0, 1, 0, 2, 1, 1, 0, 3, 0, 6, 1, 1, 0, 1, 2, 2, 1, 2, 0, 1, 0, 8, 3, 1, 2, 1, 0, 2, 5, 1, 0, 1, 0, 2, 1, 2, 0, 583, 1, 2, 1, 1, 0, 1, 1, 4, 1, 2, 0, 5, 0, 4, 7, 1, 2, 1, 0, 2, 1, 1, 0, 3, 0, 2, 1, 1, 4, 3, 0, 2, 3, 1, 0, 1, 2, 4

Offset: 1

Kevin L. Schwartz and Christian N. K. Anderson, May 13 2013

sign

This appears to be a shifted variant of A040076. - R. J. Mathar, May 28 2013

If n is prime, then a(n) = 0. If the sequence never reaches a prime number (for n = 1) or the prime number has more than 1000 digits, -1 is used instead. There are 22 such numbers for n < 10000.

			For a(20), the trajectory is 20->39->77->153->305->609->1217, a prime number. That required 6 steps, so a(20)=6.

Christian N. K. Anderson, Table of n, a(n) for n = 1..10000

Cf. A050921 (primes obtained).
Cf. A040081, A038699, A050412, A052333, A046069 (related to the Riesel problem).
Cf. A000668, A000043, A065341 (Mersenne primes), A000079 (powers of 2).
Cf. A007770 (happy numbers), A031177 (unhappy numbers).
Cf. A037274 (home primes), A037271 (steps), A037272, A037272.

y=as.bigz(rep(0,500)); ys=rep(0,500);
for(i in 1:500) { n=as.bigz(i); k=0;
    while(isprime(n)==0 & ndig(n)<1000 & k<5000) { k=k+1; n=2*n-1 }
    if(ndig(n)>=1000 | k>=5000) { ys[i]=-1; y[i]=-1;
    } else {ys[i]=k; y[i]=n; }
}

cp's OEIS Frontend

A108129 Riesel problem: let k=2n-1; then a(n)=smallest m >= 1 such that k*2^m-1 is prime, or -1 if no such prime exists.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A374965 a(n) = 2*a(n-1) + 1 for a(n-1) not prime, otherwise a(n) = prime(n) - 1; with a(1)=1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

A051914 Values of n at which record values in A052334 are reached.

Views

Author

Keywords

Examples

References

Crossrefs

Extensions

A052339 Values of n at which record values in A052340 are reached.

Views

Author

Keywords

Comments

Crossrefs

Extensions

A052340 Record numbers of iterations reached in A050412.

Views

Author

Keywords

Crossrefs

Formula

Extensions

A375028 Primes in A374965 in order of their occurrence.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

A051919 Start with n, apply k->2k+1 until reach new record prime; sequence gives record primes.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Extensions

A051918 Start with n, apply k->2k+1 until reach new record prime; sequence gives number of steps needed.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A354748 a(n) is the prime reached after A354747(n) steps when repeatedly applying the map x -> 3*x+2 to 2*n-1, or 0 if no prime is ever reached.

Views

Author

Keywords

Comments

A354748 a(n) is the prime reached after A354747(n) steps when repeatedly applying the map x -> 3x+2 to 2n-1, or 0 if no prime is ever reached.