A356472 - OEIS

%I #47 Apr 28 2023 08:16:48

%S 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,

%T 26,57,9,61,7,35,99,117,14,73,111,125,9,81,65,85,42,21,135,93,5,19,39,

%U 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

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

%H Amiram Eldar, <a href="/A356472/b356472.txt">Table of n, a(n) for n = 1..10000</a>

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

%F a(n) << n^(1+e) for any e > 0. a(n) > 1 for all n > 1. - _Charles R Greathouse IV_, Sep 08 2022

%e 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.

%t Table[Numerator[Sum[GCD[I, j], {j, 1, I}]/I], {I, 100}]

%t f[p_, e_] := e*(p - 1)/p + 1; a[n_] := Numerator[Times @@ f @@@ FactorInteger[n]]; Array[a, 100] (* _Amiram Eldar_, Apr 28 2023 *)

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

%o (PARI) a(n) = numerator(sum(i=1, n, gcd(i, n))/n); \\ _Michel Marcus_, Aug 08 2022

%o (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

%o (Python)

%o from math import prod, gcd

%o from sympy import factorint

%o def A356472(n):

%o     f = factorint(n)

%o     return (m:=prod((p-1)*e+p for p, e in f.items()))//gcd(prod(f),m) # _Chai Wah Wu_, Sep 08 2022

%Y Cf. A356473 (denominators), A018804.

%Y Cf. A057661 (LCM).

%K easy,frac,nonn

%O 1,2

%A _Matthias Kaak_, Aug 08 2022