OFFSET

1,2

COMMENTS

All three-term geometric progressions must be avoided, even those such as 4,6,9 whose ratio is not an integer.

David Applegate's computation used a floating-point 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

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..125

K. O'Bryant, Sets of Natural Numbers with Proscribed Subsets, J. Int. Seq. 18 (2015) # 15.7.7.

MAPLE

# Maple program for computing the n-th 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..n-1)});

Optimization:-Maximize(add(x[i], i=1..n), cons, assume=binary)[1]

end proc;

MATHEMATICA

a[n_] := a[n] = If[n <= 2, n, Module[{cons, x}, cons = And @@ Flatten@ Rest@ Union@ Table[x[#] + x[b] + x[b^2/#] <= 2& /@ Select[Divisors[b^2], # < b && # >= b^2/n&], {b, 2, n-1}]; Maximize[{Sum[x[i], {i, 1, n}], cons && AllTrue[Array[x, n], 0 <= # <= 1&]}, Array[x, n], Integers]][[1]]];

Reap[For[n = 1, n <= 100, n++, Print[n, " ", a[n]]; Sow[a[n]]]][[2, 1]] (* Jean-François Alcover, May 18 2023, after Robert Israel *)

CROSSREFS

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