cp's OEIS Frontend

A029939 a(n) = Sum_{d|n} phi(d)^2.

%I A029939 #52 Jan 01 2025 23:31:30
%S A029939 1,2,5,6,17,10,37,22,41,34,101,30,145,74,85,86,257,82,325,102,185,202,
%T A029939 485,110,417,290,365,222,785,170,901,342,505,514,629,246,1297,650,725,
%U A029939 374,1601,370,1765,606,697,970,2117,430,1801,834,1285,870,2705,730,1717,814,1625
%N A029939 a(n) = Sum_{d|n} phi(d)^2.
%C A029939 Equals the inverse Mobius transform (A051731) of A127473. - _Gary W. Adamson_, Aug 20 2008
%C A029939 Number of (i,j) in {1,2,...,n}^2 such that gcd(n,i) = gcd(n,j). - _Benoit Cloitre_, Dec 31 2020
%H A029939 Robert Israel, <a href="/A029939/b029939.txt">Table of n, a(n) for n = 1..10000</a>
%F A029939 Multiplicative with a(p^e) = (p^(2*e)*(p-1)+2)/(p+1). - _Vladeta Jovovic_, Nov 19 2001
%F A029939 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
%F A029939 a(n) = Sum_{k=1..n} phi(n/gcd(n, k)). - _Ridouane Oudra_, Nov 28 2019
%F A029939 Sum_{k>=1} 1/a(k) = 2.3943802654751092440350752246012273573942903149891228695146514601814537713... - _Vaclav Kotesovec_, Sep 20 2020
%F A029939 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
%p A029939 with(numtheory): A029939 := proc(n) local i,j; j := 0; for i in divisors(n) do j := j+phi(i)^2; od; j; end;
%p A029939 # alternative
%p A029939 N:= 1000: # to get a(1)..a(N)
%p A029939 A:= Vector(N,1):
%p A029939 for d from 2 to N do
%p A029939   pd:= numtheory:-phi(d)^2;
%p A029939   md:= [seq(i,i=d..N,d)];
%p A029939   A[md]:= map(`+`,A[md],pd);
%p A029939 od:
%p A029939 seq(A[i],i=1..N); # _Robert Israel_, May 30 2016
%t A029939 Table[Total[EulerPhi[Divisors[n]]^2],{n,60}] (* _Harvey P. Dale_, Feb 04 2017 *)
%t A029939 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 *)
%o A029939 (PARI) a(n) = sumdiv(n, d, eulerphi(d)^2); \\ _Michel Marcus_, Jan 17 2017
%Y A029939 Cf. A051731, A062367, A065463, A127473, A253905.
%K A029939 nonn,mult,easy
%O A029939 1,2
%A A029939 _N. J. A. Sloane_