

A208746


Size of largest subset of [1..n] containing no three terms in geometric progression.


7



1, 2, 3, 3, 4, 5, 6, 7, 7, 8, 9, 10, 11, 12, 13, 13, 14, 14, 15, 15, 16, 17, 18, 19, 19, 20, 21, 21, 22, 23, 24, 24, 25, 26, 27, 27, 28, 29, 30, 31, 32, 33, 34, 34, 35, 36, 37, 38, 38, 38, 39, 39, 40, 41, 42, 43, 44, 45, 46, 46, 47, 48, 49, 49, 50, 51, 52, 52, 53, 54, 55, 55, 56, 57, 57, 57, 58, 59, 60, 61, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 71, 72, 73, 74, 74, 75, 75, 75, 75
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

All threeterm geometric progressions must be avoided, even those such as 4,6,9 whose ratio is not an integer.
David Applegate's computation used a floatingpoint IP solver for the packing subproblems, so although it's almost certainly correct there is no proof. First he enumerated geometric progressions using
for (i=1;i<=N;i++) {
for (j=2; j*j<=i; j++) {
if (i % (j*j) != 0) continue;
for (k=1; k<j; k++) {
print i*k*k/(j*j), i*k/j, i;
}
}
}
and then solved the integer program of maximizing the subset of {1..N} subject to not taking all 3 of any progression.


LINKS

Table of n, a(n) for n=1..100.
Index entries for nonaveraging sequences


MAPLE

# Maple program for computing the nth term from Robert Israel:
A:= proc(n)
local cons, x;
cons:=map(op, {seq(map(t > x[t]+x[b]+x[b^2/t]<=2,
select(t > (t<b) and (t>=b^2/n),
numtheory:divisors(b^2))), b=2..n1)});
Optimization:Maximize(add(x[i], i=1..n), cons, assume=binary)[1]
end proc;


CROSSREFS

Cf. A003002.
Sequence in context: A066508 A053207 A138467 * A230490 A247983 A127036
Adjacent sequences: A208743 A208744 A208745 * A208747 A208748 A208749


KEYWORD

nonn


AUTHOR

David Applegate and N. J. A. Sloane, Mar 01 2012


EXTENSIONS

a(1)a(82) confirmed by Robert Israel and extended to a(100), Mar 01 2012


STATUS

approved



