A356473 Denominator of the average of gcd(i,n) for i = 1..n.
1, 2, 3, 1, 5, 2, 7, 2, 3, 10, 11, 3, 13, 14, 1, 1, 17, 2, 19, 5, 21, 22, 23, 6, 5, 26, 1, 7, 29, 2, 31, 2, 11, 34, 35, 3, 37, 38, 39, 2, 41, 14, 43, 11, 5, 46, 47, 1, 7, 10, 17, 13, 53, 2, 55, 14, 57, 58, 59, 1, 61, 62, 3, 1, 13, 22, 67, 17, 23, 70, 71, 6, 73, 74, 3, 19, 11, 26, 79, 5, 3, 82, 83, 21, 85, 86, 29
Offset: 1
Examples
For n = 3, the average of the gcd's is (gcd(1,3) + gcd(2,3) + gcd(3,3))/3 = (1 + 1 + 3)/3 = 5/3 which has denominator a(3)=3.
Links
- Robert Israel, Table of n, a(n) for n = 1..10000
Programs
-
Haskell
map denominator (map (\i -> sum (map (\j -> gcd i j) [1..i]) % i) [1..])
-
Maple
f:= proc(n) local i; denom(add(igcd(i,n),i=1..n)/n) end proc: map(f, [$1..100]); # Robert Israel, Dec 29 2022
-
Mathematica
Table[Denominator[Sum[GCD[I, j], {j, 1, I}]/I], {I, 100}] f[p_, e_] := e*(p - 1)/p + 1; a[n_] := Denominator[Times @@ f @@@ FactorInteger[n]]; Array[a, 100] (* Amiram Eldar, Apr 28 2023 *) -
PARI
a(n) = denominator(sum(i=1, n, gcd(i, n))/n); \\ Michel Marcus, Aug 08 2022
-
PARI
a(n,f=factor(n))=n/gcd(prod(i=1, #f~, (f[i, 2]*(f[i, 1]-1)/f[i, 1] + 1)*f[i, 1]^f[i, 2]),n) \\ Charles R Greathouse IV, Sep 08 2022
-
Python
from math import gcd, prod from sympy import factorint def A356473(n): return (p:=prod(f:=factorint(n)))//gcd(p,prod((p-1)*e+p for p, e in f.items())) # Chai Wah Wu, Sep 08 2022
Formula
a(n) = denominator of A018804(n)/n.
a(n) divides n, so in particular a(n) <= n. - Charles R Greathouse IV, Sep 08 2022
Comments