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

0, 1, 1, 1, 1, 6, 1, 3, 1, 13, 1, 16, 1, 24, 30, 3, 1, 39, 1, 29, 31, 58, 1, 72, 1, 81, 10, 82, 1, 148, 1, 19, 120, 139, 93, 55, 1, 174, 88, 157, 1, 279, 1, 184, 168, 256, 1, 160, 1, 303, 282, 97, 1, 372, 106, 266, 181, 409, 1, 582, 1, 468, 211, 19, 285, 763, 1

Offset: 1

Author

Sebastian Karlsson, Dec 02 2020

Keywords

• nonn

Comments

n divides a(n) iff n divides A339384(n) iff n divides A056789(n). For proof, consider the formulas for a(n) and A339384(n).

Conjecture: If a(n) = A339384(n), then n is squarefree. This appears to be true for at least the first 2000 terms.

If n is a squarefree semiprime (A006881), then a(n) = A339384(n) iff the smaller prime factor of n divides its larger prime factor + 1.

Links

• Michel Marcus, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A056789, A339384, A006881.

Programs

Maple

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

Mathematica

Table[Sum[Mod[LCM[n,k]/GCD[n,k],k],{k,n}],{n,67}] (* Stefano Spezia, Dec 02 2020 *)

PARI

a(n) = sum(k=1, n, n*k/gcd(n, k)^2 % k); \\ Michel Marcus, Dec 09 2020

Formula

a(p) = a(p^2) = 1 for prime p.

If n>4, then a(n) = A056789(n) - n * Sum_{k=1..floor(n/2)} floor(n/(gcd(n,k)^2)). For proof, just rewrite "mod" in terms of the floor-function, use the formulas lcm(n,k)*gcd(n,k) = n*k and gcd(n, k) = gcd(n, n-k) and split the sum into two equal parts.

If p is a prime and p>2, then a(2*p) = A339384(2*p) = 3 + p*(p-1)/2.

If p is prime then a(p^(2*n)) = a(p^(2*n-1)) = 1 + (1/2)*p^2*(p-1)*(p^(3*n-3)-1)/(p^3-1). In particular, a(p^(2*n+2)) = a(p^(2*n+1)) = A056789(p^n). This can be proved in a very similar fashion as the corresponding formulas of A339384(p^n) and A056789(p^n).

Extensions

More terms from Stefano Spezia, Dec 02 2020