A348061 - OEIS

%I #15 Nov 18 2022 08:31:04

%S 1,1,4,3,16,4,36,11,34,16,100,12,144,36,64,43,256,34,324,48,144,100,

%T 484,44,396,144,304,108,784,64,900,171,400,256,576,102,1296,324,576,

%U 176,1600,144,1764,300,544,484,2116,172,1758,396,1024,432,2704,304,1600,396,1296,784,3364,192

%N a(n) = Sum_{k=1..n, gcd(n,k) = 1} n / gcd(n,k-1).

%H Seiichi Manyama, <a href="/A348061/b348061.txt">Table of n, a(n) for n = 1..10000</a>

%F Multiplicative with a(p^e) = (p^(2*e+1) - (p + 1) * p^(2*e-1) + 1) / (p + 1).

%F Sum_{k=1..n} a(k) ~ c * n^3, where c = (1/3) * Product_{p prime} (1 - 1/p^2 - 1/(1 + p + p^2)) = 0.1381393084... . - _Amiram Eldar_, Nov 18 2022

%t Table[Sum[If[GCD[n, k] == 1, n/GCD[n, k - 1], 0], {k, n}], {n, 60}]

%t f[p_, e_] := (p^(2 e + 1) - (p + 1) p^(2 e - 1) + 1)/(p + 1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 60]

%o (PARI) a(n) = sum(k=1, n, if (gcd(n, k)==1, n/gcd(n, k-1))); \\ _Michel Marcus_, Sep 27 2021

%Y Cf. A057660, A062355, A348060.

%K nonn,mult

%O 1,3

%A _Ilya Gutkovskiy_, Sep 26 2021