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

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, 91, 166, 1, 148, 1, 211, 120, 139, 128, 307, 1, 174, 166, 357, 1, 363, 1, 404, 348, 256, 1, 544, 148, 403, 282, 565, 1, 588, 271, 714, 352, 409, 1, 822, 1, 468, 652, 915

Offset: 1

Author

Sebastian Karlsson, Dec 02 2020

Keywords

• nonn

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..20000
• Sebastian Karlsson, Formula for Prime Powers

Crossrefs

Cf. A056789, A339387.

Programs

Maple

a:= n-> add(irem(n*k/igcd(n, k)^2, n), k=1..n):
seq(a(n), n=1..80);  # Alois P. Heinz, Dec 03 2020

Mathematica

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

PARI

a(n) = sum(k=1, n, lcm(n,k)/gcd(n,k) % n); \\ Michel Marcus, Dec 02 2020

Formula

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

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

a(n) = 0 iff n = 1.

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

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.

If p is a prime then:

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

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

See links for proof.