login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A018804 Pillai's arithmetical function: sum of gcd(k, n) for 1 <= k <= n. 44
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

REFERENCES

Antal Bege, Hadamard product of GCD matrices, Acta Univ. Sapientiae, Mathematica, 1, 1 (2009) 43-49.

Olivier Bordelles, An Asymptotic Formula for Short Sums of Gcd-Sum Functions, Journal of Integer Sequences, Vol. 15 (2012), #12.6.8.

S. S. Pillai, On an arithmetic function, J. Annamalai University 2 (1933), pp. 243-248.

J. Sándor, A generalized Pillai function, Octogon M.M. 9 No.2 (2001), 746-748.

Jeffrey Shallit, Problem E 2821, American Mathematical Monthly 87 (1980), 220. Solution in American Mathematical Monthly, 88 (1981), 444-445.

L. Toth, Weighted Gcd-Sum Functions, Journal of Integer Sequences, 14 (2011), #11.7.7.

LINKS

T. D. Noe, Table of n, a(n) for n = 1..2000

Kevin A. Broughan, The gcd-sum function, Journal of Integer Sequences 4 (2001), Article 01.2.2, 19 pp.

Soichi Ikeda and Kaneaki Matsuoka, On the Lcm-Sum Function, Journal of Integer Sequences, Vol. 17 (2014), Article 14.1.7.

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

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

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

PROG

(PARI) a(n)=direuler(p=2, n, (1-X)/(1-p*X)^2)[n]

(Haskell)

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

(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

CROSSREFS

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.

Cf. A050873, A078430.

Sequence in context: A137319 A138808 A185456 * A032682 A022769 A067241

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 | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified August 28 03:32 EDT 2014. Contains 246160 sequences.