A098196 -id:A098196 - cp's OEIS frontend

A007755 Smallest number m such that the trajectory of m under iteration of Euler's totient function phi(n) [A000010] contains exactly n distinct numbers, including m and the fixed point.

1, 2, 3, 5, 11, 17, 41, 83, 137, 257, 641, 1097, 2329, 4369, 10537, 17477, 35209, 65537, 140417, 281929, 557057, 1114129, 2384897, 4227137, 8978569, 16843009, 35946497, 71304257, 143163649, 286331153, 541073537, 1086374209, 2281701377, 4295098369

Offset: 1

Pepijn van Erp [ vanerp(AT)sci.kun.nl ]

Least integer k such that the number of iterations of Euler phi function needed to reach 1 starting at k (k is counted) is n.
a(n) is smallest number in the class k(n) which groups families of integers which take the same number of iterations of the totient function to evolve to 1. The maximum is 2*3^(n-1).
Shapiro shows that the smallest number is greater than 2^(n-1). Catlin shows that if a(n) is odd and composite, then its factors are among the a(k), k < n. For example a(12) = a(5) a(8). There is a conjecture that all terms of this sequence are odd. - T. D. Noe, Mar 08 2004
The indices of odd prime terms are given by n=A136040(k)+2 for k=1,2,3,.... - T. D. Noe, Dec 14 2007
Shapiro mentions on page 30 of his paper the conjecture that a(n) is prime for each n > 1, but a(13) is composite and so the conjecture fails. - Charles R Greathouse IV, Oct 28 2011

			a(3) = 3 because trajectory={3,2,1}. n=1: a(1)=1 because trajectory={1}

J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 83, p. 29, Ellipses, Paris 2008. Also Entry 137, p. 47.
R. K. Guy, Unsolved Problems in Number Theory, 2nd Ed. New York: Springer-Verlag, p. 97, 1994, Section B41.

T. D. Noe, Table of n, a(n) for n = 1..1002
P. A. Catlin, Concerning the iterated phi-function, Amer Math. Monthly 77 (1970), pp. 60-61.
T. D. Noe, Computing Numbers in Section I of the Totient Iteration
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, A003434, A049108, A092873 (prime factors of a(n)), A060611, A098196, A227946.

A060611 has the same initial terms but is a different sequence.

a007755 = (+ 1) . fromJust . (`elemIndex` a003434_list) . (subtract 1)
-- Reinhard Zumkeller, Feb 08 2013, Jul 03 2011

f[n_] := Length[ NestWhileList[ EulerPhi, n, Unequal, 2]] - 1; a = Table[0, {30}]; Do[b = f[n]; If[a[[b]] == 0, a[[b]] = n; Print[n, " = ", b]], {n, 1, 22500000}] (* Robert G. Wilson v *)

a(n) = smallest m such that A049108(m)=n.
Alternatively, a(n) = smallest m such that A003434(m)=n-1.
a(n+2) ~ 2^n.

More terms from David W. Wilson, May 15 1997

Additional comments from James S. Cronen (cronej(AT)rpi.edu)

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

A145443 In class n of the phi iteration, the number of primes less than the smallest composite number.

Original entry on oeis.org

1, 2, 2, 2, 2, 1, 3, 1, 1, 2, 0, 0, 0, 1, 0, 1, 3, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 4, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 2, 2, 1, 0, 1, 0, 2, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 2, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 1

T. D. Noe, Oct 10 2008

nonn

A number is in class n if n iterations of Euler's phi function produces 2 (see A032358). a(n)>0 for the n in A136040.

			According to A005239, class 5 begins with 41, 47, 51, 53, 55, 59, 61. There are two primes less than the composite 51. Hence a(5)=2.

T. D. Noe, Table of n, a(n) for n=1..1000
T. D. Noe, Computing Numbers in Section I of the Totient Iteration

A098196

Modified comment. - T. D. Noe, Nov 18 2008

Extension T. D. Noe, Nov 18 2008

A098197 Smallest number m such that the trajectory of m under iteration of cototient function[=A051953] contains exactly n distinct numbers (including m and the fixed point=0). Or: the required number of iterations[=operations,transitions] is n-1.

Original entry on oeis.org

0, 1, 2, 4, 6, 10, 18, 30, 42, 78, 114, 186, 294, 390, 582, 798, 1194, 1950, 2922, 4074, 5586, 7770, 11154, 15810, 22110, 30702, 42570, 53130, 68970, 105090, 159390, 206910, 278850, 361410, 462210, 688722, 1019202, 1389810, 2053770, 3011850

Offset: 1

Labos Elemer, Sep 16 2004

nonn

Analogous to A007755. Separating prime and composite least numbers is not more informative [contrary to totient-iterations] because trajectory-length=3 for all primes and except 2, all terms here are composite numbers.

			Trajectories for lengths=n=1,2,3,4 are: {0},{1,0},{2,1,0},{4,2,1,0}
n=15:{390,294,210,162,108,72,48,32,16,8,4,2,1,0}

Cf. A051953, A000010, A007755, A098196.

A309672 Composite terms of A007755.

Original entry on oeis.org

2329, 4369, 10537, 35209, 281929, 1114129, 8978569, 16843009, 143163649, 286331153, 1086374209, 4295098369, 9198250129, 18325194049, 36507844609, 73016672273, 139055899009, 277033877569, 586397253889, 1103840280833, 4673067091009, 9382516064513, 17868687216769

Offset: 1

Jeppe Stig Nielsen, Oct 05 2019

nonn

10537 is a term because it is composite (= 41*257) and the totient (A000010) iterating "trajectory" starting from 10537 and ending in 1 is longer (length 15) than any similar trajectory starting from a (prime or nonprime) N < 10537.

Cf. A000010, A003434, A049108, A007755, A098196.

cp's OEIS Frontend

A007755 Smallest number m such that the trajectory of m under iteration of Euler's totient function phi(n) [A000010] contains exactly n distinct numbers, including m and the fixed point.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

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

A145443 In class n of the phi iteration, the number of primes less than the smallest composite number.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A098197 Smallest number m such that the trajectory of m under iteration of cototient function[=A051953] contains exactly n distinct numbers (including m and the fixed point=0). Or: the required number of iterations[=operations,transitions] is n-1.

Views

Author

Keywords

Comments

Examples

Crossrefs

A309672 Composite terms of A007755.

Views

Author

Keywords

Comments

Crossrefs