A049108 -id:A049108 - cp's OEIS frontend

A060611 Smallest prime p such that n = A049108(p) = length of chain of iterates of Euler Phi starting with p.

2, 3, 5, 11, 17, 41, 83, 137, 257, 641, 1097, 2657, 5441, 10883, 17477, 40961, 65537, 140417, 295937, 557057, 1193537, 2384897, 4227137, 9548417, 17966357, 35946497, 71304257, 162174977, 305268737, 541073537, 1212153857, 2281701377

Offset: 2

Labos Elemer, Apr 13 2001

nonn

From 2nd to 12th term A007755 is the same as this sequence

			n=13: a(13)=2657 is the smallest prime which gives a chain of length 13, 2657 -> 2656 -> 1312 -> 640 -> 256 -> 128 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1, while the smallest number having this property is A007755(13) = 2329 -> 2176 -> 1024 -> 512 -> 256 -> 128 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1.

T. D. Noe, Table of n, a(n) for n=2..1002
Project Euler, Problem 214: Totient chains.
T. D. Noe, Computing Numbers in Section I of the Totient Iteration

Cf. A000010, A049108 = A003434 + 1, A007755, A049117.

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

More terms from Jud McCranie, Apr 22 2001

Removed duplicate cross references, added link, reformulated example. - M. F. Hasler, Oct 25 2008

A000010 Euler totient function phi(n): count numbers <= n and prime to n.

Original entry on oeis.org

1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16, 40, 12, 42, 20, 24, 22, 46, 16, 42, 20, 32, 24, 52, 18, 40, 24, 36, 28, 58, 16, 60, 30, 36, 32, 48, 20, 66, 32, 44

Offset: 1

N. J. A. Sloane

Number of elements in a reduced residue system modulo n.
Degree of the n-th cyclotomic polynomial (cf. A013595). - Benoit Cloitre, Oct 12 2002
Number of distinct generators of a cyclic group of order n. Number of primitive n-th roots of unity. (A primitive n-th root x is such that x^k is not equal to 1 for k = 1, 2, ..., n - 1, but x^n = 1.) - Lekraj Beedassy, Mar 31 2005
Also number of complex Dirichlet characters modulo n; Sum_{k=1..n} a(k) is asymptotic to (3/Pi^2)*n^2. - Steven Finch, Feb 16 2006
a(n) is the highest degree of irreducible polynomial dividing 1 + x + x^2 + ... + x^(n-1) = (x^n - 1)/(x - 1). - Alexander Adamchuk, Sep 02 2006, corrected Sep 27 2006
a(p) = p - 1 for prime p. a(n) is even for n > 2. For n > 2, a(n)/2 = A023022(n) = number of partitions of n into 2 ordered relatively prime parts. - Alexander Adamchuk, Jan 25 2007
Number of automorphisms of the cyclic group of order n. - Benoit Jubin, Aug 09 2008
a(n+2) equals the number of palindromic Sturmian words of length n which are "bispecial", prefix or suffix of two Sturmian words of length n + 1. - Fred Lunnon, Sep 05 2010
Suppose that a and n are coprime positive integers, then by Euler's totient theorem, any factor of n divides a^phi(n) - 1. - Lei Zhou, Feb 28 2012
If m has k prime factors, (p_1, p_2, ..., p_k), then phi(m*n) = (Product_{i=1..k} phi (p_i*n))/phi(n)^(k-1). For example, phi(42*n) = phi(2*n)*phi(3*n)*phi(7*n)/phi(n)^2. - Gary Detlefs, Apr 21 2012
Sum_{n>=1} a(n)/n! = 1.954085357876006213144... This sum is referenced in Plouffe's inverter. - Alexander R. Povolotsky, Feb 02 2013 (see A336334. - Hugo Pfoertner, Jul 22 2020)
The order of the multiplicative group of units modulo n. - Michael Somos, Aug 27 2013
A strong divisibility sequence, that is, gcd(a(n), a(m)) = a(gcd(n, m)) for all positive integers n and m. - Michael Somos, Dec 30 2016
From Eric Desbiaux, Jan 01 2017: (Start)
a(n) equals the Ramanujan sum c_n(n) (last term on n-th row of triangle A054533).
a(n) equals the Jordan function J_1(n) (cf. A007434, A059376, A059377, which are the Jordan functions J_2, J_3, J_4, respectively). (End)
For n > 1, a(n) appears to be equal to the number of semi-meander solutions for n with top arches containing exactly 2 mountain ranges and exactly 2 arches of length 1. - Roger Ford, Oct 11 2017
a(n) is the minimum dimension of a lattice able to generate, via cut-and-project, the quasilattice whose diffraction pattern features n-fold rotational symmetry. The case n=15 is the first n > 1 in which the following simpler definition fails: "a(n) is the minimum dimension of a lattice with n-fold rotational symmetry". - Felix Flicker, Nov 08 2017
Number of cyclic Latin squares of order n with the first row in ascending order. - Eduard I. Vatutin, Nov 01 2020
a(n) is the number of rational numbers p/q >= 0 (in lowest terms) such that p + q = n. - Rémy Sigrist, Jan 17 2021
From Richard L. Ollerton, May 08 2021: (Start)
Formulas for the numerous OEIS entries involving Dirichlet convolution of a(n) and some sequence h(n) can be derived using the following (n >= 1):
Sum_{d|n} phi(d)*h(n/d) = Sum_{k=1..n} h(gcd(n,k)) [see P. H. van der Kamp link] = Sum_{d|n} h(d)*phi(n/d) = Sum_{k=1..n} h(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). Similarly,
Sum_{d|n} phi(d)*h(d) = Sum_{k=1..n} h(n/gcd(n,k)) = Sum_{k=1..n} h(gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)).
More generally,
Sum_{d|n} h(d) = Sum_{k=1..n} h(gcd(n,k))/phi(n/gcd(n,k)) = Sum_{k=1..n} h(n/gcd(n,k))/phi(n/gcd(n,k)).
In particular, for sequences involving the Möbius transform:
Sum_{d|n} mu(d)*h(n/d) = Sum_{k=1..n} h(gcd(n,k))*mu(n/gcd(n,k))/phi(n/gcd(n,k)) = Sum_{k=1..n} h(n/gcd(n,k))*mu(gcd(n,k))/phi(n/gcd(n,k)), where mu = A008683.
Use of gcd(n,k)*lcm(n,k) = n*k and phi(gcd(n,k))*phi(lcm(n,k)) = phi(n)*phi(k) provide further variations. (End)
From Richard L. Ollerton, Nov 07 2021: (Start)
Formulas for products corresponding to the sums above may found using the substitution h(n) = log(f(n)) where f(n) > 0 (for example, cf. formulas for the sum A018804 and product A067911 of gcd(n,k)):
Product_{d|n} f(n/d)^phi(d) = Product_{k=1..n} f(gcd(n,k)) = Product_{d|n} f(d)^phi(n/d) = Product_{k=1..n} f(n/gcd(n,k))^(phi(gcd(n,k))/phi(n/gcd(n,k))),
Product_{d|n} f(d)^phi(d) = Product_{k=1..n} f(n/gcd(n,k)) = Product_{k=1..n} f(gcd(n,k))^(phi(gcd(n,k))/phi(n/gcd(n,k))),
Product_{d|n} f(d) = Product_{k=1..n} f(gcd(n,k))^(1/phi(n/gcd(n,k))) = Product_{k=1..n} f(n/gcd(n,k))^(1/phi(n/gcd(n,k))),
Product_{d|n} f(n/d)^mu(d) = Product_{k=1..n} f(gcd(n,k))^(mu(n/gcd(n,k))/phi(n/gcd(n,k))) = Product_{k=1..n} f(n/gcd(n,k))^(mu(gcd(n,k))/phi(n/gcd(n,k))), where mu = A008683. (End)
a(n+1) is the number of binary words with exactly n distinct subsequences (when n > 0). - Radoslaw Zak, Nov 29 2021

			G.f. = x + x^2 + 2*x^3 + 2*x^4 + 4*x^5 + 2*x^6 + 6*x^7 + 4*x^8 + 6*x^9 + 4*x^10 + ...
a(8) = 4 with {1, 3, 5, 7} units modulo 8. a(10) = 4 with {1, 3, 7, 9} units modulo 10. - _Michael Somos_, Aug 27 2013
From _Eduard I. Vatutin_, Nov 01 2020: (Start)
The a(5)=4 cyclic Latin squares with the first row in ascending order are:
  0 1 2 3 4   0 1 2 3 4   0 1 2 3 4   0 1 2 3 4
  1 2 3 4 0   2 3 4 0 1   3 4 0 1 2   4 0 1 2 3
  2 3 4 0 1   4 0 1 2 3   1 2 3 4 0   3 4 0 1 2
  3 4 0 1 2   1 2 3 4 0   4 0 1 2 3   2 3 4 0 1
  4 0 1 2 3   3 4 0 1 2   2 3 4 0 1   1 2 3 4 0
(End)

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 840.
T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 24.
M. Baake and U. Grimm, Aperiodic Order Vol. 1: A Mathematical Invitation, Encyclopedia of Mathematics and its Applications 149, Cambridge University Press, 2013: see Tables 3.1 and 3.2.
Florian Cajori, A History of Mathematical Notations, Dover edition (2012), par. 409.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 193.
John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See pp. 154-156.
C. W. Curtis, Pioneers of Representation Theory ..., Amer. Math. Soc., 1999; see p. 3.
J.-M. De Koninck & A. Mercier, 1001 Problèmes en Théorie Classique des Nombres, Ellipses, Paris, 2004, Problème 529, pp. 71-257.
L. E. Dickson, History of the Theory of Numbers. Carnegie Institute Public. 256, Washington, DC, Vol. 1, 1919; Vol. 2, 1920; Vol. 3, 1923, see vol. 1, Chapter V.
S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 115-119.
Carl Friedrich Gauss, "Disquisitiones Arithmeticae", Yale University Press, 1965; see p. 21.
Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Math., 2n-d ed.; Addison-Wesley, 1994, p. 137.
R. K. Guy, Unsolved Problems in Number Theory, Springer, 1st edition, 1981. See section B36.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, th. 60, 62, 63, 288, 323, 328, 330.
Peter Hilton and Jean Pedersen, A Mathematical Tapestry, Demonstrating the Beautiful Unity of Mathematics, Cambridge University Press, pages 261-264, the Coach theorem.
Jean-Marie Monier, Analyse, Exercices corrigés, 2ème année MP, Dunod, 1997, Exercice 3.2.21 pp. 281-294.
G. Pólya and G. Szegő, Problems and Theorems in Analysis, Springer-Verlag, New York, Heidelberg, Berlin, 2 vols., 1976, Vol. II, problem 71, p. 126.
Paulo Ribenboim, The New Book of Prime Number Records.
Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See pp. 28-33.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, pages 162-167.

Daniel Forgues, Table of n, phi(n) for n = 1..100000 (first 10000 terms from N. J. A. Sloane)
Milton Abramowitz and Irene A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, Tenth Printing, 1972.
Dario A. Alpern, Factorization using the Elliptic Curve Method (along with sigma_0, sigma_1 and phi functions)
Joerg Arndt, Matters Computational (The Fxtbook), section 39.7, pp. 776-778.
F. Bayart, Indicateur d'Euler (in French).
Alexander Bogomolny, Euler Function and Theorem.
Chris K. Caldwell, The Prime Glossary, Euler's phi function
Robert D. Carmichael, A table of the values of m corresponding to given values of phi(m), Amer. J. Math., 30 (1908), 394-400. [Annotated scanned copy]
Paul Erdős, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204.
Paul Erdős, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204. [Annotated copy with A-numbers]
Kevin Ford, The number of solutions of phi(x)=m, arXiv:math/9907204 [math.NT], 1999.
Kevin Ford, Florian Luca and Pieter Moree, Values of the Euler phi-function not divisible by a given odd prime, and the distribution of Euler-Kronecker constants for cyclotomic fields, arXiv:1108.3805 [math.NT], 2011.
H. Fripertinger, The Euler phi function.
Daniele A. Gewurz and Francesca Merola, Sequences realized as Parker vectors of oligomorphic permutation groups, J. Integer Seqs., Vol. 6, 2003.
E. Pérez Herrero, Totient Carnival partitions, Psychedelic Geometry Blogspot.
Peter H. van der Kamp, On the Fourier transform of the greatest common divisor, arXiv:1201.3139 [math.NT]
M. Lal and P. Gillard, Table of Euler's phi function, n < 10^5, Math. Comp., 23 (1969), 682-683.
Derrick N. Lehmer, Review of Dickson's History of the Theory of Numbers, Bull. Amer. Math. Soc., 26 (1919), 125-132.
Peter Luschny, Sequences related to Euler's totient function.
R. J. Mathar, Graphical representation among sequences closely related to this one (cf. N. J. A. Sloane, "Families of Essentially Identical Sequences").
Mathematics Stack Exchange, Is the Euler phi function bounded below? (2013).
Mathforum, Proving phi(m) Is Even.
Keith Matthews, Factorizing n and calculating phi(n), omega(n), d(n), sigma(n) and mu(n).
Graeme McRae, Euler's Totient Function.
François Nicolas, A simple, polynomial-time algorithm for the matrix torsion problem, arXiv:0806.2068 [cs.DM], 2009.
Matthew Parker, The first 5 million terms (7-Zip compressed file).
Carl Pomerance and Hee-Sung Yang, Variant of a theorem of Erdős on the sum-of-proper-divisors function, Math. Comp., to appear (2014).
Primefan, Euler's Totient Function Values For n=1 to 500, with Divisor Lists.
Marko Riedel, Combinatorics and number theory page.
J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), no. 1, 64-94.
K. Schneider, Euler phi-function, PlanetMath.org.
Wacław F. Sierpiński, Euler's Totient Function And The Theorem Of Euler.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, p. 14.
Ulrich Sondermann, Euler's Totient Function.
William A. Stein, Phi is a Multiplicative Function
Pinthira Tangsupphathawat, Takao Komatsu and Vichian Laohakosol, Minimal Polynomials of Algebraic Cosine Values, II, J. Int. Seq., Vol. 21 (2018), Article 18.9.5.
László Tóth, Multiplicative arithmetic functions of several variables: a survey, arXiv preprint arXiv:1310.7053 [math.NT], 2013.
G. Villemin, Totient d'Euler.
K. W. Wegner, Values of phi(x) = n for n from 2 through 1978, mimeographed manuscript, no date. [Annotated scanned copy]
Eric Weisstein's World of Mathematics, Modulo Multiplication Group.
Eric Weisstein's World of Mathematics, Moebius Transform.
Eric Weisstein's World of Mathematics, Totient Function.
Wikipedia, Euler's totient function.
Wikipedia, Multiplicative group of integers modulo n.
Wikipedia, Ramanujan's sum
Wolfram Research, First 50 values of phi(n).
Gang Xiao, Numerical Calculator, To display phi(n) operate on "eulerphi(n)".
Index entries for "core" sequences
Index to divisibility sequences

Cf. A002088 (partial sums), A008683, A003434 (steps to reach 1), A007755, A049108, A002202 (values), A011755 (Sum k*phi(k)).
Cf. also A005277 (nontotient numbers). For inverse see A002181, A006511, A058277.
Jordan function J_k(n) is a generalization - see A059379 and A059380 (triangle of values of J_k(n)), this sequence (J_1), A007434 (J_2), A059376 (J_3), A059377 (J_4), A059378 (J_5).
Cf. A054521, A023022, A054525.
Row sums of triangles A134540, A127448, A143239, A143353 and A143276.
Equals right and left borders of triangle A159937. - Gary W. Adamson, Apr 26 2009
Values for prime powers p^e: A006093 (e=1), A036689 (e=2), A135177 (e=3), A138403 (e=4), A138407 (e=5), A138412 (e=6).
Values for perfect powers n^e: A002618 (e=2), A053191 (e=3), A189393 (e=4), A238533 (e=5), A306411 (e=6), A239442 (e=7), A306412 (e=8), A239443 (e=9).
Cf. A003558, A135303.
Cf. A152455, A080737.
Cf. A076479.
Cf. A023900 (Dirichlet inverse of phi), A306633 (Dgf at s=3).

Axiom
```
[eulerPhi(n) for n in 1..100]
```

a n = length (filter (==1) (map (gcd n) [1..n])) -- Allan C. Wechsler, Dec 29 2014

# Computes the first N terms of the sequence.
function A000010List(N)
    phi = [i for i in 1:N + 1]
    for i in 2:N + 1
        if phi[i] == i
            for j in i:i:N + 1
                phi[j] -= div(phi[j], i)
    end end end
return phi end
println(A000010List(68))  # Peter Luschny, Sep 03 2023

[ EulerPhi(n) : n in [1..100] ]; // Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006

with(numtheory): A000010 := phi; [ seq(phi(n), n=1..100) ]; # version 1
with(numtheory): phi := proc(n) local i,t1,t2; t1 := ifactors(n)[2]; t2 := n*mul((1-1/t1[i][1]),i=1..nops(t1)); end; # version 2
# Alternative without library function:
A000010List := proc(N) local i, j, phi;
    phi := Array([seq(i, i = 1 .. N+1)]);
    for i from 2 to N + 1 do
        if phi[i] = i then
            for j from i by i to N + 1 do
                phi[j] := phi[j] - iquo(phi[j], i) od
        fi od;
return phi end:
A000010List(68);  # Peter Luschny, Sep 03 2023

Mathematica
```
Array[EulerPhi, 70]
```

makelist(totient(n),n,0,1000); /* Emanuele Munarini, Mar 26 2011 */

{a(n) = if( n==0, 0, eulerphi(n))}; /* Michael Somos, Feb 05 2011 */

from sympy.ntheory import totient
print([totient(i) for i in range(1, 70)])  # Indranil Ghosh, Mar 17 2017

# Note also the implementation in A365339.

def A000010(n): return euler_phi(n) # Jaap Spies, Jan 07 2007

[euler_phi(n) for n in range(1, 70)]  # Zerinvary Lajos, Jun 06 2009

phi(n) = n*Product_{distinct primes p dividing n} (1 - 1/p).
Sum_{d divides n} phi(d) = n.
phi(n) = Sum_{d divides n} mu(d)*n/d, i.e., the Moebius transform of the natural numbers; mu() = Moebius function A008683().
Dirichlet generating function Sum_{n>=1} phi(n)/n^s = zeta(s-1)/zeta(s). Also Sum_{n >= 1} phi(n)*x^n/(1 - x^n) = x/(1 - x)^2.
Multiplicative with a(p^e) = (p - 1)*p^(e-1). - David W. Wilson, Aug 01 2001
Sum_{n>=1} (phi(n)*log(1 - x^n)/n) = -x/(1 - x) for -1 < x < 1 (cf. A002088) - Henry Bottomley, Nov 16 2001
a(n) = binomial(n+1, 2) - Sum_{i=1..n-1} a(i)*floor(n/i) (see A000217 for inverse). - Jon Perry, Mar 02 2004
It is a classical result (certainly known to Landau, 1909) that lim inf n/phi(n) = 1 (taking n to be primes), lim sup n/(phi(n)*log(log(n))) = e^gamma, with gamma = Euler's constant (taking n to be products of consecutive primes starting from 2 and applying Mertens' theorem). See e.g. Ribenboim, pp. 319-320. - Pieter Moree, Sep 10 2004
a(n) = Sum_{i=1..n} |k(n, i)| where k(n, i) is the Kronecker symbol. Also a(n) = n - #{1 <= i <= n : k(n, i) = 0}. - Benoit Cloitre, Aug 06 2004 [Corrected by Jianing Song, Sep 25 2018]
Conjecture: Sum_{i>=2} (-1)^i/(i*phi(i)) exists and is approximately 0.558 (A335319). - Orges Leka (oleka(AT)students.uni-mainz.de), Dec 23 2004
From Enrique Pérez Herrero, Sep 07 2010: (Start)
a(n) = Sum_{i=1..n} floor(sigma_k(i*n)/sigma_k(i)*sigma_k(n)), where sigma_2 is A001157.
a(n) = Sum_{i=1..n} floor(tau_k(i*n)/tau_k(i)*tau_k(n)), where tau_3 is A007425.
a(n) = Sum_{i=1..n} floor(rad(i*n)/rad(i)*rad(n)), where rad is A007947. (End)
a(n) = A173557(n)*A003557(n). - R. J. Mathar, Mar 30 2011
a(n) = A096396(n) + A096397(n). - Reinhard Zumkeller, Mar 24 2012
phi(p*n) = phi(n)*(floor(((n + p - 1) mod p)/(p - 1)) + p - 1), for primes p. - Gary Detlefs, Apr 21 2012
For odd n, a(n) = 2*A135303((n-1)/2)*A003558((n-1)/2) or phi(n) = 2*c*k; the Coach theorem of Pedersen et al. Cf. A135303. - Gary W. Adamson, Aug 15 2012
G.f.: Sum_{n>=1} mu(n)*x^n/(1 - x^n)^2, where mu(n) = A008683(n). - Mamuka Jibladze, Apr 05 2015
a(n) = n - cototient(n) = n - A051953(n). - Omar E. Pol, May 14 2016
a(n) = lim_{s->1} n*zeta(s)*(Sum_{d divides n} A008683(d)/(e^(1/d))^(s-1)), for n > 1. - Mats Granvik, Jan 26 2017
Conjecture: a(n) = Sum_{a=1..n} Sum_{b=1..n} Sum_{c=1..n} 1 for n > 1. The sum is over a,b,c such that n*c - a*b = 1. - Benedict W. J. Irwin, Apr 03 2017
a(n) = Sum_{j=1..n} gcd(j, n) cos(2*Pi*j/n) = Sum_{j=1..n} gcd(j, n) exp(2*Pi*i*j/n) where i is the imaginary unit. Notice that the Ramanujan's sum c_n(k) := Sum_{j=1..n, gcd(j, n) = 1} exp(2*Pi*i*j*k/n) gives a(n) = Sum_{k|n} k*c_(n/k)(1) = Sum_{k|n} k*mu(n/k). - Michael Somos, May 13 2018
G.f.: x*d/dx(x*d/dx(log(Product_{k>=1} (1 - x^k)^(-mu(k)/k^2)))), where mu(n) = A008683(n). - Mamuka Jibladze, Sep 20 2018
a(n) = Sum_{d|n} A007431(d). - Steven Foster Clark, May 29 2019
G.f. A(x) satisfies: A(x) = x/(1 - x)^2 - Sum_{k>=2} A(x^k). - Ilya Gutkovskiy, Sep 06 2019
a(n) >= sqrt(n/2) (Nicolas). - Hugo Pfoertner, Jun 01 2020
a(n) > n/(exp(gamma)*log(log(n)) + 5/(2*log(log(n)))), except for n=223092870 (Rosser, Schoenfeld). - Hugo Pfoertner, Jun 02 2020
From Bernard Schott, Nov 28 2020: (Start)
Sum_{m=1..n} 1/a(m) = A028415(n)/A048049(n) -> oo when n->oo.
Sum_{n >= 1} 1/a(n)^2 = A109695.
Sum_{n >= 1} 1/a(n)^3 = A335818.
Sum_{n >= 1} 1/a(n)^k is convergent iff k > 1.
a(2n) = a(n) iff n is odd, and, a(2n) > a(n) iff n is even. (End) [Actually, a(2n) = 2*a(n) for even n. - Jianing Song, Sep 18 2022]
a(n) = 2*A023896(n)/n, n > 1. - Richard R. Forberg, Feb 03 2021
From Richard L. Ollerton, May 09 2021: (Start)
For n > 1, Sum_{k=1..n} phi^{(-1)}(n/gcd(n,k))*a(gcd(n,k))/a(n/gcd(n,k)) = 0, where phi^{(-1)} = A023900.
For n > 1, Sum_{k=1..n} a(gcd(n,k))*mu(rad(gcd(n,k)))*rad(gcd(n,k))/gcd(n,k) = 0.
For n > 1, Sum_{k=1..n} a(gcd(n,k))*mu(rad(n/gcd(n,k)))*rad(n/gcd(n,k))*gcd(n,k) = 0.
Sum_{k=1..n} a(gcd(n,k))/a(n/gcd(n,k)) = n. (End)
a(n) = Sum_{d|n, e|n} gcd(d, e)*mobius(n/d)*mobius(n/e) (the sum is a multiplicative function of n by Tóth, and takes the value p^e - p^(e-1) for n = p^e, a prime power). - Peter Bala, Jan 22 2024
Sum_{n >= 1} phi(n)*x^n/(1 + x^n) = x + 3*x^3 + 5*x^5 + 7*x^7 + ... = Sum_{n >= 1} phi(2*n-1)*x^(2*n-1)/(1 - x^(4*n-2)). For the first equality see Pólya and Szegő, problem 71, p. 126. - Peter Bala, Feb 29 2024
Conjecture: a(n) = lim_{k->oo} (n^(k + 1))/A000203(n^k). - Velin Yanev, Dec 04 2024 [A000010(p) = p-1, A000203(p^k) = (p^(k+1)-1)/(p-1), so the conjecture is true if n is prime. - Vaclav Kotesovec, Dec 19 2024]

A003434 Number of iterations of phi(x) at n needed to reach 1.

Original entry on oeis.org

0, 1, 2, 2, 3, 2, 3, 3, 3, 3, 4, 3, 4, 3, 4, 4, 5, 3, 4, 4, 4, 4, 5, 4, 5, 4, 4, 4, 5, 4, 5, 5, 5, 5, 5, 4, 5, 4, 5, 5, 6, 4, 5, 5, 5, 5, 6, 5, 5, 5, 6, 5, 6, 4, 6, 5, 5, 5, 6, 5, 6, 5, 5, 6, 6, 5, 6, 6, 6, 5, 6, 5, 6, 5, 6, 5, 6, 5, 6, 6, 5, 6, 7, 5, 7, 5, 6, 6, 7, 5, 6, 6, 6, 6, 6, 6, 7, 5, 6, 6, 7, 6, 7, 6, 6

Offset: 1

N. J. A. Sloane

Each number n>1 occurs for the first time at the position A007755(n+1) and for the last time at 2*3^(n-1). - Ivan Neretin, Mar 24 2015

			If n=164 the trajectory is {164,80,32,16,8,4,2,1}. Its length is 8, thus a(164)=7.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
M. V. Subbarao, On a function connected with phi(n), J. Madras Univ. B. 27 (1957), pp. 327-333.

T. D. Noe, Table of n, a(n) for n = 1..10000
Hartosh Singh Bal, Gaurav Bhatnagar, Prime number conjectures from the Shapiro class structure, arXiv:1903.09619 [math.NT], 2019.
C. Defant, On Arithmetic Functions Related to Iterates of the Schemmel Totient Functions, J. Int. Seq. 18 (2015) # 15.2.1.
Paul Erdős, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204.
Paul Erdős, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204. [Annotated copy with A-numbers]
I. Niven, The iteration of certain arithmetic functions, Canad. J. Math. 2 (1950), pp. 406-408.
H. N. Shapiro, On the iterates of a certain class of arithmetic functions, Comm. Pure Appl. Math. 3 (1950), pp. 259-272.
S. Sivasankaranarayana Pillai, On a function connected with phi(n), Bull. Amer. Math. Soc., 35:6 (1929), pp. 837-841.
S. Sivasankaranarayana Pillai, On a function connected with phi(n), Bull. Amer. Math. Soc., 35.6 (1929), 837-841. (Annotated scanned copy)

Cf. A000010, A007755.

a003434 n = fst $ until ((== 1) . snd)
                        (\(i, x) -> (i + 1, a000010 x)) (0, n)
-- Reinhard Zumkeller, Feb 08 2013, Jul 03 2011

A003434 := proc(n)
    local a, e;
    e := n ;
    a :=0 ;
    while e > 1 do
        a := a+1 ;
        e := numtheory[phi](e) ;
    end do:
    a;
end proc:
seq(A003434(n),n=1..40) ; # R. J. Mathar, Jan 09 2017

f[n_] := Length@ NestWhileList[ EulerPhi, n, # != 1 &] - 1; Array[f, 105] (* Robert G. Wilson v, Feb 07 2012 *)

A003434(n)=for(k=0,n, n>1 || return(k);n=eulerphi(n)) /* Works because the loop limits are evaluated only once. Using while(...) takes 50% more time. */ \\ M. F. Hasler, Jul 01 2009

from sympy import totient
def A003434(n):
    c, m = 0, n
    while m > 1:
        c += 1
        m = totient(m)
    return c # Chai Wah Wu, Nov 14 2021

a(n) = A049108(n) - 1.
By the definition of a(n) we have for n >= 2 the recursion a(n) = a(phi(n)) + 1. - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 20 2001
Pillai proved that log(n/2)/log(3) + 1 <= a(n) <= log(n)/log(2) + 1. - Charles R Greathouse IV, Mar 22 2012

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.

Original entry on oeis.org

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)

A053475 1 + the number of iterations of A051953 (Euler-cototient) function needed to reach 0, starting at n.

Original entry on oeis.org

2, 3, 3, 4, 3, 5, 3, 5, 4, 6, 3, 6, 3, 6, 4, 6, 3, 7, 3, 7, 5, 7, 3, 7, 4, 7, 5, 7, 3, 8, 3, 7, 4, 8, 4, 8, 3, 8, 5, 8, 3, 9, 3, 8, 6, 8, 3, 8, 4, 9, 4, 8, 3, 9, 5, 8, 6, 9, 3, 9, 3, 8, 6, 8, 4, 9, 3, 9, 5, 9, 3, 9, 3, 9, 5, 9, 4, 10, 3, 9, 6, 10, 3, 10, 6, 9, 4, 9, 3, 10, 4, 9, 5, 9, 4, 9, 3, 9, 6, 10, 3, 10

Offset: 1

Labos Elemer, Jan 14 2000

nonn

Analogous sequences of iteration-lengths for A000005 or A000010 are A036459 and A049108 resp. The length values of 3 occur if the initial value is prime resulting in {p,1,0} iterations.

			Starting with n=18, the iterations of A051953 are as follows: {18,12,8,4,2,1,0}. The length of this sequence is 7, so a(18) = 7. The function is applied a(n)-1 times.

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

Cf. A000005, A000010, A051953, A036459, A049108, A076640.

Table[Length@ NestWhileList[# - EulerPhi@ # &, n, # > 0 &], {n, 84}] (* Michael De Vlieger, Jul 04 2016 *)

a(n) = A076640(n) + 1. - Michael De Vlieger, Jul 04 2016

A032358 Number of iterations of phi(n) needed to reach 2.

Original entry on oeis.org

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

Offset: 2

Ursula Gagelmann (gagelmann(AT)altavista.net)

This sequence is additive (but not completely additive). [Charles R Greathouse IV, Oct 28 2011]
Shapiro asks for a proof that for every n > 1 there is a prime p such that a(p) = n. [Charles R Greathouse IV, Oct 28 2011]
This is A003434(n)-1 for n>1. - N. J. A. Sloane, Sep 02 2017

Reinhard Zumkeller, Table of n, a(n) for n = 2..10000
P. A. Catlin, Concerning the iterated phi-function, Amer Math. Monthly 77 (1970), pp. 60-61.
Paul Erdős, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204.
Paul Erdos, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204. [Annotated copy with A-numbers]
T. D. Noe, Primes in classes of the iterated totient function, JIS 11 (2008) 08.1.2, sequence C(x).
Harold Shapiro, An arithmetic function arising from the phi function, Amer. Math. Monthly, Vol. 50, No. 1 (1943), 18-30.

Cf. A000010, A003434.

a032358 = length . takeWhile (/= 2) . (iterate a000010)
-- Reinhard Zumkeller, Oct 27 2011

A032358 := proc(n)
    local a,phin ;
    if n <=2 then
        0;
    else
        phin := n ;
        a := 0 ;
        for a from 1 do
            phin := numtheory[phi](phin) ;
            if phin = 2 then
                return a;
            end if;
        end do:
    end if;
end proc:
seq(A032358(n),n=1..30) ; # R. J. Mathar, Aug 28 2015

Table[Length[NestWhileList[EulerPhi[#]&,n,#>2&]]-1,{n,3,80}] (* Harvey P. Dale, May 01 2011 *)

a(n)=my(t);while(n>2,n=eulerphi(n);t++);t \\ Charles R Greathouse IV, Oct 28 2011

a(n) = a(phi(n))+1, a(1) = -1. - Vladeta Jovovic, Apr 29 2003
a(n) = A003434(n) - 1 = A049108(n) - 2.
From Charles R Greathouse IV, Oct 28 2011:  (Start)
Shapiro proves that log_3(n/2) <= a(n) < log_2(n) and also
a(mn) = a(m) + a(n) if either m or n is odd and a(mn) = a(m) + a(n) + 1 if m and n are even.
(End)

a(2) = 0 added and offset adjusted, suggested by David W. Wilson

A053478 Sum of iterates when phi, A000010, is iterated until fixed point 1.

Original entry on oeis.org

1, 3, 6, 7, 12, 9, 16, 15, 18, 17, 28, 19, 32, 23, 30, 31, 48, 27, 46, 35, 40, 39, 62, 39, 60, 45, 54, 47, 76, 45, 76, 63, 68, 65, 74, 55, 92, 65, 78, 71, 112, 61, 104, 79, 84, 85, 132, 79, 110, 85, 114, 91, 144, 81, 126, 95, 112, 105, 164, 91, 152, 107, 118, 127, 144, 101

Offset: 1

Labos Elemer, Jan 14 2000

nonn

For n = 2^w, the sum is 2^(w+1) - 1.

			If phi is applied repeatedly to n = 91, the iterates {91, 72, 24, 8, 4, 2, 1} are obtained. Their sum is a(91) = 91 + 72 + 24 + 8 + 4 + 2 + 1 = 202.

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

Cf. A000010, A010554, A049099, A049100, A049107, A049108, A032358.

Row sums of A375478.

a053478 = (+ 1) . sum . takeWhile (/= 1) . iterate a000010
-- Reinhard Zumkeller, Oct 27 2011

f[n_] := Plus @@ Drop[ FixedPointList[ EulerPhi, n], -1]; Table[ f[n], {n, 66}] (* Robert G. Wilson v, Dec 16 2004 *)
f[1] := 1; f[n_] := n + f[EulerPhi[n]]; Table[f[n], {n, 66}] (* Carlos Eduardo Olivieri, May 26 2015 *)

a(n)=my(s=n);while(n>1,s+=n=eulerphi(n)); s \\ Charles R Greathouse IV, Feb 21 2013

a(n) = n + a(phi(n)).

a(n) = A092693(n) + n. - Vladeta Jovovic, Jul 02 2004

A060937 Number of iterations of d(n) (A000005) needed to reach 2 starting at n (n is counted).

Original entry on oeis.org

1, 2, 3, 2, 4, 2, 4, 3, 4, 2, 5, 2, 4, 4, 3, 2, 5, 2, 5, 4, 4, 2, 5, 3, 4, 4, 5, 2, 5, 2, 5, 4, 4, 4, 4, 2, 4, 4, 5, 2, 5, 2, 5, 5, 4, 2, 5, 3, 5, 4, 5, 2, 5, 4, 5, 4, 4, 2, 6, 2, 4, 5, 3, 4, 5, 2, 5, 4, 5, 2, 6, 2, 4, 5, 5, 4, 5, 2, 5, 3, 4, 2, 6, 4, 4, 4, 5, 2, 6, 4, 5, 4, 4, 4, 6, 2, 5, 5, 4, 2, 5, 2, 5, 5, 4

Offset: 2

Ahmed Fares (ahmedfares(AT)my-deja.com), May 06 2001

nonn

By the definition of a(n) we have for n >= 3 the recursion a(n) = a(d(n)) + 1. a(n) = 2 iff n is an odd prime.

			If n=12 the trajectory is {12,6,4,3,2}. Its length is 5, thus a(12)=5.

József Sándor, Dragoslav S. Mitrinovic, Borislav Crstici, Handbook of Number Theory I, Springer Science & Business Media, 2005, chapter 2, page 66.

Charles R Greathouse IV, Table of n, a(n) for n = 2..10000
Paul Erdős and Imre Kátai, On the growth of d_k(n), Fibonacci Quarterly, Vol. 7, No. 3 (1969), pp. 267-274.

Equals A036459 + 1.

Cf. A000005, A049108, A003434.

with(numtheory): interface(quiet=true): for n from 2 to 200 do if (1=1) then temp := n: count := 1: end if; while (temp > 2) do temp := tau(temp): count := count + 1: od; printf("%d,", count); od;

a[n_] := -1 + Length @ FixedPointList[DivisorSigma[0, #] &, n]; Array[a, 100, 2] (* Amiram Eldar, Jul 10 2021 *)

a(n)=my(t=1);while(n>2,n=numdiv(n);t++);t \\ Charles R Greathouse IV, Apr 07 2012

0 < lim sup_{n->oo} (a(n)-1)/log(log(log(n))) < oo (Erdős and Kátai, 1969). - Amiram Eldar, Jul 10 2021

More terms from Winston C. Yang (winston(AT)cs.wisc.edu), May 21 2001

A049113 Number of powers of 2 in sequence obtained when phi (A000010) is repeatedly applied to n.

Original entry on oeis.org

1, 2, 2, 3, 3, 2, 2, 4, 2, 3, 3, 3, 3, 2, 4, 5, 5, 2, 2, 4, 3, 3, 3, 4, 4, 3, 2, 3, 3, 4, 4, 6, 4, 5, 4, 3, 3, 2, 4, 5, 5, 3, 3, 4, 4, 3, 3, 5, 3, 4, 6, 4, 4, 2, 5, 4, 3, 3, 3, 5, 5, 4, 3, 7, 5, 4, 4, 6, 4, 4, 4, 4, 4, 3, 5, 3, 5, 4, 4, 6, 2, 5, 5, 4, 7, 3, 4, 5, 5, 4, 4, 4, 5, 3, 4, 6, 6, 3, 5, 5, 5, 6, 6, 5, 5

Offset: 1

Labos Elemer

nonn

			If n = 164, the "iterated phi-sequence" for n is {164,80,32,16,8,4,2,1}. It includes 6 powers of 2 at the end, so a(164) = 6.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000010, A049115, A049108.

A049113 := proc(n)
    local a, e;
    e := n ;
    a :=0 ;
    while e > 1 do
        if isA000079(e) then
            a := a+1 ;
        end if;
        e := numtheory[phi](e) ;
    end do:
    1+a;
end proc:
seq(A049113(n),n=1..40) ; # R. J. Mathar, Jan 09 2017

pwrs2 = NestList[2#&, 1, 15];
Table[Length[Intersection[NestWhileList[EulerPhi[#]&, i, # > 1 &], pwrs2]], {i, 100}] (* Harvey P. Dale, Dec 12 2010 *)

a(n)=while(n!=1<Charles R Greathouse IV, Feb 21 2013

a(n) = A049108(n)-A049115(n). - R. J. Mathar, Sep 08 2021

A375478 Irregular triangle read by rows in which row n lists the iterates of the phi(x) map from n to 1, where phi(x) is Euler's totient function (A000010).

Original entry on oeis.org

1, 2, 1, 3, 2, 1, 4, 2, 1, 5, 4, 2, 1, 6, 2, 1, 7, 6, 2, 1, 8, 4, 2, 1, 9, 6, 2, 1, 10, 4, 2, 1, 11, 10, 4, 2, 1, 12, 4, 2, 1, 13, 12, 4, 2, 1, 14, 6, 2, 1, 15, 8, 4, 2, 1, 16, 8, 4, 2, 1, 17, 16, 8, 4, 2, 1, 18, 6, 2, 1, 19, 18, 6, 2, 1, 20, 8, 4, 2, 1, 21, 12, 4, 2, 1

Offset: 1

Paolo Xausa, Aug 17 2024

First differs from A246700 at n = 22.

			Triangle begins:
   1;
   2, 1;
   3, 2, 1;
   4, 2, 1;
   5, 4, 2, 1;
   6, 2, 1;
   7, 6, 2, 1;
   8, 4, 2, 1;
   9, 6, 2, 1;
  10, 4, 2, 1;
  ...

Paolo Xausa, Table of n, a(n) for n = 1..10636 (rows 1..1200 of the triangle, flattened).
Index entries for sequences related to totient function phi(n).

Supersequence of A246700.

Cf. A000010, A049108 (row lengths), A053478 (row sums).

Array[Most[FixedPointList[EulerPhi, #]] &, 25]

T(n,1) = n; T(n,k) = A000010(T(n,k-1)), for k = 2..A049108(n).

cp's OEIS Frontend

A060611 Smallest prime p such that n = A049108(p) = length of chain of iterates of Euler Phi starting with p.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A000010 Euler totient function phi(n): count numbers <= n and prime to n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Axiom

Haskell

Julia

Magma

Maple

Mathematica

Maxima

PARI

Python

Python

Sage

Sage

Formula

A003434 Number of iterations of phi(x) at n needed to reach 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

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

A053475 1 + the number of iterations of A051953 (Euler-cototient) function needed to reach 0, starting at n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A032358 Number of iterations of phi(n) needed to reach 2.

Views

Author

Keywords

Comments

Links