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,2

Comments

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

Links

Walt Rorie-Baety, Table of n, a(n) for n = 1..1000

Project Euler, Problem 379: Least common multiple count

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

Example

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

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

Prog

(Haskell) a n = length [(x, y)| x <- [1..n], y <- [x..n], lcm x y <= n]
(PARI) a(n)=(sum(k=1, n, numdiv(k^2))+n)/2 \\ Charles R Greathouse IV, Apr 10 2012

Crossrefs

Cf. A018892, A061503 (symmetric case).

Sequence in context: A024679 A187973 A190488 * A117467 A310025 A133097

Adjacent sequences: A182079 A182080 A182081 * A182083 A182084 A182085

Keyword

nonn

Author

Walt Rorie-Baety, Apr 10 2012

Status

approved