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

A058812 Irregular triangle of rows of numbers in increasing order. Row 1 = {1}. Row m + 1 contains all numbers k such that phi(k) is in row m.

Original entry on oeis.org

1, 2, 3, 4, 6, 5, 7, 8, 9, 10, 12, 14, 18, 11, 13, 15, 16, 19, 20, 21, 22, 24, 26, 27, 28, 30, 36, 38, 42, 54, 17, 23, 25, 29, 31, 32, 33, 34, 35, 37, 39, 40, 43, 44, 45, 46, 48, 49, 50, 52, 56, 57, 58, 60, 62, 63, 66, 70, 72, 74, 76, 78, 81, 84, 86, 90, 98, 108, 114, 126

Offset: 0

Labos Elemer, Jan 03 2001

Nontotient values (A007617) are also present as inverses of some previous value.

Old name was: Irregular triangle of inverse totient values of integers generated recursively. Initial value is 1. The inverse-phi sets in increasing order are as follows: {1} -> {2} -> {3, 4, 6} -> {5, 7, 8, 9, 10, 12, 14, 18} -> ... The terms of each row are arranged by magnitude. The next row starts when the increase of terms is violated. 2^n is included in the n-th row. - David A. Corneth, Mar 26 2019

			Triangle begins:
  1;
  2;
  3, 4, 6;
  5, 7, 8, 9, 10, 12, 14, 18;
  ...
Row 3 is {3, 4, 6} as for each number k in this row, phi(k) is in row 2. - _David A. Corneth_, Mar 26 2019

T. D. Noe, Rows n=0..9 of triangle, flattened
Hartosh Singh Bal, Gaurav Bhatnagar, Prime number conjectures from the Shapiro class structure, arXiv:1903.09619 [math.NT], 2019.
T. D. Noe, Primes in classes of the iterated totient function, JIS 11 (2008) 08.1.2.
Index entries for sequences that are permutations of the natural numbers

Cf. A000010, A007617, A005277.
A058811 gives the number of terms in each row.
Cf. A003434, A007755, A060611, A092878, A098196, A135832.
Cf. also A334111.

inversePhi[m_?OddQ] = {}; inversePhi[1] = {1, 2}; inversePhi[m_] := Module[{p, nmax, n, nn}, p = Select[Divisors[m] + 1, PrimeQ]; nmax = m*Times @@ (p/(p-1)); n = m; nn = {}; While[n <= nmax, If[EulerPhi[n] == m, AppendTo[nn, n]]; n++]; nn]; row[n_] := row[n] = inversePhi /@ row[n-1] // Flatten // Union; row[0] = {1}; row[1] = {2}; Table[row[n], {n, 0, 5}] // Flatten (* Jean-François Alcover, Dec 06 2012 *)

Definition revised by T. D. Noe, Nov 30 2007

New name from David A. Corneth, Mar 26 2019

A092878 Number of initial odd numbers in class n of the iterated phi function.

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 13, 16, 24, 33, 47, 60, 94, 122, 155, 187, 266, 354, 409, 550, 734, 955, 1186, 1472, 1864, 2404, 3026, 3712, 4675, 5939, 7260, 8826, 10970, 13529, 16572, 20104, 24943, 30391, 36790, 44416, 53925, 65216, 78658, 94300, 114196, 136821

Offset: 0

T. D. Noe, Mar 10 2004, Nov 30 2007, Nov 18 2008

nonn

Class n, for n>0, contains all numbers k such that n iterations of the Euler phi function applied to k yields 2; class 0 contains only the numbers 1 and 2. There is a conjecture that the smallest number in class n is always odd. This increasing sequence supports that conjecture. As shown by Shapiro, all the initial odd numbers in class n>0 are between 2^n and 2^(n+1).

			a(2) = 2 because the sequence of eight numbers 5,7,8,9,10,12,14,18 (which all take exactly 2 iterations of the phi function to produce 2) begins with 2 odd numbers.

R. K. Guy, Unsolved Problems in Number Theory, 2nd Ed., New York, Springer-Verlag, 1994, B41.

T. D. Noe, Computing Numbers in Section I of the Totient Iteration
Harold Shapiro, An arithmetic function arising from the phi function, Amer. Math. Monthly, Vol. 50, No. 1 (1943), 18-30.

Cf. A003434 (iterations of phi(n) needed to reach 1).
Cf. A058811 (number of numbers in class n).
Cf. A135833 (number of Section I primes).

nMax=23; nn=2^nMax; c=Table[0,{nn}]; Do[c[[n]]=1+c[[EulerPhi[n]]], {n,2,nn}]; Table[Length[Select[Flatten[Position[c,n]], #<=2^n && OddQ[ # ]&]], {n,0,nMax}]

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

A058812 Irregular triangle of rows of numbers in increasing order. Row 1 = {1}. Row m + 1 contains all numbers k such that phi(k) is in row m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A092878 Number of initial odd numbers in class n of the iterated phi function.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica