login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A018804 Pillai's arithmetical function: Sum_{k=1..n} gcd(k, n). 143

%I #245 Jan 12 2024 22:25:43

%S 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 65,75,81,104,57,135,61,112,105,99,117,168,73,111,125,180,81,195,85,

%U 168,189,135,93,240,133,195,165,200,105,243,189,260,185,171,117,360

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

%C 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 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 Number of non-congruent solutions to xy == 0 (mod n). - Yuval Dekel (dekelyuval(AT)hotmail.com), Oct 06 2003

%C n>1 divides a(n)+1 iff n is prime. - _Thomas Ordowski_, Oct 22 2014

%C 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 {a(n)} == 1, 3, 1, 0, 1, 3, 1, 0, ... (mod 4). - _Isaac Saffold_, Dec 30 2017

%C 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 S. S. Pillai, On an arithmetic function, J. Annamalai University 2 (1933), pp. 243-248.

%D J. Sándor, A generalized Pillai function, Octogon Mathematical Magazine Vol. 9, No. 2 (2001), 746-748.

%H 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 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 Antal Bege, <a href="http://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 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 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 Olivier Bordelles, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Bordelles/bord21.html">A Multidimensional Cesaro Type Identity and Applications</a>, J. Int. Seq. 18 (2015) # 15.3.7.

%H Kevin A. Broughan, <a href="http://www.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 J.-M. De Koninck and I. Katai, <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 Pentti Haukkanen, 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 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 Mathematical Reflections, <a href="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.

%H 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 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 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 Jeffrey Shallit, <a href="http://www.jstor.org/stable/2321618">Problem E 2821</a>, American Mathematical Monthly 87 (1980), 220.

%H Jeffrey Shallit, <a href="http://www.jstor.org/stable/2321834">Solution</a>, American Mathematical Monthly, 88 (1981), 444-445.

%H Laszlo Toth, <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 Laszlo Toth, <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 Laszlo Toth, <a href="http://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 Laszlo Toth, <a href="http://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 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 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 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 a(n) = Sum_{d|n} d*phi(n/d), where phi(n) is Euler totient function (cf. A000010). - _Vladeta Jovovic_, Apr 04 2001

%F Multiplicative; for prime p, a(p^e) = p^(e-1)*((p-1)e+p).

%F Dirichlet g.f.: zeta(s-1)^2/zeta(s).

%F a(n) = Sum_{d|n} d*tau(d)*mu(n/d). - _Benoit Cloitre_, Oct 23 2003

%F Equals A054523 * [1,2,3,...]. Equals row sums of triangle A010766. - _Gary W. Adamson_, May 20 2007

%F 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 Equals row sums of triangle A127478. - _Gary W. Adamson_, Aug 03 2008

%F 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 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 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 a(2*n) = a(n)*(3-A007814(n)/(A007814(n)+2)) - _Velin Yanev_, Jun 30 2017

%F 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 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 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 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 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 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 a:=n->sum(igcd(n,j),j=1..n): seq(a(n), n=1..60); # _Zerinvary Lajos_, Nov 05 2006

%t 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 a[ n_] := If[ n < 1, 0, n Sum[ EulerPhi[d] / d, {d, Divisors@n}]]; (* _Michael Somos_, Jan 07 2017 *)

%t 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 (PARI) {a(n) = direuler(p=2, n, (1 - X) / (1 - p*X)^2)[n]}; /* _Michael Somos_, May 31 2000 */

%o (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 (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 (PARI) a(n) = sumdiv(n, d, n*eulerphi(d)/d); \\ _Michel Marcus_, Jan 07 2017

%o (Haskell)

%o a018804 n = sum $ map (gcd n) [1..n] -- _Reinhard Zumkeller_, Jul 16 2012

%o (Python)

%o from sympy.ntheory import totient, divisors

%o print([sum(n*totient(d)//d for d in divisors(n)) for n in range(1, 101)]) # _Indranil Ghosh_, Apr 04 2017

%o (Python)

%o from sympy import factorint

%o from math import prod

%o 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 (Magma) [&+[Gcd(n,k):k in [1..n]]:n in [1..60]]; // _Marius A. Burtea_, Nov 14 2019

%Y Column 1 of A343510 and A343516.

%Y 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 Cf. A185210, A010766, A054523, A127468, A050873, A078430, A095026, A227507, A000010, A344372, A272718 (partial sums), A368736 - A368741.

%K nonn,mult

%O 1,2

%A _David W. Wilson_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 04:13 EDT 2024. Contains 371235 sequences. (Running on oeis4.)