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

1, 3, 5, 8, 10, 15, 17, 21, 24, 29, 31, 39, 41, 46, 51, 56, 58, 66, 68, 76, 81, 86, 88, 99, 102, 107, 111, 119, 121, 135, 137, 143, 148, 153, 158, 171, 173, 178, 183, 194, 196, 210, 212, 220, 228, 233, 235, 249, 252, 260, 265, 273, 275, 286, 291, 302, 307, 312

Offset: 1

Author

Walt Rorie-Baety, Apr 10 2012

Keywords

• nonn

Comments

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

Examples

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

Links

• Walt Rorie-Baety, Table of n, a(n) for n = 1..1000
• Project Euler, Problem 379: Least common multiple count.

Crossrefs

Partial sums of A018892.

Cf. A000005, A007875, A013661, A061503 (symmetric case).

Programs

Haskell

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

Mathematica

Table[Count[Flatten[Table[LCM[i, j], {i, n}, {j, i, n}]], ?(# <= n &)], {n, 60}] (* _T. D. Noe, Apr 10 2012 *)
nn = 100; (Accumulate[Table[DivisorSigma[0, n^2], {n, nn}]] + Range[nn])/2 (* T. D. Noe, Apr 10 2012 *)

PARI

a(n)=(sum(k=1,n,numdiv(k^2))+n)/2 \\ Charles R Greathouse IV, Apr 10 2012

Formula

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

a(n) = Sum_{k=1..n} A007875(k) * floor(n/k). - Daniel Suteu, Jan 08 2021

a(n) ~ n * log(n)^2 /(4*zeta(2)) (see A018892 for a more accurate asymptotic formula). - Amiram Eldar, Feb 01 2025