A339387 - OEIS

%I #44 Dec 25 2020 10:15:17

%S 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,

%T 1,148,1,19,120,139,93,55,1,174,88,157,1,279,1,184,168,256,1,160,1,

%U 303,282,97,1,372,106,266,181,409,1,582,1,468,211,19,285,763,1

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

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

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

%C 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.

%H Michel Marcus, <a href="/A339387/b339387.txt">Table of n, a(n) for n = 1..10000</a>

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

%F 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.

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

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

%p a:= n-> add(irem(n*k/igcd(n, k)^2, k), k=1..n):

%p seq(a(n), n=1..80);  # _Alois P. Heinz_, Dec 03 2020

%t Table[Sum[Mod[LCM[n,k]/GCD[n,k],k],{k,n}],{n,67}] (* _Stefano Spezia_, Dec 02 2020 *)

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

%Y Cf. A056789, A339384, A006881.

%K nonn

%O 1,6

%A _Sebastian Karlsson_, Dec 02 2020

%E More terms from _Stefano Spezia_, Dec 02 2020