A332713 a(n) = Sum_{d|n} phi(d/gcd(d, n/d)).

1, 2, 3, 4, 5, 6, 7, 7, 8, 10, 11, 12, 13, 14, 15, 13, 17, 16, 19, 20, 21, 22, 23, 21, 22, 26, 22, 28, 29, 30, 31, 24, 33, 34, 35, 32, 37, 38, 39, 35, 41, 42, 43, 44, 40, 46, 47, 39, 44, 44, 51, 52, 53, 44, 55, 49, 57, 58, 59, 60, 61, 62, 56, 46, 65, 66, 67, 68, 69, 70

Offset

1,2

Links

Amiram Eldar, Table of n, a(n) for n = 1..10000

Vaclav Kotesovec, Graph - the asymptotic ratio (1000000 terms).

Formula

Dirichlet g.f.: zeta(s) * zeta(2*s) * zeta(s - 1) * Product_{p prime} (1 - p^(-s) + p^(-2*s) - p^(1 - 2*s)).

a(n) = Sum_{d|n} phi(lcm(d, n/d)/d).

a(n) = Sum_{d|n} A010052(n/d) * A055653(d).

Sum_{k=1..n} a(k) ~ c * Pi^6 * n^2 / 1080, where c = A330523 = Product_{primes p} (1 - 1/p^2 - 1/p^3 + 1/p^4) = 0.5358961538283379998085... - Vaclav Kotesovec, Feb 22 2020

From Richard L. Ollerton, May 10 2021: (Start)

a(n) = Sum_{k=1..n} phi(gcd(n,k)/gcd(gcd(n,k),n/gcd(n,k)))/phi(n/gcd(n,k)).

a(n) = Sum_{k=1..n} phi(n/gcd(n,k)/gcd(gcd(n,k),n/gcd(n,k)))/phi(n/gcd(n,k)).

a(n) = Sum_{k=1..n} phi(lcm(gcd(n,k),n/gcd(n,k))/gcd(n,k))/phi(n/gcd(n,k)).

a(n) = Sum_{k=1..n} phi(lcm(gcd(n,k),n/gcd(n,k))*gcd(n,k)/n)/phi(n/gcd(n,k)).

a(n) = Sum_{k=1..n} A010052(gcd(n,k))*A055653(n/gcd(n,k))/phi(n/gcd(n,k)).

a(n) = Sum_{k=1..n} A010052(n/gcd(n,k))*A055653(gcd(n,k))/phi(n/gcd(n,k)). (End)

Multiplicative with a(p^e) = Sum_{k=0..e} phi(p^(k - min(k, e-k))). - Amiram Eldar, Nov 15 2025

Mathematica

Table[Sum[EulerPhi[d/GCD[d, n/d]], {d, Divisors[n]}], {n, 1, 70}]
(* Alternative: *)
A055653[n_] := Sum[Boole[GCD[d, n/d] == 1] EulerPhi[d], {d, Divisors[n]}]; a[n_] := Sum[Boole[IntegerQ[(n/d)^(1/2)]] A055653[d], {d, Divisors[n]}]; Table[a[n], {n, 1, 70}]
(* Alternative: *)
f[p_, e_] := Module[{d}, Sum[d = k - Min[k, e-k]; If[d == 0, 1, (p-1)*p^(d-1)], {k, 0, e}]];
a[n_] := Times @@ f @@@ FactorInteger[n]; a[1] = 1; Array[a, 100] (* Amiram Eldar, Nov 15 2025 *)

Prog

(PARI) a(n) = sumdiv(n, d, eulerphi(d/gcd(d, n/d))); \\ Michel Marcus, Feb 20 2020
(PARI) s(p, e) = my(d); sum(k = 0, e, d = k - min(k, e-k); if(d == 0, 1, (p-1)*p^(d-1)));
a(n) = {my(f = factor(n)); prod(i = 1, #f~, s(f[i, 1], f[i, 2])); } \\ Amiram Eldar, Nov 15 2025

Crossrefs

Cf. A000010, A001616, A010052, A046790 (numbers n such that a(n) < n), A055653, A061884, A078779 (fixed points), A332619, A332686, A332712.

Sequence in context: A124808 A238401 A337978 * A017862 A265539 A254926

Adjacent sequences: A332710 A332711 A332712 * A332714 A332715 A332716

Keyword

nonn,mult,easy

Author

Ilya Gutkovskiy, Feb 20 2020

Status

approved