A058812 -id:A058812 - 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

A334111 Irregular triangle where row n gives all terms k for which A064097(k) = n.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 8, 7, 9, 10, 12, 16, 11, 13, 14, 15, 17, 18, 20, 24, 32, 19, 21, 22, 25, 26, 27, 28, 30, 34, 36, 40, 48, 64, 23, 29, 31, 33, 35, 37, 38, 39, 41, 42, 44, 45, 50, 51, 52, 54, 56, 60, 68, 72, 80, 96, 128, 43, 46, 49, 53, 55, 57, 58, 61, 62, 63, 65, 66, 70, 73, 74, 75, 76, 78, 81, 82, 84

Offset: 0

Antti Karttunen, Michael De Vlieger and Robert G. Wilson v, Apr 14 2020

Applying map k -> (p-1)*(k/p) to any term k on any row n > 1, where p is any prime factor of k, gives one of the terms on preceding row n-1.
Any prime that appears on row n is 1 + {some term on row n-1}.
The e-th powers of the terms on row n form a subset of terms on row (e*n). More generally, a product of terms that occur on rows i_1, i_2, ..., i_k can be found at row (i_1 + i_2 + ... + i_k), because A064097 is completely additive.
A001221(k) gives the number of terms on the row above that are immediate descendants of k.
A067513(k) gives the number of terms on the row below that lead to k.

			Rows 0-6 of the irregular table:
0 |   1;
1 |   2;
2 |   3, 4;
3 |   5, 6, 8;
4 |   7, 9, 10, 12, 16;
5 |  11, 13, 14, 15, 17, 18, 20, 24, 32;
6 |  19, 21, 22, 25, 26, 27, 28, 30, 34, 36, 40, 48, 64;

Michael De Vlieger, Table of n, a(n) for n = 0..14422 (rows 0 <= n <= 17, flattened)
Index entries for sequences that are permutations of the natural numbers

Cf. A001221, A064097, A067513, A333123, A334144.
Cf. A105017 (left edge), A000079 (right edge), A175125 (row lengths).
Cf. also A058812, A334100.

f[n_] := Length@ NestWhileList[# - #/FactorInteger[#][[1, 1]] &, n, # != 1 &]; SortBy[ Range@70, f]
(* Second program *)
With[{nn = 8}, Values@ Take[KeySort@ PositionIndex@ Array[-1 + Length@ NestWhileList[# - #/FactorInteger[#][[1, 1]] &, #, # > 1 &] &, 2^nn], nn + 1]] // Flatten (* Michael De Vlieger, Apr 18 2020 *)

A060681(n) = (n-if(1==n,n,n/vecmin(factor(n)[,1])));
A064097(n) = if(1==n,0,1+A064097(A060681(n)));
for(n=0, 10, for(k=1,2^n,if(A064097(k)==n, print1(k,", "))));

A135832 Irregular triangle of Section I primes. Row n contains primes p with 2^n < p < 2^(n+1) and phi^n(p) = 2, where phi^n means n iterations of Euler's totient function.

Original entry on oeis.org

3, 5, 7, 11, 13, 17, 23, 29, 31, 41, 47, 53, 59, 61, 83, 89, 97, 101, 103, 107, 113, 137, 167, 179, 193, 227, 233, 239, 241, 251, 257, 353, 359, 389, 401, 409, 443, 449, 461, 467, 479, 499, 503, 641, 719, 769, 773, 809, 821, 823, 857, 881, 887, 929, 941, 953

Offset: 1

T. D. Noe, Nov 30 2007

Sequence A135833 gives the number of terms in row n. Shapiro describes how the numbers x with phi^n(x)=2 can be divided into 3 sections: I: 2^n < x < 2^(n+1), II: 2^(n+1) <= x <= 3^n and III: 3^n < x <= 2*3^n. The primes in section I are fairly sparse. All other primes belong to section II. Section III consists only of even numbers. See A058812 for the numbers x for each n.

			Table begins:
   3;
   5,  7;
  11, 13;
  17, 23, 29, 31;
  41, 47, 53, 59, 61;
  83, ...

T. D. Noe, Rows n = 1..22 of triangle, flattened
Harold Shapiro, An arithmetic function arising from the phi function, Amer. Math. Monthly, Vol. 50, No. 1 (1943), 18-30.

Cf. A135834 (Section II primes).

nMax=10; nn=2^nMax; c=Table[0,{nn}]; Do[c[[n]]=1+c[[EulerPhi[n]]], {n,2,nn}]; t={}; Do[t=Join[t,Select[Flatten[Position[c,n]], #<2^n && PrimeQ[ # ]&]], {n,nMax}]; t

A136040 Classes of the phi iteration for which the smallest number is prime.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 14, 16, 17, 19, 21, 22, 25, 26, 29, 31, 41, 49, 51, 52, 55, 58, 59, 60, 63, 65, 66, 67, 69, 71, 74, 77, 79, 81, 82, 87, 89, 108, 109, 113, 114, 116, 119, 122, 124, 127, 129, 130, 136, 137, 142, 143, 145, 147, 148, 151, 154, 158, 159, 161, 162, 163

Offset: 1

T. D. Noe, Dec 12 2007

nonn

Rows of A058812 which begin with a prime. The actual primes are in A092873, which is A007755(n+2) for the n in this sequence.

T. D. Noe, Table of n, a(n) for n=1..288
T. D. Noe, Primes in classes of the iterated totient function, JIS 11 (2008) 08.1.2
Harold Shapiro, An arithmetic function arising from the phi function, Amer. Math. Monthly, Vol. 50, No. 1 (1943), 18-30.

Added 63 and 159. - T. D. Noe, Nov 18 2008

A005239 Irregular triangle of Section I numbers. Row n contains numbers k with 2^n < k < 2^(n+1) and phi^n(k) = 2, where phi^n means n iterations of Euler's totient function.

Original entry on oeis.org

3, 5, 7, 11, 13, 15, 17, 23, 25, 29, 31, 41, 47, 51, 53, 55, 59, 61, 83, 85, 89, 97, 101, 103, 107, 113, 115, 119, 121, 123, 125, 137, 167, 179, 187, 193, 205, 221, 227, 233, 235, 239, 241, 249, 251, 253, 255, 257, 289, 353, 359, 389, 391, 401, 409

Offset: 1

N. J. A. Sloane

Sequence A092878 gives the number of terms in row n. Shapiro describes how the numbers x with phi^n(x)=2 can be divided into 3 sections: I: 2^n < x < 2^(n+1), II: 2^(n+1) <= x <= 3^n and III: 3^n < x <= 2*3^n. See A058812 for the numbers x for each n. - T. D. Noe, Dec 05 2007

			Triangle begins:
   3;
   5,  7;
  11, 13, 15;
  17, 23, 25, 29,  31;
  41, 47, 51, 53,  55,  59,  61;
  83, 85, 89, 97, 101, 103, 107, 113, 115, 119, 121, 123, 125;
  ...

R. K. Guy, Unsolved Problems in Number Theory, B41.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Rows n = 1..22 of triangle, flattened
T. D. Noe, Primes in classes of the iterated totient function, JIS 11 (2008) 08.1.2.
Harold Shapiro, An arithmetic function arising from the phi function, Amer. Math. Monthly, Vol. 50, No. 1 (1943), 18-30.

Cf. A000010, A058812, A092878.

Cf. A135832 (Section I primes).

nMax=10; nn=2^nMax; c=Table[0,{nn}]; Do[c[[n]]=1+c[[EulerPhi[n]]], {n,2,nn}]; t={}; Do[t=Join[t,Select[Flatten[Position[c,n]], #<2^n&]], {n,nMax}]; t (* T. D. Noe, Dec 05 2007 *)

More terms from Jud McCranie, Feb 15 1997

Corrected and extended by T. D. Noe, Dec 05 2007

A064674 Number of primes q such that phiter(q)=n where phiter(n)=A064415(n).

Original entry on oeis.org

0, 2, 2, 3, 6, 12, 23, 46, 94, 198, 424, 854, 1859, 3884, 8362, 17837, 38977, 84188, 183167, 398685, 874078

Offset: 0

Christian WEINSBERG (cweinsbe(AT)fr.packardbell.org), Oct 10 2001

For n>1, a(n) is the number of primes in class n of the Phi iteration. See A003434 and A058812. [From T. D. Noe, Nov 05 2008]

Cf. A000010, A003434, A064415, A064416.

a(12)-a(16) from T. D. Noe, Nov 05 2008

a(17)-a(20) from Sean A. Irvine, Jul 22 2023

A136041 Largest prime p such that phi^n(p) = 2, where phi^n means n iterations of Euler's totient function.

Original entry on oeis.org

3, 7, 19, 43, 163, 487, 1459, 3079, 8803, 39367, 78787, 196831, 581743, 2125819, 6381667, 19131877, 86093443, 258280327, 516560659, 1214874127

Offset: 1

T. D. Noe, Dec 12 2007

The largest prime in row n+1 of A058812. From Shapiro, we know that a(n) <= 1 + 2*3^(n-1). This bound is attained for n=1,2,3,5,6,7,17,18,.., which is n=A003306(k)+1 for k=1,2,3,...

Harold Shapiro, An arithmetic function arising from the phi function, Amer. Math. Monthly, Vol. 50, No. 1 (1943), 18-30.

nn=20; pk=Table[0,{nn}]; Do[p=Prime[n]; k=Length[NestWhileList[EulerPhi,p,#>2&]]-1; If[0

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

A334111 Irregular triangle where row n gives all terms k for which A064097(k) = n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A135832 Irregular triangle of Section I primes. Row n contains primes p with 2^n < p < 2^(n+1) and phi^n(p) = 2, where phi^n means n iterations of Euler's totient function.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A136040 Classes of the phi iteration for which the smallest number is prime.

Views

Author

Keywords

Comments

Links

Extensions

A005239 Irregular triangle of Section I numbers. Row n contains numbers k with 2^n < k < 2^(n+1) and phi^n(k) = 2, where phi^n means n iterations of Euler's totient function.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Extensions

A064674 Number of primes q such that phiter(q)=n where phiter(n)=A064415(n).

Views

Author

Keywords

Comments

Crossrefs

Extensions

A136041 Largest prime p such that phi^n(p) = 2, where phi^n means n iterations of Euler's totient function.

Views

Author

Keywords

Comments

Links

Programs

Mathematica