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

%I #26 Dec 08 2020 15:48:35

%S 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 91,166,1,148,1,211,120,139,128,307,1,174,166,357,1,363,1,404,348,256,

%U 1,544,148,403,282,565,1,588,271,714,352,409,1,822,1,468,652,915

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

%H Alois P. Heinz, <a href="/A339384/b339384.txt">Table of n, a(n) for n = 1..20000</a>

%H Sebastian Karlsson, <a href="/A339384/a339384_1.pdf">Formula for Prime Powers</a>

%F a(n) = A056789(n) - n * Sum_{k=1..n} (floor(k / gcd(n,k)^2)).

%F a(p^2) = A056789(p) for prime number p.

%F a(n) = 0 iff n = 1.

%F a(n) = 1 iff n is a prime.

%F 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 If p is a prime then:

%F 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 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 See links for proof.

%p a:= n-> add(irem(n*k/igcd(n, k)^2, n), k=1..n):

%p seq(a(n), n=1..80); # _Alois P. Heinz_, Dec 03 2020

%t a[n_] := Sum[Mod[LCM[n, k]/GCD[n, k], n], {k, 1, n}]; Array[a, 100] (* _Amiram Eldar_, Dec 03 2020 *)

%o (PARI) a(n) = sum(k=1, n, lcm(n,k)/gcd(n,k) % n); \\ _Michel Marcus_, Dec 02 2020

%Y Cf. A056789, A339387.

%K nonn

%O 1,4

%A _Sebastian Karlsson_, Dec 02 2020