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

A098196 Smallest nonprime number which if used as initial term for iteration of the A000010[x] function, results in list-to-fixed-point of length=n, or 0 if no such number exists.

Original entry on oeis.org

1, 0, 4, 8, 15, 25, 51, 85, 187, 289, 685, 1285, 2329, 4369, 10537, 18649, 35209, 66049, 150289, 281929, 598553, 1114129, 2387089, 4491589, 8978569, 16843009, 36087169, 71861329, 143163649, 286331153, 579117769, 1086374209, 2307492233

Offset: 1

Labos Elemer, Sep 13 2004

nonn

Remark: length-of-iteration means the number of distinct terms to fixed point [including start and end]. While number of iterations[=required operations] equals length-1.

The smallest composite number is the smallest product of primes in A007755 such that the phi-iteration has exactly n terms. [From T. D. Noe, Sep 18 2008]

			Iteration lists for the first 5 terms: {1},{0},{4,2,1},{8,4,2,1},{15,8,4,2,1},..

T. D. Noe, Table of n, a(n) for n=1..1002

Cf. A007755, A060611.

Corrected and extended by T. D. Noe, Sep 18 2008

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

A098196 Smallest nonprime number which if used as initial term for iteration of the A000010[x] function, results in list-to-fixed-point of length=n, or 0 if no such number exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions