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,4

Links

Alois P. Heinz, Table of n, a(n) for n = 1..20000

Sebastian Karlsson, Formula for Prime Powers

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.

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

Prog

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

Crossrefs

Cf. A056789, A339387.

Sequence in context: A202851 A007650 A236540 * A165552 A067231 A218971

Adjacent sequences: A339381 A339382 A339383 * A339385 A339386 A339387

Keyword

nonn

Author

Sebastian Karlsson, Dec 02 2020

Status

approved