cp's OEIS Frontend

For prime p, a(p) = 1 + p^2*(p-1)/2.

We note lcm(k,n) = k*n iff gcd(k,n) = 1 (and in general lcm(k,n) equals k*n/gcd(k,n)), and so for these values LCM/GCD = k*n. From A023896, we have that Sum_{k=1..n-1: gcd(k,n)=1} k = n*phi(n)/2, and so Sum_{k=1..n-1: gcd(k,n)=1} k*n = n * Sum_{k=1..n-1: gcd(k,n)=1} k = n^2*phi(n)/2. As this is true, certainly Sum_{k=1..n} lcm(k,n)/gcd(k,n) > n^2*phi(n)/2. - Jon Perry, Nov 09 2014 [Edited by Petros Hadjicostas, May 27 2020]

Conjecture: for prime p, a(p^n) = 1 + (1/2)*(p - 1)*p^2*(p^(3*n) - 1)/(p^3 - 1) for n = 1,2,3,.... Cf. A339384. - Peter Bala, Dec 04 2020

The conjecture can be proven by splitting up the sum like this: a(p^n) = 1 + Sum_{1 <= r < p^n if gcd(p,r) = 1} lcm(p^n,r)/gcd(p^n,r) + Sum_{1 <= r < p^(n-1) if gcd(p,r) = 1} lcm(p^n,p*r)/gcd(p^n,p*r) + … + Sum_{1 <= r < p if gcd(p,r) = 1} lcm(p^n,p^(n-1)*r)/gcd(p^n,p^(n-1)*r) = 1 + Sum_{1 <= r < p^n if gcd(p,r) = 1} p^n*r + Sum_{1 <= r < p^(n-1) if gcd(p,r) = 1} p^(n-1)*r + … + Sum_{1 <= r < p if gcd(p,r) = 1} p*r = 1 + p^n*(1/2)*p^n*phi(p^n) + p^(n-1)*(1/2)*p^(n-1)*phi(p^(n-1)) + … + p*(1/2)*p*phi(p) = 1 + (1/2)*(p-1)*Sum_{k=1..n} p^(3k-1) = 1 + (1/2)*(p-1)*p^2*(p^(3*n)-1)/(p^3-1). - Sebastian Karlsson, Dec 07 2020

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.