|
| |
|
|
A018804
|
|
Pillai's arithmetical function: sum of gcd(k, n) for 1 <= k <= n.
|
|
42
|
|
|
|
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
a(n) is the 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. [From Gary W. Adamson, Aug 27 2008]
|
|
|
REFERENCES
|
Antal Bege, Hadamard product of GCD matrices, Acta Univ. Sapientiae, Mathematica, 1, 1 (2009) 43-49
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.
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 (zerinvarylajos(AT)yahoo.com), 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
|
|
|
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.
Sequence in context: A137319 A138808 A185456 * A032682 A022769 A067241
Adjacent sequences: A018801 A018802 A018803 * A018805 A018806 A018807
|
|
|
KEYWORD
|
nonn,mult,changed
|
|
|
AUTHOR
|
David W. Wilson
|
|
|
STATUS
|
approved
|
| |
|
|
