A081373 Number of values of k, 1 <= k <= n, with phi(k) = phi(n), where phi is Euler totient function, A000010.

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

Offset: 1

Author

Labos Elemer, Mar 24 2003

Keywords

• nonn

Comments

Ordinal transform of Euler totient function phi, A000010. - Antti Karttunen, Aug 26 2024

Examples

			For n = 16: phi(k) = {1,1,2,2,4,2,6,4,6,4,10,4,12,6,8,8} for k = 1,...,n; 2 numbers exist with phi(k) = phi(n) = 8: {15,16}, so a(16) = 2.
If n = p is an odd prime number, then a(p) = 1 with phi(k) = p-1.
		

Links

• Paul Tek, Table of n, a(n) for n = 1..100000
• Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).

Crossrefs

Cf. A000010, A081375 (positions of records), A210719 (of 1's).

Cf. also A067004, A303756, A303757, A303777 (ordinal transform of this sequence).

Programs

Mathematica

f[x_] := Count[Table[EulerPhi[j]-EulerPhi[x], {j, 1, x}], 0] Table[f[w], {w, 1, 100}]

PARI

a(n)=my(t=eulerphi(n), s); sum(k=1, n, eulerphi(k)==t) \\ Charles R Greathouse IV, Feb 21 2013, corrected by Antti Karttunen, Aug 26 2024

PARI

a(n) = #select(x -> x <= n, invphi(eulerphi(n))); \\ Amiram Eldar, Nov 08 2024, using Max Alekseyev's invphi.gp