cp's OEIS Frontend

A018804 Pillai's arithmetical function: Sum_{k=1..n} gcd(k, n).

%I A018804 #261 Aug 13 2025 18:41:11
%S A018804 1,3,5,8,9,15,13,20,21,27,21,40,25,39,45,48,33,63,37,72,65,63,45,100,
%T A018804 65,75,81,104,57,135,61,112,105,99,117,168,73,111,125,180,81,195,85,
%U A018804 168,189,135,93,240,133,195,165,200,105,243,189,260,185,171,117,360
%N A018804 Pillai's arithmetical function: Sum_{k=1..n} gcd(k, n).
%C A018804 a(n) is the number of times the number 1 appears in the character table of the cyclic group C_n. - Ahmed Fares (ahmedfares(AT)my-deja.com), Jun 02 2001
%C A018804 a(n) is the number of ways to express all fractions f/g whereby each product (f/g)*n is a natural number between 1 and n (using fractions of the form f/g with 1 <= f,g <= n). For example, for n=4 there are 8 such fractions: 1/1, 1/2, 2/2, 3/3, 1/4, 2/4, 3/4 and 4/4. - Ron Lalonde (ronronronlalonde(AT)hotmail.com), Oct 03 2002
%C A018804 Number of non-congruent solutions to xy == 0 (mod n). - Yuval Dekel (dekelyuval(AT)hotmail.com), Oct 06 2003
%C A018804 Conjecture: n>1 divides a(n)+1 iff n is prime. - _Thomas Ordowski_, Oct 22 2014
%C A018804 The above conjecture is false, with counterexample given by n = 3*37*43*42307*116341 and a(n)+1 = 26*n. - _Varun Vejalla_, Jun 19 2025
%C A018804 a(n) is the number of 0's in the multiplication table Z/nZ (cf. A000010 for number of 1's). - _Eric Desbiaux_, Jun 11 2015
%C A018804 {a(n)} == 1, 3, 1, 0, 1, 3, 1, 0, ... (mod 4). - _Isaac Saffold_, Dec 30 2017
%C A018804 Since a(p^e) = p^(e-1)*((p-1)e+p) it follows a(p) = 2p-1 and therefore p divides a(p)+1. - _Ruediger Jehn_, Jun 23 2022
%D A018804 S. S. Pillai, On an arithmetic function, J. Annamalai University 2 (1933), pp. 243-248.
%D A018804 J. Sándor, A generalized Pillai function, Octogon Mathematical Magazine Vol. 9, No. 2 (2001), 746-748.
%H A018804 Seiichi Manyama, <a href="/A018804/b018804.txt">Table of n, a(n) for n = 1..10000</a> (first 2000 terms from T. D. Noe)
%H A018804 U. Abel, W. Awan, and V. Kushnirevych, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Abel/abel5.html">A Generalization of the Gcd-Sum Function</a>, J. Int. Seq. 16 (2013) #13.6.7.
%H A018804 Antal Bege, <a href="https://www.emis.de/journals/AUSM/C1-1/MATH1-4.PDF">Hadamard product of GCD matrices</a>, Acta Univ. Sapientiae, Mathematica, 1, 1 (2009) 43-49.
%H A018804 Olivier Bordelles, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Bordelles/bordelles6.html">The Composition of the gcd and Certain Arithmetic Functions</a>, J. Int. Seq. 13 (2010) #10.7.1.
%H A018804 Olivier Bordelles, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Bordelles/bordelles11.html">An Asymptotic Formula for Short Sums of Gcd-Sum Functions</a>, Journal of Integer Sequences, Vol. 15 (2012), #12.6.8.
%H A018804 Olivier Bordelles, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Bordelles/bord21.html">A Multidimensional Cesáro Type Identity and Applications</a>, J. Int. Seq. 18 (2015) # 15.3.7.
%H A018804 Kevin A. Broughan, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL4/BROUGHAN/gcdsum.html">The gcd-sum function</a>, Journal of Integer Sequences 4 (2001), Article 01.2.2, 19 pp.
%H A018804 J.-M. De Koninck and I. Kátai, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/DeKoninck/dekoninck7.html">Some remarks on a paper of L. Toth</a>, JIS 13 (2010) 10.1.2.
%H A018804 Pentti Haukkanen and László Tóth, <a href="https://arxiv.org/abs/1911.05411">Menon-type identities again: Note on a paper by Li, Kim and Qiao</a>, arXiv:1911.05411 [math.NT], 2019.
%H A018804 Soichi Ikeda and Kaneaki Matsuoka, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Ikeda/ikeda4.html">On the Lcm-Sum Function</a>, Journal of Integer Sequences, Vol. 17 (2014), Article 14.1.7.
%H A018804 Mathematical Reflections, <a href="https://web.archive.org/web/20201024230832/https://www.awesomemath.org/wp-pdf-files/math-reflections/mr-2016-02/mr_1_2016_solutions.pdf">Solution to Problem O364</a>, Issue 2, 2016, p 24. [Cached copy at Wayback Machine]
%H A018804 Taylor McAdam, <a href="https://arxiv.org/abs/1802.08764">Almost-primes in horospherical flows on the space of lattices</a>, arXiv:1802.08764 [math.DS], 2018.
%H A018804 Taylor McAdam, <a href="https://doi.org/10.3934/jmd.2019022">Almost-prime times in horospherical flows on the space of lattices</a>, Journal of Modern Dynamics (2019) Vol. 15, 277-327.
%H A018804 J. Ransford, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Ransford/ransford2.html">A Sum of Gcd’s over Friable Numbers</a>, JIS vol 19 (2016) # 16.3.2
%H A018804 Jeffrey Shallit, <a href="https://www.jstor.org/stable/2321618">Problem E 2821</a>, American Mathematical Monthly 87 (1980), 220.
%H A018804 Jeffrey Shallit, <a href="https://www.jstor.org/stable/2321834">Solution</a>, American Mathematical Monthly, 88 (1981), 444-445.
%H A018804 László Tóth, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Toth/toth3.html">A gcd-sum function over regular integers modulo n</a>, JIS 12 (2009) 09.2.5.
%H A018804 László Tóth, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Toth2/toth5.html">On the Bi-Unitary Analogues of Euler's Arithmetical Function and the Gcd-Sum Function</a>, JIS 12 (2009) 09.5.2.
%H A018804 László Tóth, <a href="https://www.cs.uwaterloo.ca/journals/JIS/VOL13/Toth/toth10.html">A survey of gcd-sum functions</a>, J. Integer Sequences 13 (2010), Article 10.8.1, 23 pp.
%H A018804 László Tóth, <a href="https://www.cs.uwaterloo.ca/journals/JIS/VOL14/Toth/toth9.html">Weighted gcd-sum functions</a>, J. Integer Sequences, 14 (2011), Article 11.7.7.
%H A018804 D. Zhang and W. Zhai, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Zhang/zhang10.html">Mean Values of a Gcd-Sum Function Over Regular Integers Modulo n</a>, J. Int. Seq. 13 (2010), 10.4.7.
%H A018804 D. Zhang and W. Zhai, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Zhang/zhang14.html">Mean Values of a Class of Arithmetical Functions</a>, J. Int. Seq. 14 (2011) #11.6.5.
%H A018804 D. Zhang and W. Zhai, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Zhang/zhang20.html">On an Open Problem of Tóth</a>, J. Int. Seq. 16 (2013) #13.6.5.
%F A018804 a(n) = Sum_{d|n} d*phi(n/d), where phi(n) is Euler totient function (cf. A000010). - _Vladeta Jovovic_, Apr 04 2001
%F A018804 Multiplicative; for prime p, a(p^e) = p^(e-1)*((p-1)e+p).
%F A018804 Dirichlet g.f.: zeta(s-1)^2/zeta(s).
%F A018804 a(n) = Sum_{d|n} d*tau(d)*mu(n/d). - _Benoit Cloitre_, Oct 23 2003
%F A018804 Equals A054523 * [1,2,3,...]. Equals row sums of triangle A010766. - _Gary W. Adamson_, May 20 2007
%F A018804 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
%F A018804 Equals row sums of triangle A127478. - _Gary W. Adamson_, Aug 03 2008
%F A018804 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
%F A018804 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
%F A018804 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
%F A018804 a(2*n) = a(n)*(3-A007814(n)/(A007814(n)+2)) - _Velin Yanev_, Jun 30 2017
%F A018804 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
%F A018804 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
%F A018804 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
%F A018804 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
%F A018804 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
%e A018804 G.f. = x + 3*x^2 + 5*x^3 + 8*x^4 + 9*x^5 + 15*x^6 + 13*x^7 + 20*x^8 + ...
%p A018804 a:=n->sum(igcd(n,j),j=1..n): seq(a(n), n=1..60); # _Zerinvary Lajos_, Nov 05 2006
%t A018804 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 *)
%t A018804 a[ n_] := If[ n < 1, 0, n Sum[ EulerPhi[d] / d, {d, Divisors@n}]]; (* _Michael Somos_, Jan 07 2017 *)
%t A018804 f[p_, e_] := (e*(p - 1)/p + 1)*p^e; a[n_] := Times @@ (f @@@ FactorInteger[n]); Array[a, 100] (* _Amiram Eldar_, Jul 19 2019 *)
%o A018804 (PARI) {a(n) = direuler(p=2, n, (1 - X) / (1 - p*X)^2)[n]}; /* _Michael Somos_, May 31 2000 */
%o A018804 (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
%o A018804 (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
%o A018804 (PARI) a(n) = sumdiv(n, d, n*eulerphi(d)/d); \\ _Michel Marcus_, Jan 07 2017
%o A018804 (Haskell)
%o A018804 a018804 n = sum $ map (gcd n) [1..n]  -- _Reinhard Zumkeller_, Jul 16 2012
%o A018804 (Python)
%o A018804 from sympy.ntheory import totient, divisors
%o A018804 print([sum(n*totient(d)//d for d in divisors(n)) for n in range(1, 101)]) # _Indranil Ghosh_, Apr 04 2017
%o A018804 (Python)
%o A018804 from sympy import factorint
%o A018804 from math import prod
%o A018804 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
%o A018804 (Magma) [&+[Gcd(n,k):k in [1..n]]:n in [1..60]]; // _Marius A. Burtea_, Nov 14 2019
%Y A018804 Column 1 of A343510 and A343516.
%Y A018804 Cf. A080997, A080998 for rankings of the positive integers in terms of centrality, defined to be the average fraction of an integer that it shares with the other integers as a gcd, or A018804(n)/n^2, also A080999, a permutation of this sequence (A080999(n) = A018804(A080997(n))).
%Y A018804 Cf. A185210, A010766, A054523, A127468, A050873, A078430, A095026, A227507, A000010, A344372, A272718 (partial sums), A368736 - A368741.
%K A018804 nonn,mult
%O A018804 1,2
%A A018804 _David W. Wilson_