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,5

Links

Paolo Xausa, Table of n, a(n) for n = 1..10000

Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).

Formula

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

Mathematica

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

Prog

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

Crossrefs

Cf. A000010, A069932, A378637, A378641.

Sequence in context: A092319 A254938 A244149 * A147410 A146623 A197943

Adjacent sequences: A378639 A378640 A378641 * A378643 A378644 A378645

Keyword

nonn,easy

Author

Paolo Xausa, Dec 05 2024

Status

approved