A061091 Number of k with 1 <= k <= n relatively prime to phi(k).

1, 2, 3, 3, 4, 4, 5, 5, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 16, 16, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19, 20, 20, 21, 21, 21, 21, 21, 21, 22, 22, 23, 23, 23, 23, 24, 24, 25, 25, 26, 26, 27, 27, 28, 28, 28

Offset: 1

Author

Frank Ellermann, May 29 2001

Keywords

• nonn
• easy

References

• Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 115-119.

Links

• Seiichi Manyama, Table of n, a(n) for n = 1..10000
• Joel E. Cohen, Conjectures about Primes and Cyclic Numbers, arXiv:2508.08335 [math.NT], 2025. See p. 2.
• Paul Erdős, Some asymptotic formulas in number theory, J. Indian Math. Soc. 12 (1948) 75-78.
• Steven R. Finch, Euler Totient Function Asymptotic Constants. [Broken link]
• Steven R. Finch, Euler Totient Function Asymptotic Constants. [From the Wayback machine]
• Paul Pollack, Numbers which are orders only of cyclic groups, Proceedings of the American Mathematical Society, Vol. 150, No. 2 (2022), pp. 515-524; arXiv preprint, arXiv:2007.09734 [math.NT], 2020.
• Imre Z. Ruzsa, Erdős and the integers, J. Number Theory, Vol. 79, No. 1 (1999), 115-163.

Crossrefs

Partial sums of A297086.

Cf. A000010 (phi), A001620 (gamma), A003277, A073004, A080130.

Programs

Mathematica

s[n_] := Boole[CoprimeQ[n, EulerPhi[n]]]; Accumulate[Array[s, 100]]  (* Amiram Eldar, Dec 10 2024 *)

PARI

a(n) = sum(k=1, n, gcd(k, eulerphi(k)) == 1) \\ Charles R Greathouse IV, Jan 29 2013 (corrected by Iain Fox, Dec 25 2017)

PARI

list(lim) = {my(s = 0); for(k = 1, lim, s += gcd(k, eulerphi(k)) == 1; print1(s, ", "));} \\ Amiram Eldar, Dec 10 2024

Formula

Limit_{n->oo} a(n) * log(log(log(n))) / n = 1/exp(gamma).

a(n) = Sum_{k=1..n} gcd(k, phi(k)) = 1.

a(1) = 1; a(n) = a(n-1) + A297086(n). - Iain Fox, Dec 25 2017