A378642 Number of numbers m <= n such that phi(m) does not divide n, where phi is the Euler totient function (A000010).

0, 0, 1, 0, 3, 1, 5, 1, 7, 5, 9, 1, 11, 9, 13, 5, 15, 9, 17, 10, 19, 17, 21, 5, 23, 21, 25, 19, 27, 19, 29, 16, 31, 29, 33, 16, 35, 33, 37, 22, 39, 33, 41, 34, 43, 41, 45, 16, 47, 43, 49, 43, 51, 41, 53, 41, 55, 53, 57, 34, 59, 57, 61, 42, 63, 55, 65, 59, 67, 63

Offset: 1

Author

Paolo Xausa, Dec 05 2024

Keywords

• nonn
• easy

Links

• Paolo Xausa, Table of n, a(n) for n = 1..10000
• Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).

Crossrefs

Cf. A000010, A069932, A378637, A378641.

Programs

Mathematica

Table[Count[Divisible[n, #[[;;n]]], False], {n, Length[#]}] & [EulerPhi[Range[100]]]

PARI

a(n) = n - sumdiv(n, d, #select(x -> x<=n, invphi(d))); \\ Amiram Eldar, Dec 10 2024, using Max Alekseyev's invphi.gp

Formula

a(n) = n - A069932(n).