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

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

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.

Index entries for non-averaging sequences

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

Cf. A003002.

Sequence in context: A053207 A334714 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