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
KEYWORD
nonn
AUTHOR
Sebastian Karlsson, Dec 02 2020
STATUS
approved