A182082 - OEIS

%I #34 Jan 21 2021 11:37:24

%S 1,3,5,8,10,15,17,21,24,29,31,39,41,46,51,56,58,66,68,76,81,86,88,99,

%T 102,107,111,119,121,135,137,143,148,153,158,171,173,178,183,194,196,

%U 210,212,220,228,233,235,249,252,260,265,273,275,286,291,302,307,312

%N Number of pairs, (x,y), with x >= y, whose LCM does not exceed n.

%C Note that this is the asymmetric count. If all pairs (x,y) are counted, A061503 is obtained. - _T. D. Noe_, Apr 10 2012

%H Walt Rorie-Baety, <a href="/A182082/b182082.txt">Table of n, a(n) for n = 1..1000</a>

%H Project Euler, <a href="https://projecteuler.net/problem=379">Problem 379: Least common multiple count</a>

%F a(n) = Sum_{k=1..n} (d(k^2)+1)/2, where d is the number of divisors function (A000005). - _Charles R Greathouse IV_, Apr 10 2012

%F a(n) = Sum_{k=1..n} A007875(k) * floor(n/k). - _Daniel Suteu_, Jan 08 2021

%e a(1000000) = 37429395, according to Project Euler problem #379.

%t Table[Count[Flatten[Table[LCM[i, j], {i, n}, {j, i, n}]], _?(# <= n &)], {n, 60}] (* _T. D. Noe_, Apr 10 2012 *)

%t nn = 100; (Accumulate[Table[DivisorSigma[0, n^2], {n, nn}]] + Range[nn])/2 (* _T. D. Noe_, Apr 10 2012 *)

%o (Haskell) a n = length [(x,y)| x <- [1..n], y <- [x..n], lcm x y <= n]

%o (PARI) a(n)=(sum(k=1,n,numdiv(k^2))+n)/2 \\ _Charles R Greathouse IV_, Apr 10 2012

%Y Cf. A018892, A061503 (symmetric case).

%K nonn

%O 1,2

%A _Walt Rorie-Baety_, Apr 10 2012