login
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.
10

%I #43 Sep 21 2024 12:42:16

%S 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,

%T 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,

%U 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

%N 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.

%C 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.

%C 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

%C 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

%C Same as A046069 except for a(2) = 1. - _Georg Fischer_, Nov 03 2018

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

%H Jon E. Schoenfield, <a href="/A108129/b108129.txt">Table of n, a(n) for n = 1..329</a>

%H A. Aigner, <a href="https://doi.org/10.1002/mana.1961.3210230405">Folgen der Art ar^n + b, welche nur teilbare Zahlen liefern</a>, Math. Nachr. 23 (1961), pp. 259-264. (Cited in Browkin & Schinzel)

%H R. Ballinger & W. Keller, <a href="http://www.prothsearch.com/rieselprob.html">The Riesel Problem: Definition and Status</a>.

%H J. Browkin and A. Schinzel, <a href="http://matwbn.icm.edu.pl/ksiazki/cm/cm68/cm6817.pdf">On integers not of the form n-phi(n)</a>, Colloq. Math., 68 (1995), pp. 55-58.

%H Wilfrid Keller, <a href="http://www.prothsearch.com/riesel2.html">List of primes k.2^n - 1 for k < 300 </a>.

%H Hans Riesel, <a href="/A076337/a076337.pdf">Some large prime numbers</a>. Translated from the Swedish original (Några stora primtal, Elementa 39 (1956), pp. 258-260) by Lars Blomberg.

%t Array[Function[k, SelectFirst[Range@300, PrimeQ[k 2^# - 1] &]][2 # - 1] &, 102] (* _Michael De Vlieger_, Jan 12 2018 *)

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

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

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

%Y Cf. A040081, A046069.

%K nonn

%O 1,1

%A _Jorge Coveiro_, Jun 04 2005

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

%E Name corrected by _T. D. Noe_, Feb 13 2011