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

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 59th year, we have over 358,000 sequences, and we’ve crossed 10,300 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A018804 Pillai's arithmetical function: Sum_{k=1..n} gcd(k, n). 128
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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

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

Number of non-congruent solutions to xy == 0 (mod n). - Yuval Dekel (dekelyuval(AT)hotmail.com), Oct 06 2003

Equals row sums of triangle A127375. - Gary W. Adamson, Aug 27 2008

n>1 divides a(n)+1 iff n is prime. - Thomas Ordowski, Oct 22 2014

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

{a(n)} == 1, 3, 1, 0, 1, 3, 1, 0, ... (mod 4). - Isaac Saffold, Dec 30 2017

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

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

T. D. Noe and 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 Cesaro 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. Katai, Some remarks on a paper of L. Toth, JIS 13 (2010) 10.1.2.

Pentti Haukkanen, 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.

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.

Jeffrey Shallit, Problem E 2821, American Mathematical Monthly 87 (1980), 220.

Jeffrey Shallit, Solution, American Mathematical Monthly, 88 (1981), 444-445.

Laszlo Toth, A gcd-sum function over regular integers modulo n, JIS 12 (2009) 09.2.5.

Laszlo Toth, On the Bi-Unitary Analogues of Euler's Arithmetical Function and the Gcd-Sum Function, JIS 12 (2009) 09.5.2.

Laszlo Toth, A survey of gcd-sum functions, J. Integer Sequences 13 (2010), Article 10.8.1, 23 pp.

Laszlo Toth, 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.

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 A054523 * [1,2,3,...]. Equals row sums of triangle A010766. - Gary W. Adamson, May 20 2007

Equals Mobius transform of A029935 = A054525 * (1, 2, 4, 5, 8, 8, 12, 12, ...). - Gary W. Adamson, Aug 02 2008

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

a(2*n) = a(n)*(3-A007814(n)/(A007814(n)+2)) - Velin Yanev, Jun 30 2017

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

EXAMPLE

G.f. = x + 3*x^2 + 5*x^3 + 8*x^4 + 9*x^5 + 15*x^6 + 13*x^7 + 20*x^8 + ...

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 *)

PROG

(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

(Haskell)

a018804 n = sum $ map (gcd n) [1..n] -- Reinhard Zumkeller, Jul 16 2012

(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

(Magma) [&+[Gcd(n, k):k in [1..n]]:n in [1..60]]; // Marius A. Burtea, Nov 14 2019

CROSSREFS

Column 1 of A343510 and A343516.

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))).

Cf. A185210, A010766, A054523, A127468, A127375, A050873, A078430, A095026, A227507, A000010.

Sequence in context: A185456 A308405 A331314 * A032682 A022769 A343114

Adjacent sequences: A018801 A018802 A018803 * A018805 A018806 A018807

KEYWORD

nonn,mult

AUTHOR

David W. Wilson

STATUS

approved

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 November 29 07:12 EST 2022. Contains 358422 sequences. (Running on oeis4.)