A339387 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,6

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

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

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

PROG

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

CROSSREFS

Cf. A056789, A339384, A006881.

Sequence in context: A290101 A102419 A352891 * A074193 A074453 A069608

Adjacent sequences: A339384 A339385 A339386 * A339388 A339389 A339390

KEYWORD

nonn

AUTHOR

Sebastian Karlsson, Dec 02 2020

EXTENSIONS

More terms from Stefano Spezia, Dec 02 2020

STATUS

approved