|
|
A006579
|
|
a(n) = Sum_{k=1..n-1} gcd(n,k).
(Formerly M0941)
|
|
14
|
|
|
0, 1, 2, 4, 4, 9, 6, 12, 12, 17, 10, 28, 12, 25, 30, 32, 16, 45, 18, 52, 44, 41, 22, 76, 40, 49, 54, 76, 28, 105, 30, 80, 72, 65, 82, 132, 36, 73, 86, 140, 40, 153, 42, 124, 144, 89, 46, 192, 84, 145, 114, 148, 52, 189, 134, 204, 128, 113, 58, 300, 60, 121, 210, 192
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
This sequence for a(n) also arises in the following context. If f(x) is a monic univariate polynomial of degree d>1 over Zn (= Z/nZ, the ring of integers modulo n), and we let X be the number of distinct roots of f(x) in Zn taken over all n^d choices for f(x), then the variance Var[X] = a(n)/n and the expected value E[X] = 1. - Michael Monagan, Sep 11 2015
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
FORMULA
|
a(p) = p-1 for a prime p.
a(n+2) = Sum_{k=0..n} gcd(n-k+1, k+1) = -Sum_{k=0..4n+2} gcd(4n-k+3, k+1)*(-1)^k/4. - Paul Barry, May 03 2005
G.f.: Sum_{k>=1} phi(k) * x^(2*k) / (1 - x^k)^2. - Ilya Gutkovskiy, Feb 06 2020
a(p^k) = k(p-1)p^(k-1) for prime p. - Chai Wah Wu, May 15 2022
|
|
EXAMPLE
|
a(12) = gcd(12,1) + gcd(12,2) + ... + gcd(12,11) = 1 + 2 + 3 + 4 + 1 + 6 + 1 + 4 + 3 + 2 + 1 = 28.
|
|
MAPLE
|
a:= n-> add(igcd(n, k), k=1..n-1):
seq(a(n), n=1..64);
|
|
MATHEMATICA
|
f[n_] := Sum[ GCD[n, k], {k, 1, n - 1}]; Table[ f[n], {n, 1, 60}]
f[p_, e_] := (e*(p - 1)/p + 1)*p^e; a[n_] := Times @@ f @@@ FactorInteger[n] - n; Array[a, 100] (* Amiram Eldar, Apr 26 2023 *)
|
|
PROG
|
(Python)
from math import prod
from sympy import factorint
def A006579(n): return prod(p**(e-1)*((p-1)*e+p) for p, e in factorint(n).items()) - n # Chai Wah Wu, May 15 2022
|
|
CROSSREFS
|
Antidiagonal sums of array A003989.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Corrected by Ron Lalonde (ronronronlalonde(AT)hotmail.com), Oct 24 2002
|
|
STATUS
|
approved
|
|
|
|