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

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

Crossrefs

Sequence in context: A332220 A263089 A340611 * A070319 A057142 A320837

Adjacent sequences: A068506 A068507 A068508 * A068510 A068511 A068512

Keyword

nonn

Author

Naohiro Nomoto, Mar 12 2002

Extensions

More terms from Rob Pratt, Feb 08 2010

Status

approved