cp's OEIS Frontend

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

%I A068509 #24 Apr 12 2022 22:29:42
%S A068509 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 A068509 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 A068509 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 A068509 a(n) = maximum length of a subset in {1,..,n} whose integers have pairwise LCM not exceeding n.
%C A068509 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 A068509 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 A068509 R. K. Guy, Unsolved Problems in Number Theory, B26.
%H A068509 William Rex Marshall, <a href="/A068509/b068509.txt">Table of n, a(n) for n = 1..1000</a>
%H A068509 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 A068509 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 A068509 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 A068509 (3*sqrt(n))/(2*sqrt(2)) - 2 < a(n) <= 1.638*sqrt(n). - P. Erdos and S. L. G. Choi
%K A068509 nonn
%O A068509 1,2
%A A068509 _Naohiro Nomoto_, Mar 12 2002
%E A068509 More terms from _Rob Pratt_, Feb 08 2010