A135833 -id:A135833 - cp's OEIS frontend

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.

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

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

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