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

%I #32 Aug 07 2021 01:40:54

%S 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,

%T 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,

%U 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

%N a(n) = phi(n) - phi(n-phi(n)), a(1) = 1.

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

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

%H Paul Erdős, <a href="https://books.google.com/books?id=KBD87GWw9mMC&amp;lpg=PA381&amp;pg=PA505">Problem P. 294</a>, Canad. Math. Bull., Vol. 23, No. 4 (1980), p. 505.

%H Florian Luca and Carl Pomerance, <a href="https://doi.org/10.4064/cm92-1-10">On some problems of Mąkowski-Schinzel and Erdős concerning the arithmetical functions phi and sigma</a>, Colloq. Math., Vol. 92, No. 1 (2002), pp. 111-130.

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

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

%p with(numtheory):

%p A := seq(phi(n) - phi(n-phi(n)), n=1..100);

%t a[n_] := (phi = EulerPhi[n]) - EulerPhi[n - phi]; Array[a, 100] (* _Amiram Eldar_, Jul 29 2021 *)

%o (PARI) a(n) = if (n==1, 1, eulerphi(n) - eulerphi(n-eulerphi(n))); \\ _Michel Marcus_, Jul 29 2021

%o (Python)

%o from sympy import totient as phi

%o def a(n):

%o if n == 1: return 1

%o phin = phi(n)

%o return phin - phi(n - phin)

%o print([a(n) for n in range(1, 81)]) # _Michael S. Branicky_, Jul 29 2021

%Y Cf. A000010, A054571.

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

%K sign

%O 1,5

%A _Bernard Schott_, Jul 29 2021