A068509 a(n) = maximum length of a subset in {1,..,n} whose integers have pairwise LCM not exceeding n.

1, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12

Offset: 1

Author

Naohiro Nomoto, Mar 12 2002

Keywords

• nonn

Comments

Can be formulated as a maximum independent set problem and solved using integer linear programming: maximize Sum_{i=1..n} x(i) subject to x(i) + x(j) <= 1 for all i < j with lcm(i,j) > n, x(i) in {0,1} for all i. - Rob Pratt, Feb 08 2010

First differs from A070319 when n = 336, due to the set of 21 elements {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 21, 24, 30, 36, 42, 48} where each pair of elements has lcm <= 336, while no positive integer <= 336 has more than 20 divisors. Therefore A068509(336) = 21 and A070319(336) = 20. - William Rex Marshall, Sep 11 2012

References

• R. K. Guy, Unsolved Problems in Number Theory, B26.

Links

• William Rex Marshall, Table of n, a(n) for n = 1..1000
• S. L. G. Choi, The largest subset in [1, n] whose integers have pairwise l.c.m. not exceeding n, Mathematika 19:2 (1972), pp. 221-230.
• S. L. G. Choi, The largest subset in [1,n] whose integers have pairwise l.c.m. not exceeding n, II, Acta Arithmetica 29 (1976), pp. 105-111.
• P. Erdos, Extremal problems in number theory, Proc. Sympos. Pure Math., Vol. VIII , pp. 181-191. (see p. 183)

Formula

(3*sqrt(n))/(2*sqrt(2)) - 2 < a(n) <= 1.638*sqrt(n). - P. Erdos and S. L. G. Choi

Extensions

More terms from Rob Pratt, Feb 08 2010