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

Author

Robert G. Wilson v, Dec 22 1999

Keywords

• nonn
• nice
• easy

Comments

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)

Examples

			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
		

Links

• 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

Crossrefs

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

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

Programs

Maple

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

Mathematica

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

PARI

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

Formula

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

Extensions

More terms from Christian G. Bower, Dec 23 1999

Second definition corrected by Jaroslav Krizek, Feb 13 2011