A018804 Pillai's arithmetical function: Sum_{k=1..n} gcd(k, n).
1, 3, 5, 8, 9, 15, 13, 20, 21, 27, 21, 40, 25, 39, 45, 48, 33, 63, 37, 72, 65, 63, 45, 100, 65, 75, 81, 104, 57, 135, 61, 112, 105, 99, 117, 168, 73, 111, 125, 180, 81, 195, 85, 168, 189, 135, 93, 240, 133, 195, 165, 200, 105, 243, 189, 260, 185, 171, 117, 360
Offset: 1
Examples
G.f. = x + 3*x^2 + 5*x^3 + 8*x^4 + 9*x^5 + 15*x^6 + 13*x^7 + 20*x^8 + ...
References
- S. S. Pillai, On an arithmetic function, J. Annamalai University 2 (1933), pp. 243-248.
- J. Sándor, A generalized Pillai function, Octogon Mathematical Magazine Vol. 9, No. 2 (2001), 746-748.
Links
- Seiichi Manyama, Table of n, a(n) for n = 1..10000 (first 2000 terms from T. D. Noe)
- U. Abel, W. Awan, and V. Kushnirevych, A Generalization of the Gcd-Sum Function, J. Int. Seq. 16 (2013) #13.6.7.
- Antal Bege, Hadamard product of GCD matrices, Acta Univ. Sapientiae, Mathematica, 1, 1 (2009) 43-49.
- Olivier Bordelles, The Composition of the gcd and Certain Arithmetic Functions, J. Int. Seq. 13 (2010) #10.7.1.
- Olivier Bordelles, An Asymptotic Formula for Short Sums of Gcd-Sum Functions, Journal of Integer Sequences, Vol. 15 (2012), #12.6.8.
- Olivier Bordelles, A Multidimensional Cesáro Type Identity and Applications, J. Int. Seq. 18 (2015) # 15.3.7.
- Kevin A. Broughan, The gcd-sum function, Journal of Integer Sequences 4 (2001), Article 01.2.2, 19 pp.
- J.-M. De Koninck and I. Kátai, Some remarks on a paper of L. Toth, JIS 13 (2010) 10.1.2.
- Pentti Haukkanen and László Tóth, Menon-type identities again: Note on a paper by Li, Kim and Qiao, arXiv:1911.05411 [math.NT], 2019.
- Soichi Ikeda and Kaneaki Matsuoka, On the Lcm-Sum Function, Journal of Integer Sequences, Vol. 17 (2014), Article 14.1.7.
- Mathematical Reflections, Solution to Problem O364, Issue 2, 2016, p 24. [Cached copy at Wayback Machine]
- Taylor McAdam, Almost-primes in horospherical flows on the space of lattices, arXiv:1802.08764 [math.DS], 2018.
- Taylor McAdam, Almost-prime times in horospherical flows on the space of lattices, Journal of Modern Dynamics (2019) Vol. 15, 277-327.
- J. Ransford, A Sum of Gcd’s over Friable Numbers, JIS vol 19 (2016) # 16.3.2
- Jeffrey Shallit, Problem E 2821, American Mathematical Monthly 87 (1980), 220.
- Jeffrey Shallit, Solution, American Mathematical Monthly, 88 (1981), 444-445.
- László Tóth, A gcd-sum function over regular integers modulo n, JIS 12 (2009) 09.2.5.
- László Tóth, On the Bi-Unitary Analogues of Euler's Arithmetical Function and the Gcd-Sum Function, JIS 12 (2009) 09.5.2.
- László Tóth, A survey of gcd-sum functions, J. Integer Sequences 13 (2010), Article 10.8.1, 23 pp.
- László Tóth, Weighted gcd-sum functions, J. Integer Sequences, 14 (2011), Article 11.7.7.
- D. Zhang and W. Zhai, Mean Values of a Gcd-Sum Function Over Regular Integers Modulo n, J. Int. Seq. 13 (2010), 10.4.7.
- D. Zhang and W. Zhai, Mean Values of a Class of Arithmetical Functions, J. Int. Seq. 14 (2011) #11.6.5.
- D. Zhang and W. Zhai, On an Open Problem of Tóth, J. Int. Seq. 16 (2013) #13.6.5.
Crossrefs
Programs
-
Haskell
a018804 n = sum $ map (gcd n) [1..n] -- Reinhard Zumkeller, Jul 16 2012
-
Magma
[&+[Gcd(n,k):k in [1..n]]:n in [1..60]]; // Marius A. Burtea, Nov 14 2019
-
Maple
a:=n->sum(igcd(n,j),j=1..n): seq(a(n), n=1..60); # Zerinvary Lajos, Nov 05 2006
-
Mathematica
f[n_] := Block[{d = Divisors[n]}, Sum[ d*EulerPhi[n/d], {d, d}]]; Table[f[n], {n, 60}] (* Robert G. Wilson v, Mar 20 2012 *) a[ n_] := If[ n < 1, 0, n Sum[ EulerPhi[d] / d, {d, Divisors@n}]]; (* Michael Somos, Jan 07 2017 *) f[p_, e_] := (e*(p - 1)/p + 1)*p^e; a[n_] := Times @@ (f @@@ FactorInteger[n]); Array[a, 100] (* Amiram Eldar, Jul 19 2019 *) -
PARI
{a(n) = direuler(p=2, n, (1 - X) / (1 - p*X)^2)[n]}; /* Michael Somos, May 31 2000 */ -
PARI
a(n)={ my(ct=0); for(i=0,n-1,for(j=0,n-1, ct+=(Mod(i*j,n)==0) ) ); ct; } \\ Joerg Arndt, Aug 03 2013 -
PARI
a(n)=my(f=factor(n)); prod(i=1,#f~,(f[i,2]*(f[i,1]-1)/f[i,1] + 1)*f[i,1]^f[i,2]) \\ Charles R Greathouse IV, Oct 28 2014
-
PARI
a(n) = sumdiv(n, d, n*eulerphi(d)/d); \\ Michel Marcus, Jan 07 2017
-
Python
from sympy.ntheory import totient, divisors print([sum(n*totient(d)//d for d in divisors(n)) for n in range(1, 101)]) # Indranil Ghosh, Apr 04 2017
-
Python
from sympy import factorint from math import prod def A018804(n): return prod(p**(e-1)*((p-1)*e+p) for p, e in factorint(n).items()) # Chai Wah Wu, Nov 29 2021
Formula
a(n) = Sum_{d|n} d*phi(n/d), where phi(n) is Euler totient function (cf. A000010). - Vladeta Jovovic, Apr 04 2001
Multiplicative; for prime p, a(p^e) = p^(e-1)*((p-1)e+p).
Dirichlet g.f.: zeta(s-1)^2/zeta(s).
a(n) = Sum_{d|n} d*tau(d)*mu(n/d). - Benoit Cloitre, Oct 23 2003
Equals inverse Mobius transform of A029935 = A054525 * (1, 2, 4, 5, 8, 8, 12, 12, ...). - Gary W. Adamson, Aug 02 2008, corrected Feb 07 2023
Equals row sums of triangle A127478. - Gary W. Adamson, Aug 03 2008
G.f.: Sum_{k>=1} phi(k)*x^k/(1 - x^k)^2, where phi(k) is the Euler totient function. - Ilya Gutkovskiy, Jan 02 2017
a(n) = Sum_{a = 1..n} Sum_{b = 1..n} Sum_{c = 1..n} 1, for n > 1. The sum is over a,b,c such that n*c - a*b = 0. - Benedict W. J. Irwin, Apr 04 2017
Proof: Let gcd(a, n) = g and x = n/g. Define B = {x, 2*x, ..., g*x}; then for all b in B there exists a number c such that a*b = n*c. Since the set B has g elements it follows that Sum_{b=1..n} Sum_{c=1..n} 1 >= g = gcd(a, n) and therefore Sum_{a=1..n} Sum_{b=1..n} Sum_{c=1..n} 1 >= Sum_{a=1..n} gcd(a, n). On the other hand, for all b not in B there is no number c <= n such that a*b = n*c and hence Sum_{b = 1..n} Sum_{c = 1..n} 1 = g. Therefore Sum_{a=1..n} Sum_{b = 1..n} Sum_{c = 1..n} 1 = a(n). - Ruediger Jehn, Jun 23 2022
Proof: Let m = A007814(m) and decompose n into n = k*2^m. We know from Chai Wah Wu's program below that a(n) = Product(p_i^(e_i-1)*((p_i-1)*e_i+p_i)) where the numbers p_i are the prime factors of n and e_i are the corresponding exponents. Hence a(2n) = 2^m*(m+3)*a(k) = 2^m*(m+3)*a(k). On the other hand, a(n) = 2^(m-1)*(m+2)*a(k). Dividing the first equation by the second yields a(2n)/a(n) = 2*(m+3)/(m+2), which equals 3 - m/(m+2). Hence a(2n) = a(n)*(3 - m/(m+2)). - Ruediger Jehn, Jun 23 2022
Sum_{k=1..n} a(k) ~ 3*n^2/Pi^2 * (log(n) - 1/2 + 2*gamma - 6*Zeta'(2)/Pi^2), where gamma is the Euler-Mascheroni constant A001620. - Vaclav Kotesovec, Feb 08 2019
a(n) = Sum_{k=1..n} n/gcd(n,k)*phi(gcd(n,k))/phi(n/gcd(n,k)). - Richard L. Ollerton, May 10 2021
log(a(n)/n) << log n log log log n/log log n; in particular, a(n) << n^(1+e) for any e > 0. See Broughan link for bounds in terms of omega(n). - Charles R Greathouse IV, Sep 08 2022
a(n) = (1/4)*Sum_{k = 1..4*n} (-1)^k * gcd(k, 4*n) = (1/4) * A344372(2*n). - Peter Bala, Jan 01 2024
Comments