cp's OEIS Frontend

A339384 a(n) = Sum_{k=1..n} (lcm(n,k)/gcd(n,k) mod n).

%I A339384 #26 Dec 08 2020 15:48:35
%S A339384 0,1,1,3,1,6,1,11,10,13,1,28,1,24,30,51,1,57,1,89,52,58,1,120,51,81,
%T A339384 91,166,1,148,1,211,120,139,128,307,1,174,166,357,1,363,1,404,348,256,
%U A339384 1,544,148,403,282,565,1,588,271,714,352,409,1,822,1,468,652,915
%N A339384 a(n) = Sum_{k=1..n} (lcm(n,k)/gcd(n,k) mod n).
%H A339384 Alois P. Heinz, <a href="/A339384/b339384.txt">Table of n, a(n) for n = 1..20000</a>
%H A339384 Sebastian Karlsson, <a href="/A339384/a339384_1.pdf">Formula for Prime Powers</a>
%F A339384 a(n) = A056789(n) - n * Sum_{k=1..n} (floor(k / gcd(n,k)^2)).
%F A339384 a(p^2) = A056789(p) for prime number p.
%F A339384 a(n) = 0 iff n = 1.
%F A339384 a(n) = 1 iff n is a prime.
%F A339384 a(p^2) = 1 + p^2(p-1)/2, if p is a prime. Sketch of proof: for an arbitrary term "lcm(n,k)/gcd(n,k) mod n", this is clearly 0 if n and k are relatively prime. If it isn't 0, then k = p*r < n for 1 <= r < p or k = n. Hence, a(p^2) = 1 + p*Sum_{r=1..p-1} r. Hence, a(p^2) = 1 + p^2*(p-1)/2.
%F A339384 If p is a prime then:
%F A339384 a(p^(2*n)) = 1 + (1/2)*p^2*(p-1)*((p^(3*n)-1)/(p^3-1)+p^(3n-2)*(p^(n-1)-1)/(p-1))
%F A339384 a(p^(2*n+1)) = 1 + (1/2)*p^2*(p-1)*((p^(3*n)-1)/(p^3-1)+p^(3n-1)*(p^n-1)/(p-1))
%F A339384 See links for proof.
%p A339384 a:= n-> add(irem(n*k/igcd(n, k)^2, n), k=1..n):
%p A339384 seq(a(n), n=1..80);  # _Alois P. Heinz_, Dec 03 2020
%t A339384 a[n_] := Sum[Mod[LCM[n, k]/GCD[n, k], n], {k, 1, n}]; Array[a, 100] (* _Amiram Eldar_, Dec 03 2020 *)
%o A339384 (PARI) a(n) = sum(k=1, n, lcm(n,k)/gcd(n,k) % n); \\ _Michel Marcus_, Dec 02 2020
%Y A339384 Cf. A056789, A339387.
%K A339384 nonn
%O A339384 1,4
%A A339384 _Sebastian Karlsson_, Dec 02 2020