|
|
A029939
|
|
a(n) = Sum_{d|n} phi(d)^2.
|
|
15
|
|
|
1, 2, 5, 6, 17, 10, 37, 22, 41, 34, 101, 30, 145, 74, 85, 86, 257, 82, 325, 102, 185, 202, 485, 110, 417, 290, 365, 222, 785, 170, 901, 342, 505, 514, 629, 246, 1297, 650, 725, 374, 1601, 370, 1765, 606, 697, 970, 2117, 430, 1801, 834, 1285, 870, 2705, 730, 1717, 814, 1625
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
Number of (i,j) in {1,2,...,n}^2 such that gcd(n,i) = gcd(n,j). - Benoit Cloitre, Dec 31 2020
|
|
LINKS
|
|
|
FORMULA
|
Multiplicative with a(p^e) = (p^(2*e)*(p-1)+2)/(p+1). - Vladeta Jovovic, Nov 19 2001
G.f.: Sum_{k>=1} phi(k)^2*x^k/(1 - x^k), where phi(k) is the Euler totient function (A000010). - Ilya Gutkovskiy, Jan 16 2017
Sum_{k>=1} 1/a(k) = 2.3943802654751092440350752246012273573942903149891228695146514601814537713... - Vaclav Kotesovec, Sep 20 2020
Sum_{k=1..n} a(k) ~ c * n^3, where c = (zeta(3)/(3*zeta(2)) * Product_{p prime} (1 - 1/(p*(p+1))) = A253905 * A065463 / 3 = 0.171593... . - Amiram Eldar, Oct 25 2022
|
|
MAPLE
|
with(numtheory): A029939 := proc(n) local i, j; j := 0; for i in divisors(n) do j := j+phi(i)^2; od; j; end;
# alternative
N:= 1000: # to get a(1)..a(N)
A:= Vector(N, 1):
for d from 2 to N do
pd:= numtheory:-phi(d)^2;
md:= [seq(i, i=d..N, d)];
A[md]:= map(`+`, A[md], pd);
od:
|
|
MATHEMATICA
|
Table[Total[EulerPhi[Divisors[n]]^2], {n, 60}] (* Harvey P. Dale, Feb 04 2017 *)
f[p_, e_] := (p^(2*e)*(p-1)+2)/(p+1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Sep 18 2020 *)
|
|
PROG
|
(PARI) a(n) = sumdiv(n, d, eulerphi(d)^2); \\ Michel Marcus, Jan 17 2017
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,mult,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|