A356472 Numerator of the average of gcd(i,n) for i = 1..n.

1, 3, 5, 2, 9, 5, 13, 5, 7, 27, 21, 10, 25, 39, 3, 3, 33, 7, 37, 18, 65, 63, 45, 25, 13, 75, 3, 26, 57, 9, 61, 7, 35, 99, 117, 14, 73, 111, 125, 9, 81, 65, 85, 42, 21, 135, 93, 5, 19, 39, 55, 50, 105, 9, 189, 65, 185, 171, 117, 6, 121, 183, 13, 4, 45, 105, 133, 66, 75, 351, 141, 35, 145, 219, 13, 74, 39, 125, 157

Offset: 1

Author

Matthias Kaak, Aug 08 2022

Keywords

• easy
• frac
• nonn

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 and its numerator is a(3)=5.
		

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A356473 (denominators), A018804, A057661 (LCM).

Cf. A001620, A013661, A306016.

Programs

Haskell

map numerator (map (\i -> sum (map (\j -> gcd i j) [1..i]) % i) [1..])

Mathematica

Table[Numerator[Sum[GCD[I, j], {j, 1, I}]/I], {I, 100}]
f[p_, e_] := e*(p - 1)/p + 1; a[n_] := Numerator[Times @@ f @@@ FactorInteger[n]]; Array[a, 100] (* Amiram Eldar, Apr 28 2023 *)

PARI

a(n) = numerator(sum(i=1, n, gcd(i, n))/n); \\ Michel Marcus, Aug 08 2022

PARI

a(n,f=factor(n))=my(k=prod(i=1, #f~, (f[i, 2]*(f[i, 1]-1)/f[i, 1] + 1)*f[i, 1]^f[i, 2])); k/gcd(k,n) \\ Charles R Greathouse IV, Sep 08 2022

Python

from math import prod, gcd
from sympy import factorint
def A356472(n):
    f = factorint(n)
    return (m:=prod((p-1)*e+p for p, e in f.items()))//gcd(prod(f),m) # Chai Wah Wu, Sep 08 2022

Formula

a(n) = numerator(A018804(n)/n).

a(n) << n^(1+e) for any e > 0. a(n) > 1 for all n > 1. - Charles R Greathouse IV, Sep 08 2022

Sum_{k=1..n} a(k)/A356473(k) ~ (n/zeta(2)) * (log(n) + 2*gamma - 1 - zeta'(2)/zeta(2)), where gamma is Euler's constant (A001620). - Amiram Eldar, Dec 25 2024