A346692 a(n) = phi(n) - phi(n-phi(n)), a(1) = 1.

1, 0, 1, 1, 3, 0, 5, 2, 4, 2, 9, 0, 11, 2, 2, 4, 15, 2, 17, 4, 6, 6, 21, 0, 16, 6, 12, 4, 27, -2, 29, 8, 8, 10, 14, 4, 35, 10, 16, 8, 39, 4, 41, 12, 12, 14, 45, 0, 36, 12, 14, 12, 51, 6, 32, 8, 24, 20, 57, -4, 59, 14, 18, 16, 32, -2, 65, 20, 24, 2, 69, 8, 71, 18, 16, 20, 44, 6, 77, 16

Offset: 1

Author

Bernard Schott, Jul 29 2021

Keywords

• sign

Comments

P. Erdős conjectured that a(n) > 0 on a set of asymptotic density 1, then Luca and Pomerance proved this conjecture (see link).

References

• Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section B42, p. 150.

Links

• Paul Erdős, Problem P. 294, Canad. Math. Bull., Vol. 23, No. 4 (1980), p. 505.
• Florian Luca and Carl Pomerance, On some problems of Mąkowski-Schinzel and Erdős concerning the arithmetical functions phi and sigma, Colloq. Math., Vol. 92, No. 1 (2002), pp. 111-130.

Crossrefs

Cf. A000010, A054571.

Cf. A051487 (a(n)=0), A051488 (a(n)<0).

Programs

Maple

with(numtheory):
A := seq(phi(n) - phi(n-phi(n)), n=1..100);

Mathematica

a[n_] := (phi = EulerPhi[n]) - EulerPhi[n - phi]; Array[a, 100] (* Amiram Eldar, Jul 29 2021 *)

PARI

a(n) = if (n==1, 1, eulerphi(n) - eulerphi(n-eulerphi(n))); \\ Michel Marcus, Jul 29 2021

Python

from sympy import totient as phi
def a(n):
    if n == 1: return 1
    phin = phi(n)
    return phin - phi(n - phin)
print([a(n) for n in range(1, 81)]) # Michael S. Branicky, Jul 29 2021

Formula

a(n) = A000010(n) - A054571(n).

If p prime, a(p) = p-2, and for k >= 2, a(p^k) = (p-1)^2 * p^(k-2).