A040081 -id:A040081 - cp's OEIS frontend

A046069 Riesel Problem: Smallest m >= 0 such that (2n-1)2^m-1 is prime, or -1 if no such value exists.

2, 0, 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

Offset: 1

Eric W. Weisstein

nonn

There exist odd integers 2k-1 such that (2k-1)2^n-1 is always composite.

Ribenboim, P., The New Book of Prime Number Records. New York: Springer-Verlag, pp. 357-359, 1996.

T. D. Noe, Table of n, a(n) for n=1..1000
Hans Riesel, Some large prime numbers. Translated from the Swedish original (Några stora primtal, Elementa 39 (1956), pp. 258-260) by Lars Blomberg.
Eric Weisstein's World of Mathematics, Riesel Number.

Main sequences for Riesel problem: A038699, A040081, A046069, A050412, A052333, A076337, A101036, A108129.
Cf. A046067, A046070.
Bisection of A040081.

max = 10^6; (* this maximum value of m is sufficient up to n=1000 *) a[1] = 2; a[2] = 0; a[n_] := For[m = 1, m <= max, m++, If[PrimeQ[(2*n - 1)*2^m - 1], Return[m]]] /. Null -> -1; Reap[ Do[ Print[ "a(", n, ") = ", a[n]]; Sow[a[n]], {n, 1, 100}]][[2, 1]] (* Jean-François Alcover, Nov 15 2013 *)

A194591 Least k >= 0 such that n2^k - 1 or n2^k + 1 is prime, or -1 if no such value exists.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 1, 0, 2, 0, 1, 0, 1, 0, 1, 0, 2, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 5, 0, 3, 0, 1, 1, 1, 0, 2, 0, 1, 0, 2, 0, 2, 0, 1, 1, 2, 0, 1, 0, 1, 0, 1, 0, 4, 1

Offset: 1

Arkadiusz Wesolowski, Aug 29 2011

sign

Fred Cohen and J. L. Selfridge showed that a(n) = -1 infinitely often.

a(n) = 0 iff n is in A045718.

			For n=7, 7*2^0-1 and 7*2^0+1 are composite, but 7*2^1-1=13 is prime, so a(7)=1.

Arkadiusz Wesolowski, Table of n, a(n) for n = 1..1000
Fred Cohen and J. L. Selfridge, Not every number is the sum or difference of two prime powers, Math. Comp. 29 (1975), 79-81.
Eric Weisstein's World of Mathematics, Brier Number

Cf. A194603, A194606, A194607, A194608, A194635, A194636, A194637, A194638, A194639.
Cf. A040081, A040076, A076335, A180247.
Cf. A217892 and A194600 (indices and values of the records).

Table[k = 0; While[! PrimeQ[n*2^k - 1] && ! PrimeQ[n*2^k + 1], k++]; k, {n, 100}] (* T. D. Noe, Aug 29 2011 *)

If a(n)>0, then a(2n)=a(n)-1.

A194606 Least k >= 0 such that prime(n)2^k - 1 or prime(n)2^k + 1 is prime, or -1 if no such value exists, where prime(n) denotes the n-th prime number.

Original entry on oeis.org

0, 0, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 2, 4, 1, 5, 3, 2, 2, 2, 1, 1, 1, 1, 3, 3, 3, 6, 1, 2, 1, 2, 1, 3, 4, 1, 2, 4, 1, 1, 3, 1, 2, 2, 1, 1, 3, 2, 1, 1, 1, 11, 1, 4, 2, 3, 1, 2, 1, 11, 1, 1, 9, 3, 6, 1, 1, 3, 3, 4, 1, 1, 2, 1, 2, 11, 4, 3, 2, 1, 4, 1, 2, 1, 1

Offset: 1

Arkadiusz Wesolowski, Aug 30 2011

sign

A194607 gives the record values.

			For n=4, 7*2^0-1 and 7*2^0+1 are composite, but 7*2^1-1=13 is prime, so a(4)=1.

Arkadiusz Wesolowski, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Brier Number

Cf. A194591, A194600, A194603, A194607, A194608, A194635, A194636, A194637, A194638, A194639.

Cf. A040081, A040076, A076335, A180247.

Table[p = Prime[n]; k = 0; While[! PrimeQ[p*2^k - 1] && ! PrimeQ[p*2^k + 1], k++]; k, {n, 100}] (* Arkadiusz Wesolowski, Sep 04 2011 *)

A194636 Least k >= 0 such that (2n-1)2^k - 1 or (2n-1)2^k + 1 is prime, or -1 if no such value exists.

Original entry on oeis.org

0, 0, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 4, 1, 1, 1, 1, 1, 5, 3, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 1, 4, 1, 1, 1, 2, 1, 1, 1, 3, 3, 1, 3, 6, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 3, 1, 2, 1, 1, 2, 5, 1, 3, 4, 1, 1, 1, 1, 2, 2, 1, 4, 1, 2

Offset: 1

Arkadiusz Wesolowski, Aug 31 2011

sign

Bisection of A194591: a(n) = A194591(2*n-1).

A194637 gives the record values.

			For n=4, 7*2^0-1 and 7*2^0+1 are composite, but 7*2^1-1=13 is prime, so a(4)=1.

Arkadiusz Wesolowski, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Brier Number

Cf. A194591, A194600, A194603, A194606, A194607, A194608, A194635, A194637, A194638, A194639.

Cf. A040081, A040076, A076335, A180247.

Table[n = 2*n - 1; k = 0; While[! PrimeQ[n*2^k - 1] && ! PrimeQ[n*2^k + 1], k++]; k, {n, 100}] (* Arkadiusz Wesolowski, Sep 04 2011 *)
p[n_]:=Module[{c=2n-1,k=0},While[!Or@@PrimeQ[c*2^k+{1,-1}],k++];k]; Array[ p,90] (* Harvey P. Dale, Mar 08 2013 *)

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.

Original entry on oeis.org

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

A108234 Minimum m such that n*2^m+k is prime, for k < 2^m. In other words, assuming you've read n out of a binary stream, a(n) is the minimum number of additional bits (appended to the least significant end of n) you must read before it is possible to obtain a prime.

Original entry on oeis.org

1, 0, 0, 2, 0, 1, 0, 1, 1, 2, 0, 3, 0, 1, 1, 2, 0, 1, 0, 1, 1, 2, 0, 2, 2, 1, 2, 2, 0, 1, 0, 2, 1, 2, 1, 1, 0, 3, 1, 2, 0, 3, 0, 1, 2, 3, 0, 1, 2, 1, 1, 2, 0, 1, 2, 1, 2, 2, 0, 2, 0, 2, 1, 2, 1, 4, 0, 1, 1, 2, 0, 3, 0, 1, 1, 2, 2, 1, 0, 3, 1, 2, 0, 2, 3, 1, 2, 2, 0, 1, 2, 3, 2, 2, 1, 1, 0, 1, 1, 2

Offset: 1

Mike Stay, Jun 16 2005

Somewhat related to the Riesel problem, A040081, the minimum m such that n*2^m-1 is prime.

			a(12) = 3 because 12 = 1100 in binary and 97 = 1100001 is the first prime that starts with 1100, needing 3 extra bits.

Antti Karttunen, Table of n, a(n) for n = 1..16384

Cf. A040081, A091991, A164022 (smallest prime).

% and Octave.
for n=1:100;m=0;k=0;while(~isprime(n*2^m+k))k=k+1;if k==2^m k=0;m=m+1;end;end;x(n)=m;end;x

A108234(n) = { my(m=0,k=0); while(!isprime((n*2^m)+k), k=k+1; if(2^m==k, k=0; m=m+1)); m; }; \\ Antti Karttunen, Dec 16 2017, after Octave/MATLAB code

Definition clarified by Antti Karttunen, Dec 16 2017

A250205 Riesel problem in base 6: Least k > 0 such that n*6^k-1 is prime, or 0 if no such k exists.

Original entry on oeis.org

1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 2, 1, 1, 0, 1, 1, 1, 2, 0, 1, 1, 2, 1, 0, 2, 1, 1, 1, 0, 1, 1, 2, 2, 0, 4, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 4, 1, 3, 0, 1, 1, 6, 2, 0, 5, 1, 1, 1, 0, 6, 2, 1, 1, 0, 1, 2, 10, 1, 0, 1, 3, 1, 1, 0, 1, 1, 2, 1, 0, 1, 8, 1, 1, 0, 1, 2, 2, 4, 0, 49, 1, 1, 1, 0, 2, 1, 1, 1, 0, 2, 1, 6, 2, 0, 1, 1, 1, 1, 0, 5, 1, 1, 2, 0, 1, 10, 2, 1

Offset: 1

Eric Chen, Mar 13 2015

nonn

a(5j+1) = 0 except for a(1), since (5j+1)*6^k-1 is always divisible by 5, but there are infinitely many numbers not in the form 5j+1 such that a(n) = 0.
a(n) = 0 for n == 84687 mod 10124569, because then n*6^k-1 is always divisible by at least one of 7, 13, 31, 37, 97. - Robert Israel, Mar 17 2015
Conjecture: if n is not in the form 5j+1 and n < 84687, then a(n) > 0.

Eric Chen, Table of n, a(n) for n = 1..1000
Gary Barnes, Riesel conjectures and proofs

Cf. A040081, A046069, A050412, A108129.

Cf. A250204 (Least k > 0 such that n*6^k+1 is prime).

N:= 1000: # to get a(1) to a(N), using k up to 10000
a[1]:= 1:
for n from 2 to N do
if n mod 5 = 1 then a[n]:= 0
else
    for k from 1 to 10000 do
    if isprime(n*6^k-1) then
       a[n]:= k;
         break
      fi
    od
fi
od:
seq(a[n],n=1..N); # Robert Israel, Mar 17 2015

(* m <= 10000 is sufficient up to n = 1000 *)
a[n_] := For[k = 1, k <= 10000, k++, If[PrimeQ[n*6^k - 1], Return[k]]] /. Null -> 0; Table[a[n], {n, 1, 120}]

a(n) = if(n%5==1 && n>1, 0, for(k = 1, 10000, if(ispseudoprime(n*6^k-1), return(k))))

a(A024898(n)) = 1. - Michel Marcus, Mar 16 2015

A093008 Smallest number of 1's to append to the binary representation of n such that primes become nonprimes and nonprimes become primes.

Original entry on oeis.org

1, 5, 2, 2, 4, 1, 1, 1, 1, 2, 3, 3, 1, 1, 1, 2, 1, 1, 1, 1, 1, 4, 2, 3, 2, 1, 3, 4, 2, 1, 1, 2, 1, 2, 1, 1, 1, 3, 1, 2, 3, 7, 1, 1, 3, 4, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 3, 12, 1, 3, 1, 2, 1, 4, 1, 5, 1, 1, 1, 2, 1, 7, 1, 1, 1, 2, 2, 1, 1, 3, 1, 2, 2, 5, 6, 1, 23, 4, 6, 1, 2, 3, 3, 2, 1, 1, 1, 1, 1, 10

Offset: 1

Reinhard Zumkeller, Mar 14 2004

nonn

n>1: a(n) = A063377(n) + A040081(n+1).

Cf. A093009.

A217377 a(n) is the smallest m>=0 such that ((5n+1)*6^m-1)/5 is prime; or -1 if no such value exists.

Original entry on oeis.org

1, 0, 0, 2, 0, 1, 0, 4, 2, 1, 0, 1, 0, 3, 2, 1, 0, 1, 0, 2, 1, 4, 0, 3, 1, 1, 1, 3, 0, 1, 0, 1, 1, 2, 1, 2, 0, 1, 3, 1, 0, 15, 0, 3, 1, 1, 0, 4, 3, 3008, 1, 1, 0, 2, 1, 1, 4, 1, 0, 3, 0, 1, 1, 2, 2, 1, 0, 1, 3, 1, 0, 1, 0, 2, 2, 1, 1, 4, 0, 2, 1, 4, 0, 5, 2, 8

Offset: 1

Dmitri Kamenetsky, Oct 01 2012

nonn

Let f(n)=6n+1. Let f(n,m) be f applied to n m-times. For example f(n,3) = f(f(f(n))). Then a(n) is the smallest m>=0 such that f(n,m) is prime.
a(525)=27871 is the largest found value in this sequence, which generates a probable prime with 21691 digits.
a(1247) and a(1898) are currently unknown. If they are positive then a(1247)>86500 and a(1898)>58000.

			a(8)=4, because 4 is the smallest value for m such that ((5*8+1)*6^m-1)/5 is prime. The prime value is (41*6^4-1)/5 = 6*(6*(6*(6*8+1)+1)+1)+1 = 10627.

Dmitri Kamenetsky, Table of n, a(n) for n = 1..1246

Cf. A040081.

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

A046069 Riesel Problem: Smallest m >= 0 such that (2n-1)2^m-1 is prime, or -1 if no such value exists.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

A194591 Least k >= 0 such that n*2^k - 1 or n*2^k + 1 is prime, or -1 if no such value exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A194606 Least k >= 0 such that prime(n)*2^k - 1 or prime(n)*2^k + 1 is prime, or -1 if no such value exists, where prime(n) denotes the n-th prime number.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A194636 Least k >= 0 such that (2*n-1)*2^k - 1 or (2*n-1)*2^k + 1 is prime, or -1 if no such value exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

A108234 Minimum m such that n*2^m+k is prime, for k < 2^m. In other words, assuming you've read n out of a binary stream, a(n) is the minimum number of additional bits (appended to the least significant end of n) you must read before it is possible to obtain a prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

MATLAB

PARI

Extensions

A250205 Riesel problem in base 6: Least k > 0 such that n*6^k-1 is prime, or 0 if no such k exists.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A093008 Smallest number of 1's to append to the binary representation of n such that primes become nonprimes and nonprimes become primes.

Views

A194591 Least k >= 0 such that n2^k - 1 or n2^k + 1 is prime, or -1 if no such value exists.

A194606 Least k >= 0 such that prime(n)2^k - 1 or prime(n)2^k + 1 is prime, or -1 if no such value exists, where prime(n) denotes the n-th prime number.

A194636 Least k >= 0 such that (2n-1)2^k - 1 or (2n-1)2^k + 1 is prime, or -1 if no such value exists.