A046067 -id:A046067 - cp's OEIS frontend

A260349 a(n) = min(k : A046067((k+1)/2) = n).

1, 3, 7, 17, 55, 59, 19, 167, 31, 311, 289, 227, 351, 203, 379, 197, 103, 1253, 829, 335, 211, 353, 649, 437, 1921, 1853, 2869, 917, 361, 263, 283, 1637, 1213, 3353, 1519, 797, 241, 1691, 259, 1391, 2503, 1109, 3859, 1857

Offset: 0

Hugo van der Sanden, Jul 23 2015

nonn

a(n) is the first odd number k for which k * 2^i + 1 is prime when i = n but composite for all i: 0 <= i < n, or 0 if no such k exists. Thus it is the first k for which A046067((k+1)/2) = n, and therefore also the first k for which you need to test the primality of exactly n values to show that it is not a Sierpiński number.

Jaeschke shows that for each n>0, the set {k : A046067((k+1)/2) = n} is infinite. - Jeppe Stig Nielsen, Jul 06 2020

			7 * 2^i + 1 is composite for i < 2 (with values 8, 15) but prime for i = 2 (29); the smaller odd numbers 1, 3 and 5 each yield a prime for smaller i, so a(2) = 7.

Hugo van der Sanden, Table of n, a(n) for n = 0..3253
G. Jaeschke, On the Smallest k Such that All k*2^N + 1 are Composite, Mathematics of Computation, Vol. 40, No. 161 (Jan., 1983), pp. 381-384.

Cf. A046067, A076336, A260350.

a(n)=forstep(k=1,+oo,2,for(i=0,n-1,ispseudoprime(k<Jeppe Stig Nielsen, Jul 06 2020

A029810 Erroneous version of A033809, A046067.

Original entry on oeis.org

1, 2, 1, 2, 1, 1, 2, 1, 3, 6, 1, 1, 2, 2, 1, 8, 1, 1, 2, 1, 1, 2, 2, 583, 2, 1, 1, 4, 2, 5, 4, 1

Offset: 1

dead

A040076 Smallest m >= 0 such that n*2^m + 1 is prime, or -1 if no such m exists.

Original entry on oeis.org

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, 1, 2, 0, 1, 1, 8, 7, 2, 582, 1, 0, 2, 1, 1, 0, 3, 0

Offset: 1

David W. Wilson

Sierpiński showed that a(n) = -1 infinitely often. John Selfridge showed that a(78557) = -1 and it is conjectured that a(n) >= 0 for all n < 78557.

Determining a(131072) = a(2^17) is equivalent to finding the next Fermat prime after F_4 = 2^16 + 1. - Jeppe Stig Nielsen, Jul 27 2019

			1*(2^0)+1=2 is prime, so a(1)=0;
3*(2^1)+1=5 is prime, so a(3)=1;
For n=7, 7+1 and 7*2+1 are composite, but 7*2^2+1=29 is prime, so a(7)=2.

T. D. Noe, Table of n, a(n) for n = 1..10000 (with help from the Sierpiński problem website)
Ray Ballinger and Wilfrid Keller, The Sierpiński Problem: Definition and Status
Seventeen or Bust, A Distributed Attack on the Sierpiński problem

For the corresponding primes see A050921.
Cf. A103964, A040081.
Cf. A033809, A046067 (odd n), A057192 (prime n).

Do[m = 0; While[ !PrimeQ[n*2^m + 1], m++ ]; Print[m], {n, 1, 110} ]
sm[n_]:=Module[{k=0},While[!PrimeQ[n 2^k+1],k++];k]; Array[sm,120] (* Harvey P. Dale, Feb 05 2020 *)

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

Original entry on oeis.org

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

A057192 Least m such that 1 + prime(n)*2^m is a prime, or -1 if no such m exists.

Original entry on oeis.org

0, 1, 1, 2, 1, 2, 3, 6, 1, 1, 8, 2, 1, 2, 583, 1, 5, 4, 2, 3, 2, 2, 1, 1, 2, 3, 16, 3, 6, 1, 2, 1, 3, 2, 3, 4, 8, 2, 7, 1, 1, 4, 1, 2, 15, 2, 20, 8, 11, 6, 1, 1, 36, 1, 279, 29, 3, 4, 2, 1, 30, 1, 2, 9, 4, 7, 4, 4, 3, 10, 21, 1, 12, 2, 14, 6393, 11, 4, 3, 2, 1, 4, 1, 2, 6, 1, 3, 8, 5, 6, 19, 3, 2, 1, 2, 5

Offset: 1

Labos Elemer, Jan 10 2001

sign

Primes p such that p * 2^m + 1 is composite for all m are called Sierpiński numbers. The smallest known prime Sierpiński number is 271129. Currently, 10223 is the smallest prime whose status is unknown.
For 0 < k < a(n), prime(n)*2^k is a nontotient. See A005277. - T. D. Noe, Sep 13 2007
With the discovery of the primality of 10223 * 2^31172165 + 1 on November 6, 2016, we now know that 10223 is not a Sierpiński number. The smallest prime of unknown status is thus now 21181. The smallest confirmed instance of a(n) = -1 is for n = 78557. - Alonso del Arte, Dec 16 2016 [Since we only care about prime Sierpiński numbers in this sequence, 78557 should be replaced by primepi(271129) = 23738. - Jianing Song, Dec 15 2021]
Aguirre conjectured that, for every n > 1, a(n) is even if and only if prime(n) mod 3 = 1 (see the MathStackExchange link below). - Lorenzo Sauras Altuzarra, Feb 12 2021
If prime(n) is not a Fermat prime, then a(n) is also the least m such that prime(n)*2^m is a totient number, or -1 if no such m exists. If prime(n) = 2^2^e + 1 is a Fermat prime, then the least m such that prime(n)*2^m is a totient number is min{2^e, a(n)} if a(n) != -1 or 2^e if a(n) = -1, since 2^2^e * (2^2^e + 1) = phi((2^2^e+1)^2) is a totient number. For example, the least m such that 257*2^m is a totient number is m = 8, rather than a(primepi(257)) = 279; the least m such that 65537*2^m is a totient number is m = 16, rather than a(primepi(65537)) = 287. - Jianing Song, Dec 15 2021

			a(8) = 6 because prime(8) = 19 and the first prime in the sequence 1 + 19 * {2, 4, 8,1 6, 32, 64} = {39, 77, 153, 305, 609, 1217} is 1217 = 1 + 19 * 2^6.

See A046067.

T. D. Noe, Table of n, a(n) for n = 1..1000
Ray Ballinger and Wilfrid Keller, Sierpiński Problem
Timothy Revell, "Crowdsourced prime number could help solve a 50-year-old problem", New Scientist, November 18, 2016.
Tejas R. Rao, Effective primality test for p*2^n+1, p prime, n>1, arXiv:1811.06070 [math.NT], 2018.
Seventeen or Bust, A Distributed Attack on the Sierpinski problem
StackExchange, If p is prime, does there exist a positive integer k such that 2^k*p + 1 is also prime?

Cf. A058887, A058811, A058812, A002202, A014197, A005277, A005384, A005385, A051686.
Cf. A046067 (least k such that (2n - 1) * 2^k + 1 is prime).
a(n) = -1 if and only if n is in A076336.

a := proc(n)
   local m:
   m := 0:
   while not isprime(1+ithprime(n)*2^m) do m := m+1: od:
   m:
end: # Lorenzo Sauras Altuzarra, Feb 12 2021

Table[p = Prime[n]; k = 0; While[Not[PrimeQ[1 + p * 2^k]], k++]; k, {n, 100}] (* T. D. Noe *)

a(n) = my(m=0, p=prime(n)); while (!isprime(1+p*2^m), m++); m; \\ Michel Marcus, Feb 12 2021

Corrected by T. D. Noe, Aug 03 2005

A033809 Smallest m>0 such that (2n-1)2^m+1 is prime, or -1 if no such value exists.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 2, 1, 3, 6, 1, 1, 2, 2, 1, 8, 1, 1, 2, 1, 1, 2, 2, 583, 2, 1, 1, 4, 2, 5, 4, 1, 1, 2, 1, 3, 2, 1, 3, 2, 1, 1, 4, 2, 1, 8, 2, 1, 2, 1, 3, 16, 1, 3, 6, 1, 1, 2, 3, 1, 8, 6, 1, 2, 3, 1, 4, 1, 3, 2, 1, 53, 6, 8, 3, 4, 1, 1, 8, 6, 3, 2, 1, 7, 2, 8, 1, 2, 2, 1, 4, 1, 3, 6, 1, 1, 2, 4, 15, 2

Offset: 1

Eric W. Weisstein

sign

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

Cf. A046067 (except for initial term a(1) identical to this sequence), A046068, A046069, A046070.

Cf. A040076

A046068 Second smallest m such that (2n-1)2^m+1 is prime, or -1 if no such value exists.

Original entry on oeis.org

1, 2, 3, 4, 2, 3, 8, 2, 15, 10, 4, 9, 4, 4, 3, 60, 6, 3, 4, 2, 11, 6, 9, 1483, 6, 3, 5, 8, 3, 11, 12, 4, 3, 6, 2, 5, 6, 3, 7, 10, 4, 5, 6, 6, 7, 168, 4, 3, 4, 2, 9, 18, 2, 7, 14, 4, 5, 12, 4, 3, 12, 8, 5, 12, 5, 3, 6, 2, 27, 14, 3, 77, 16, 11, 7, 20, 2, 7, 12, 7, 5, 4, 2, 103, 14, 9, 13, 4

Offset: 1

Eric W. Weisstein

sign

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.

Eric Weisstein's World of Mathematics, Riesel Number.
Eric Weisstein's World of Mathematics, Sierpiński Number of the Second Kind

Cf. A046067, A046070.

max = 10000 (* this maximum value of m is sufficient up to n=191 *); a[n_] := Reap[ For[m = 1; cnt = 0, m <= max && cnt < 2, m++, If[m == max, Sow[-1], If[PrimeQ[(2*n - 1)*2^m + 1], cnt++; Sow[m]]]]][[2, 1]]; a[1] = {0, 1}; Table[a[n][[2]], {n, 1, 88}] (* Jean-François Alcover, Feb 27 2013 *)

A057025 Smallest prime of form (2n+1)*2^m+1 for some m.

Original entry on oeis.org

2, 7, 11, 29, 19, 23, 53, 31, 137, 1217, 43, 47, 101, 109, 59, 7937, 67, 71, 149, 79, 83, 173, 181

Offset: 0

Henry Bottomley, Jul 24 2000

nonn

next term a(23) = 47*2^583+1 > 10^177. Sequence then continues: 197, 103, 107, 881, 229, 1889, 977, 127, 131, 269, 139, 569, 293, 151, 617, 317, 163, 167, 1361, 349, 179, 23297, 373, 191, 389, 199, 809, ...

If no such prime exists for any m then 2n+1 is called a Sierpiński number. One could use a(n) = 0 for these cases. E.g., a(39278) = 0 because 78557 is a Sierpiński number. For the corresponding numbers m see A046067(n+1), n >= 0, where -1 entries corresponds to a(n) = 0. See also the Sierpiński links there. - Wolfdieter Lang, Feb 07 2013

			a(5)=23 because 2*5+1=11 and smallest prime of the form 11*2^m+1 is 23 (since 11+1=12 is not prime)

Index entries for sequences of n such that k*2^n-1 (or k*2^n+1) is prime

Cf. A032373, A057023, A057026, A046067.

A253178 Least k>=1 such that 2*A007494(n)^k+1 is prime.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 47, 1, 1, 1, 1, 2, 1, 2, 1, 1, 3, 1, 1, 1, 2729, 1, 1, 2, 1, 2, 175, 1, 1, 1, 1, 1, 1, 3, 3, 3, 43, 1, 1, 2, 1, 1, 3, 2, 1, 1, 3, 1, 11, 1, 1, 4, 1, 2, 1, 1, 3, 2, 1, 1, 1, 1, 192275, 2, 1233, 1, 3, 5, 51, 1, 1, 1, 1, 286, 1, 1, 755, 2, 1, 4, 1, 6, 1, 2

Offset: 1

Eric Chen, Mar 20 2015

If n == 1 (mod 3), then for every positive integer k, 2*n^k+1 is divisible by 3 and cannot be prime (unless n=1). Thus we restrict the domain of this sequence to A007494 (n which is not in the form 3j+1).
Conjecture: a(n) is defined for all n.
a(145) > 200000, a(146) .. a(156) = {1, 1, 66, 1, 4, 3, 1, 1, 1, 1, 6}, a(157) > 100000, a(158) .. a(180) = {2, 1, 2, 11, 1, 1, 3, 321, 1, 1, 3, 1, 2, 12183, 5, 1, 1, 957, 2, 3, 16, 3, 1}.
a(n) = 1 if and only if n is in A144769.

Eric Chen, Table of n, a(n) for n = 1..144

Cf. A138066, A138067, A255707, A250200, A119624, A119591, A040076, A046067.

A007494[n_] := 2n - Floor[n/2];
Table[k=1; While[!PrimeQ[2*A007494[n]^k+1], k++]; k, {n, 1, 144}]

a007494(n) = n+(n+1)>>1;
a(n) = for(k=1, 2^24, if(ispseudoprime(2*a007494(n)^k+1),return(k)));

a(n) = A119624(A007494(n)).

A071628 Smallest m such that (2n-1)2^m is totient, that is, in A002202, or -1 if (2n-1)2^m is never a totient.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 2, 1, 3, 6, 1, 1, 2, 1, 1, 8, 1, 1, 2, 1, 1, 2, 2, 583, 2, 1, 1, 1, 2, 5, 4, 1, 1, 2, 1, 3, 2, 1, 3, 2, 1, 1, 4, 2, 1, 4, 2, 1, 2, 1, 3, 16, 1, 3, 6, 1, 1, 2, 2, 1, 4, 2, 1, 2, 3, 1, 4, 1, 3, 2, 1, 3, 2, 1, 3, 4, 1, 1, 8, 2, 3, 2, 1, 7, 2, 1, 1, 2, 2, 1, 4, 1, 3, 4, 1, 1, 2, 2, 15, 2, 3, 2

Offset: 1

Labos Elemer, May 30 2002

nonn

When 2n-1 is the k-th prime, then a(n) = A040076(2n-1) = A046067(n) = A057192(k). [This is only partially correct. If 2n-1 = 2^2^m + 1 is a Fermat prime, then a(n) = min{2^m, A040076(2n-1)} if 2n-1 is not a Sierpiński number and a(n) = 2^m otherwise, since phi((2n-1)^2) = (2n-1)*2^m. For example, a(129) = 8 < A040076(257) = 279, a(32769) = 16 < A040076(65537) = 287. - Jianing Song, Dec 14 2021]
From Jianing Song, Dec 14 2021: (Start)
a(1) should have been 0.
If 2n-1 is a prime Sierpiński number which is not a Fermat prime, then a(2n-1) = -1.
Do there exists n such that 2n-1 is composite and that a(2n-1) = -1? It seems very unlikely that this will happen: Let 2n-1 = (a_1)^(e_1) * (a_2)^(e_2) * ... * (a_r)^(e_r) * (q_1)^(f_1) * (q_2)^(f_2) * ... * (q_s)^(f_s), where a_1, a_2, ..., a_r are distinct numbers that are not Fermat primes (a_i is not necessarily a prime), q_1, q_2, ..., q_s are distinct Fermat primes. If p_{i,1}, p_{i,2}, ..., p_{i,e_i} are distinct primes of the form 2^e * (a_i) + 1, then the odd part of phi((Product_{i=1..r, j=1..e_i} p_{i,j}) * (Product_{i=1..s} (q_s)^(1+f_s))) is 2n-1.
Therefore, if k is not a Sierpiński number implies that there are infinitely many e such that 2^e * k + 1 is prime, then a necessary condition for a(2n-1) = -1 is that: for every factorization 2n-1 = (u_1) * (u_2) * ... * (u_t) (u_i is not necessarily a prime, and (u_i)'s are not necessarily distinct), at least one u_i must be a Sierpiński number which is not a Fermat prime. In particular, 2n-1 itself must be a Sierpiński number. (End)

			n=52:2n-1=13, [seq(nops(invphi(103*2^i)),i=1..25)]; gives: [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,6,8,10,12,14,16,18,20]; nonzero appears first at position 16, so a(52)=16,since 6750208=103.2^16 is totient, while 3375104 is nontotient. n=24, 2n-1=47: the first nonempty InvPhi(47.2^i) set arises at i=a[24]=583, a very large number.

T. D. Noe, Table of n, a(n) for n=1..1000
D. Bressoud, CNT.m Computational Number Theory Mathematica package.

Similar to but different from A046067. See also A058887, A057192.

Cf. A000010, A002202, A007617, A076336 (Sierpiński numbers).

with(numtheory); [seq(nops(invphi(odd*2^i)),i=1..N)]; Position of first nonzero provides a[n] belonging to 2n-1 odd number.

Needs["CNT`"]; Table[m=1; While[PhiInverse[n*2^m] == {}, m++], {n,1,200,2}]

a(n)=Min[{x; Card(InvPhi[(2n-1)*(2^x)])>0}]

Escape clause added by Jianing Song, Dec 14 2021

cp's OEIS Frontend

A260349 a(n) = min(k : A046067((k+1)/2) = n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A029810 Erroneous version of A033809, A046067.

Views

Author

Keywords

A040076 Smallest m >= 0 such that n*2^m + 1 is prime, or -1 if no such m exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

A057192 Least m such that 1 + prime(n)*2^m is a prime, or -1 if no such m exists.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A033809 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

A046068 Second smallest m 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

A057025 Smallest prime of form (2n+1)*2^m+1 for some m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A253178 Least k>=1 such that 2*A007494(n)^k+1 is prime.

Views

Author

Keywords

Comments

A071628 Smallest m such that (2n-1)2^m is totient, that is, in A002202, or -1 if (2n-1)2^m is never a totient.