A068509 - OEIS

%I #24 Apr 12 2022 22:29:42

%S 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,

%T 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,

%U 12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12

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

%C 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

%C 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

%D R. K. Guy, Unsolved Problems in Number Theory, B26.

%H William Rex Marshall, <a href="/A068509/b068509.txt">Table of n, a(n) for n = 1..1000</a>

%H S. L. G. Choi, <a href="http://dx.doi.org/10.1112/S0025579300005684">The largest subset in [1, n] whose integers have pairwise l.c.m. not exceeding n</a>, Mathematika 19:2 (1972), pp. 221-230.

%H S. L. G. Choi, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa29/aa2922.pdf">The largest subset in [1,n] whose integers have pairwise l.c.m. not exceeding n, II</a>, Acta Arithmetica 29 (1976), pp. 105-111.

%H P. Erdos, <a href="http://www.renyi.hu/~p_erdos/1965-02.pdf">Extremal problems in number theory</a>, Proc. Sympos. Pure Math., Vol. VIII , pp. 181-191. (see p. 183)

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

%K nonn

%O 1,2

%A _Naohiro Nomoto_, Mar 12 2002

%E More terms from _Rob Pratt_, Feb 08 2010