login
a(n) = Sum_{d|n} gcd(d, n/d).
13

%I #78 Nov 28 2023 13:05:45

%S 1,2,2,4,2,4,2,6,5,4,2,8,2,4,4,10,2,10,2,8,4,4,2,12,7,4,8,8,2,8,2,14,

%T 4,4,4,20,2,4,4,12,2,8,2,8,10,4,2,20,9,14,4,8,2,16,4,12,4,4,2,16,2,4,

%U 10,22,4,8,2,8,4,8,2,30,2,4,14,8,4,8,2,20,17,4,2,16,4,4,4,12,2,20,4,8,4,4

%N a(n) = Sum_{d|n} gcd(d, n/d).

%C a(n) is odd iff n is odd square. - _Vladeta Jovovic_, Aug 27 2002

%C From _Robert Israel_, Dec 26 2015: (Start)

%C a(n) >= A000005(n), with equality iff n is squarefree (i.e., is in A005117).

%C a(n) = 2 iff n is prime. (End)

%H Robert Israel, <a href="/A055155/b055155.txt">Table of n, a(n) for n = 1..10000</a>

%H Ekkehard Krätzel, Werner Nowak and László Tóth, <a href="https://eudml.org/doc/269485">On certain arithmetic functions involving the greatest common divisor</a>, Cent. Eur. J. Math., Vol. 10, No. 2 (2012), pp. 761-774.

%H Manfred Kühleitner and Werner Georg Nowak, <a href="https://doi.org/10.2478/s11533-012-0143-2">On a question of A. Schinzel: Omega estimates for a special type of arithmetic functions</a>, Central European Journal of Mathematics, Vol. 11, No. 3 (2013), pp. 477-486, <a href="http://arxiv.org/abs/1204.1146">preprint</a>, arXiv: 1204.1146 [math.NT], 2012.

%H Project Euler, <a href="https://projecteuler.net/problem=530">Problem 530 - GCD of Divisors</a>.

%H László Tóth, <a href="https://doi.org/10.1007/978-1-4939-1106-6_19">Multiplicative arithmetic functions of several variables: a survey</a>, in: T. Rassias and P. Pardalos (eds.), Mathematics Without Boundaries, Springer, New York, N.Y., 2014, pp. 483-514, <a href="http://arxiv.org/abs/1310.7053">arXiv preprint</a>, arXiv:1310.7053 [math.NT], 2013-2014.

%F Multiplicative with a(p^e) = (p^(e/2)*(p+1)-2)/(p-1) for even e and a(p^e) = 2*(p^((e+1)/2)-1)/(p-1) for odd e. - _Vladeta Jovovic_, Nov 01 2001

%F Dirichlet g.f.: (zeta(s))^2*zeta(2s-1)/zeta(2s); inverse Mobius transform of A000188. - _R. J. Mathar_, Feb 16 2011

%F Dirichlet convolution of A069290 and A008966. - _R. J. Mathar_, Oct 31 2011

%F Sum_{k=1..n} a(k) ~ 3*n / (2*Pi^6) * (Pi^4 * log(n)^2 + ((8*g - 2)*Pi^4 - 24 * Pi^2 * z1) * log(n) + 2*Pi^4 * (1 - 4*g + 5*g^2 - 6*sg1) + 288 * z1^2 - 24 * Pi^2 * (-z1 + 4*g*z1 + z2)), where g is the Euler-Mascheroni constant A001620, sg1 is the first Stieltjes constant A082633, z1 = Zeta'(2) = A073002, z2 = Zeta''(2) = A201994. - _Vaclav Kotesovec_, Feb 01 2019

%F a(n) = (1/n)*Sum_{i=1..n} sigma(gcd(n,i^2)). - _Ridouane Oudra_, Dec 30 2020

%F a(n) = Sum_{k=1..n} gcd(gcd(n,k),n/gcd(n,k))/phi(n/gcd(n,k)), where phi = A000010. - _Richard L. Ollerton_, May 09 2021

%e a(9) = gcd(1,9) + gcd(3,3) + gcd(9,1) = 5, since 1, 3, 9 are the positive divisors of 9.

%p N:= 1000: # to get a(1) to a(N)

%p V:= Vector(N):

%p for k from 1 to N do

%p for j from 1 to floor(N/k) do

%p V[k*j]:= V[k*j]+igcd(k,j)

%p od

%p od:

%p convert(V,list); # _Robert Israel_, Dec 26 2015

%t Table[DivisorSum[n, GCD[#, n/#] &], {n, 94}] (* _Michael De Vlieger_, Sep 23 2017 *)

%t f[p_, e_] := If[EvenQ[e], (p^(e/2)*(p+1)-2)/(p-1), 2*(p^((e+1)/2)-1)/(p-1)]; a[1] = 1; a[n_] := Times @@ (f @@@ FactorInteger[n]); Array[a, 100] (* _Amiram Eldar_, Sep 30 2020 *)

%o (PARI) a(n) = sumdiv(n, d, gcd(d, n/d)); \\ _Michel Marcus_, Aug 03 2016

%o (Python)

%o from sympy import divisors, gcd

%o def A055155(n): return sum(gcd(d,n//d) for d in divisors(n,generator=True)) # _Chai Wah Wu_, Aug 19 2021

%Y Cf. A000005, A000188, A001620, A005117, A057670, A073002. A082633, A201994.

%Y Cf. A000010.

%K easy,nonn,mult

%O 1,2

%A _Leroy Quet_, Jul 02 2000