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,2

Links

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

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

Example

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.

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

Prog

(Haskell) map numerator (map (\i -> sum (map (\j -> gcd i j) [1..i]) % i) [1..])
(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

Crossrefs

Cf. A356473 (denominators), A018804.

Cf. A057661 (LCM).

Sequence in context: A322982 A275846 A273668 * A245653 A209748 A065172

Adjacent sequences: A356469 A356470 A356471 * A356473 A356474 A356475

Keyword

easy,frac,nonn

Author

Matthias Kaak, Aug 08 2022

Status

approved