A058887 -id:A058887 - cp's OEIS frontend

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

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

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

A181662 a(n) is the smallest positive integral multiple of 2^n not in the range of the Euler phi function.

Original entry on oeis.org

3, 14, 68, 152, 304, 608, 1984, 3968, 12032, 24064, 48128, 96256, 192512, 385024, 770048, 1540096, 3080192, 6160384, 12320768, 24641536, 49283072, 98566144, 197132288, 394264576, 788529152, 1577058304, 3154116608, 6308233216, 12616466432, 25232932864, 50465865728, 100931731456

Offset: 0

N. J. A. Sloane, Nov 18 2010

nonn

From Jianing Song, Dec 14 2021: (Start)
Let a(n) = 2^n * k, then k must be odd, otherwise a(n)/2 is a totient number, which implies that a(n) is a totient.
Note that 271129 * 2^m is a nontotient for all m (see A058887), so k <= 271129. In fact, let p be smallest prime such that 2^e*p + 1 is composite for all 0 <= e <= n, then k <= p (since 2^n*p is a nontotient).
Actually, k is equal to p. To verify this, it suffices to show that k cannot be an odd composite number < 271129; that is to say, if 2^n * k is a nontotient for an odd composite number < 271129, then there exists k' < k such that 2^n * k' is a nontotient.
The case k < 383 can be easily checked. Let k be an odd composite number in the range (383, 271129), k * 2^n is a nontotient implies n < 2554 unless k = 98431 or 248959 (see the a-file below), then 383 * 2^n is a nontotient (the least n such that 383 * 2^n + 1 is prime is n = 6393). For k = 98431 or 248959, k * 2^n is a nontotient implies n < 7062, then 2897 * 2^n is a nontotient (the least n such that 2897 * 2^n + 1 is prime is n = 9715. (End)

David Harden, Posting to Sequence Fans Mailing List, Sep 19 2010.

Jianing Song, List of odd composites < 271129 such that the smallest n such that k * 2^n is a totient is greater than 100.

Cf. A005277, A007617, A058887, A040076, A057192.

a(n) = A058887(n)*2^n.

Escape clause removed by Jianing Song, Dec 14 2021

A057247 a(n) is the smallest prime of the form 1 + prime(n)*2^m, with m > 0.

Original entry on oeis.org

5, 7, 11, 29, 23, 53, 137, 1217, 47, 59, 7937, 149, 83, 173

Offset: 1

Labos Elemer, Jan 10 2001

nonn

The prime a(15) has 178 decimal digits. [Corrected by Sean A. Irvine, May 27 2022]

			Sophie-Germain primes are here at n = 1, 2, 3, 5, 9, 10, .. etc. At n = 11, p(11) = 31 and in the sequence of q = 1+31*{2, 4, 8, 16, 32, 64, 128, 256} = {63, 125, 249, 497, 993, 1985, 3969, 7937}, the first prime is 7937, so b(11) = 8, a(11) = 7937.

Alois P. Heinz, Table of n, a(n) for n = 1..75
Jean-François Alcover, Table of n, a(n) for n=16..50.

Cf. A058887, A005384, A005385, A057192.

a:= proc(n) option remember; local p, m, t; p:= ithprime(n);
      for m do t:= 1+p*2^m; if isprime(t) then return t fi od
    end:
seq(a(n), n=1..15);  # Alois P. Heinz, May 27 2022

a[n_] := (For[pn = Prime[n]; p = 2, p < 3*10^8 (* large enough to compute 50 terms except a(15) *), p = NextPrime[p], m = Log[2, (p-1)/pn]; If[m > 0 && IntegerQ[m], Print["a(", n, ") = ", p]; Return[p]]]; Print["a(", n, ") not found ", p]; 0); Table[a[n], {n, 1, 50}] (* Jean-François Alcover, Nov 08 2016 *)

from sympy import isprime, prime
def a(n):
    m, pn = 1, prime(n)
    while not isprime(1 + pn*2**m): m += 1
    return 1 + pn*2**m
print([a(n) for n in range(1, 21)]) # Michael S. Branicky, May 27 2022

a(n) = Min{q|q is prime, p(n) is the n-th prime and q = 1+p(n)*2^b(n)}.

Title clarified by Sean A. Irvine, May 27 2022

A350118 Primes p for which the smallest m such that p*2^m + 1 is prime increases. Sequence terminates with the smallest prime Sierpiński number.

Original entry on oeis.org

2, 3, 7, 17, 19, 31, 47, 383, 2897, 3061, 5297, 7013, 10223

Offset: 1

Jianing Song, Dec 14 2021

The smallest prime Sierpiński number is likely to be 271129.
Related to A058887: this sequence is A058887 with repeated values removed. The following list shows that relation between these two sequences:
a(2) = 3, A350119(2) = 1 => A058887(0..0) = 3;
a(3) = 7, A350119(3) = 2 => A058887(1..1) = 7;
a(4) = 17, A350119(4) = 3 => A058887(2..2) = 17;
a(5) = 19, A350119(5) = 6 => A058887(3..5) = 19;
a(6) = 31, A350119(6) = 8 => A058887(6..7) = 31;
a(7) = 47, A350119(7) = 583 => A058887(8..582) = 47;
a(8) = 383, A350119(8) = 6393 => A058887(583..6392) = 383;
...
a(N) is the smallest prime Sierpiński number, A350119(N) = -1 => A058887(k) = a(N) for all k >= A350119(N-1).

			Let b(p) be the smallest m such that p*2^m + 1 is prime. We have a(1) = 2 with b(2) = 0.
The least prime p such that b(p) > 0 is p = 3 with b(3) = 1, so a(2) = 3.
The least prime p such that b(p) > 1 is p = 7 with b(7) = 2, so a(3) = 7.
The least prime p such that b(p) > 2 is p = 17 with b(17) = 3, so a(4) = 17.
The least prime p such that b(p) > 3 is p = 19 with b(19) = 6, so a(5) = 19.
The least prime p such that b(p) > 6 is p = 31 with b(31) = 8, so a(6) = 31.
The least prime p such that b(p) > 8 is p = 47 with b(47) = 583, so a(7) = 47.

Cf. A058887, A057192, A350119, A064699, A076336 (Sierpiński numbers).

b(p) = for(k=0, oo, if(isprime(p*2^k+1), return(k)))
list(lim) = if(lim>=2, my(v=[2],r=0); forprime(p=2, lim, if(b(p)>r, r=b(p); v=concat(v,p))); v)

cp's OEIS Frontend

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

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A181662 a(n) is the smallest positive integral multiple of 2^n not in the range of the Euler phi function.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A057247 a(n) is the smallest prime of the form 1 + prime(n)*2^m, with m > 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

A350118 Primes p for which the smallest m such that p*2^m + 1 is prime increases. Sequence terminates with the smallest prime Sierpiński number.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

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.