A052339 -id:A052339 - cp's OEIS frontend

A050412 Riesel problem: start with n; repeatedly double and add 1 until reaching a prime. Sequence gives number of steps to reach a prime or 0 if no prime is ever reached.

1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 3, 4, 1, 1, 2, 2, 1, 2, 1, 1, 4, 1, 3, 2, 1, 3, 4, 1, 1, 2, 2, 1, 2, 1, 1, 2, 3, 1, 2, 1, 7, 24, 1, 3, 4, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 3, 12, 2, 3, 4, 2, 1, 4, 1, 5, 2, 1, 1, 2, 4, 7, 2552, 1, 1, 2, 2, 1, 4, 3, 1, 2, 1, 5, 6, 1, 23, 4, 1, 1, 2, 3, 3, 2, 1, 1, 4, 1, 1

Offset: 1

Robert G. Wilson v, Dec 22 1999

a(n) is the smallest m >= 1 such that (n+1)*2^m - 1 is prime (or 0 if no such prime exists).
It is conjectured that n = 509203 is the smallest Riesel number, i.e., n*2^k - 1 is composite for every k>0. - Robert G. Wilson v, Mar 01 2015. [This would imply that a(509203) is the first zero term in this sequence. - N. J. A. Sloane, Jul 31 2024]
Comment from N. J. A. Sloane, Aug 01 2024 (Start)
Both the Ballinger-Keller and Prime Wiki links assert that 104917*2^340181-1 is prime, but leave open the possibility that there is an m < 340181 which makes 104917*2^m - 1 a prime.
This question was finally settled by Lucas A. Brown on Jul 31 2024, who showed that m = 340181 is the smallest value that gives a prime. This implies that a(104917) = 340181.
Brown used a Python program (see below), with BPSW for the primality testing and gmpy2 to handle the arithmetic. The program was started on Jul 30 2024 and finished on Jul 31 2024.
He reports that it took about 15 hours in wall-clock time, and used 24 threads running in parallel.  (End)

			For n=4; the smallest m>=1 such that (4+1)*2^m-1 is prime is m=2: 5*2^2-1=19 (prime). - _Jaroslav Krizek_, Feb 13 2011

Robert G. Wilson v, Table of n, a(n) for n = 1..2291 (first 657 terms from T. D. Noe)
Ray Ballinger and Wilfrid Keller, The Riesel Problem: Definition and Status, Proth Search Page.
Hans Riesel, Some large prime numbers. Translated from the Swedish original (Några stora primtal, Elementa 39 (1956), pp. 258-260) by Lars Blomberg.
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]
Prime Wiki, Riesel primes of the form 104917•2^n-1

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

Cf. A051914, A052333 (primes reached), A052334, A052339, A052340, A050413, A078680, A101036.

A050412 := proc(n)
    local twox1,k ;
    twox1 := 2*n+1 ;
    k := 1;
    while not isprime(twox1) do
        twox1 := 2*twox1+1 ;
        k := k+1 ;
    end do:
    return k;
end proc: # R. J. Mathar, Jul 23 2015

a[n_] := Block[{s=n, c=1}, While[ ! PrimeQ[2*s+1], s = 2*s+1; c++]; c]; Table[ a[n], {n, 1, 99} ] (* Jean-François Alcover, Feb 06 2012, after Pari *)
a[n_] := Block[{k = 1}, While[ !PrimeQ[2^k (n + 1) - 1], k++];k]; Array[a, 100] (* Robert G. Wilson v, Feb 14 2015 *) (* Corrected by Paolo Xausa, Jul 30 2024 *)

a(n)=if(n<0,0,s=n; c=1; while(isprime(2*s+1)==0,s=2*s+1; c++); c)
(Python, designed specifically for n = 104917)
#! /usr/bin/env python3
from labmath import primegen, isprime, mpz, count
from multiprocessing import Pool
primes = list(primegen(1000000))
def test(n):
    for p in primes:
        if (104917 * pow(2, n, p)) % p == 1:
            return (n, False)
    return (n, isprime(104917 * mpz(2)**n - 1, tb=[]))
with Pool(24) as P:
    for (n, result) in P.imap(test, count()):
        print('\b'*80, n, end='', flush=True)
        if result:
            break # Lucas A. Brown, Aug 01 2024

If a(n) = k with k>1, then a(2n+1) = k-1. - Robert G. Wilson v, Mar 01 2015

If a(n) = 0, then a(2n+1) is also 0. Conjecture: If a(n) = 1, then a(2n+1) is not 0. - Jeppe Stig Nielsen, Feb 12 2023

More terms from Christian G. Bower, Dec 23 1999

Second definition corrected by Jaroslav Krizek, Feb 13 2011

A052333 Riesel problem: start with n; repeatedly double and add 1 until reach a prime. Sequence gives a(n) = prime reached, or 0 if no prime is ever reached.

Original entry on oeis.org

3, 5, 7, 19, 11, 13, 31, 17, 19, 43, 23, 103, 223, 29, 31, 67, 71, 37, 79, 41, 43, 367, 47, 199, 103, 53, 223, 463, 59, 61, 127, 131, 67, 139, 71, 73, 151, 311, 79, 163, 83, 5503, 738197503, 89, 367, 751, 191, 97, 199, 101, 103, 211, 107, 109, 223, 113, 463

Offset: 1

Christian G. Bower, Dec 19 1999

Equivalently, a(n) = smallest prime of form (n+1)*2^k-1 for k >= 1, or 0 if no such prime exists.
a(509202) = 0 (i.e. never reaches a prime) - Chris Nash (chris_nash(AT)hotmail.com). (Of course this is related to the entry 509203 of A076337.)
a(73) is a 771-digit prime reached after 2552 iterations - Warut Roonguthai. This was proved to be a prime by Paul Jobling (Paul.Jobling(AT)WhiteCross.com) using PrimeForm and by Ignacio Larrosa Cañestro using Titanix (http://www.znz.freesurf.fr/pages/titanix.html). [Oct 30 2000]

			a(4)=19 because 4 -> 9 (composite) -> 19 (prime).

N. J. A. Sloane, Table of n, a(n) for n = 1..657. Note that A050412(658) = 800516, so a(658) has 240983 digits, which is too large for a b-file.
Ray Ballinger and Wilfrid Keller, The Riesel Problem: Definition and Status
Hans Riesel, Some large prime numbers. Translated from the Swedish original (Några stora primtal, Elementa 39 (1956), pp. 258-260) by Lars Blomberg.
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]

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

Cf. A051914, A052334, A052339, A052340, A040081.

Table[NestWhile[2#+1&,2n+1,!PrimeQ[#]&,1,1000],{n,60}] (* Harvey P. Dale, May 08 2011 *)

a(n)=while(!isprime(n=2*n+1),);n \\ oo loop when a(n) = 0. - Charles R Greathouse IV, May 08 2011

A052334 Record primes reached in A052333.

Original entry on oeis.org

3, 5, 7, 19, 31, 43, 103, 223, 367, 463, 5503, 738197503

Offset: 1

Christian G. Bower, Dec 19 1999

Start with n=1, take 2n+1, if composite take 2n+1 again, keep going until you reach a prime. Repeat for n=2, 3... If prime is a record, add to sequence. If never reach a prime, skip that value of n.

a(13) is a 771-digit prime reached after 2552 iterations starting from 73. - Warut Roonguthai. This was proved to be a prime by Paul Jobling (Paul.Jobling(AT)WhiteCross.com) using PrimeForm and by Ignacio Larrosa Cañestro using Titanix (http://www.znz.freesurf.fr/pages/titanix.html). [Oct 30 2000]

Amiram Eldar, Table of n, a(n) for n = 1..13

Cf. A050412, A051914, A052333, A052339, A052340.

record = 2; Reap[For[n = 1, n <= 100, n++, k = n; While[ !PrimeQ[k = 2*k + 1]]; If[k > record, Print[k]; Sow[k]; record = k]]][[2, 1]] (* Jean-François Alcover, Jul 19 2013 *)

a(n) = A052333(A051914(n)). - Amiram Eldar, Jul 25 2019

cp's OEIS Frontend

A050412 Riesel problem: start with n; repeatedly double and add 1 until reaching a prime. Sequence gives number of steps to reach a prime or 0 if no prime is ever reached.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A052333 Riesel problem: start with n; repeatedly double and add 1 until reach a prime. Sequence gives a(n) = prime reached, or 0 if no prime is ever reached.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A052334 Record primes reached in A052333.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Examples

References

Crossrefs

Extensions

A052340 Record numbers of iterations reached in A050412.

Views

Author

Keywords

Crossrefs

Formula

Extensions