A055654 Difference between n and the result of "Phi-summation" over unitary divisors of n.

0, 0, 0, 1, 0, 0, 0, 3, 2, 0, 0, 3, 0, 0, 0, 7, 0, 4, 0, 5, 0, 0, 0, 9, 4, 0, 8, 7, 0, 0, 0, 15, 0, 0, 0, 15, 0, 0, 0, 15, 0, 0, 0, 11, 10, 0, 0, 21, 6, 8, 0, 13, 0, 16, 0, 21, 0, 0, 0, 15, 0, 0, 14, 31, 0, 0, 0, 17, 0, 0, 0, 37, 0, 0, 12, 19, 0, 0, 0, 35, 26, 0, 0, 21, 0, 0, 0, 33, 0, 20, 0, 23

Offset: 1

Author

Labos Elemer, Jun 07 2000

Keywords

• nonn
• easy

Comments

Squarefree numbers are roots of a(n)=0 equation, while Min n for which a(n)=k is k^2. See also A000188, A008833.

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000188, A008833, A055653, A053570, A053571, A055631, A055632, A055653, A065465.

Programs

Haskell

a055654 n = a055654_list !! (n-1)
a055654_list = zipWith (-) [1..] a055653_list
-- Reinhard Zumkeller, Mar 11 2012

Mathematica

Table[n - DivisorSum[n, EulerPhi[#] &, CoprimeQ[#, n/#] &], {n, 92}] (* Michael De Vlieger, Oct 26 2017 *)
f[p_, e_] := p^e - p^(e-1) + 1; a[1] = 0; a[n_] := n - Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Oct 04 2024 *)

PARI

a(n) = n - sumdiv(n, d, if (gcd(d, n/d)==1, eulerphi(d))); \\ Michel Marcus, Oct 27 2017

PARI

a(n) = {my(f = factor(n)); n - prod(k = 1, #f~, f[k,1]^f[k,2] - f[k,1]^(f[k,2] - 1) + 1);} \\ Amiram Eldar, Oct 04 2024

Formula

a(n) = n - Sum_{u|n, gcd(u,n/u) = 1} phi(u), i.e. when u is a unitary divisor of n.

a(n) = n - A055653(n). - Sean A. Irvine, Mar 30 2022

Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = 1 - A065465 = 0.11848616... . - Amiram Eldar, Oct 04 2024