A372040 Smallest k such that there is an n-element subset of {1, 2, ..., k} that does not contain a (nonempty) subset that sums to a square.

2, 3, 5, 8, 12, 18, 22, 34, 40, 62, 76, 85, 134

Offset

1,1

Comments

Erdős showed that a(n) << n^3. Nguyen & Vu showed that there is some k such that n^3/log^k n << a(n), showing that the Erdős bound is optimal up to log factors.

Links

Table of n, a(n) for n=1..13.

Erdős Problems, Erdős problem #587

Hoi Nguyen and Van Vu, Squares in sumsets, arXiv:0811.1311 [math.CO], 2008-2009; In: Bárány, I., Solymosi, J., Sági, G. (eds) An Irregular Mind. Bolyai Society Mathematical Studies, vol 21. Springer, Berlin, Heidelberg.

Formula

n^3/log^k n << a(n) << n^3 for some constant k.

Example

{1} is not a valid choice for n = 1 since 1 is a square. {2, 3, 5, 6} is not a valid choice for n = 4 since 3+6 is a square.
a(1) = 2: {2}
a(2) = 3: {2, 3}
a(3) = 5: {2, 3, 5}
a(4) = 8: {5, 6, 7, 8}
a(5) = 12: {3, 7, 8, 11, 12}
a(6) = 18: {2, 11, 13, 15, 17, 18}
a(7) = 22: {2, 13, 15, 17, 18, 20, 22}
a(8) = 34: {5, 6, 12, 17, 22, 23, 28, 34}
a(9) = 40: {6, 11, 17, 22, 23, 28, 29, 34, 40}
a(10) = 62: {6, 23, 29, 33, 37, 50, 54, 56, 60, 62}
a(11) = 76: {10, 13, 20, 33, 43, 46, 56, 59, 66, 69, 76}
a(12) = 85: {5, 14, 19, 33, 38, 47, 52, 61, 66, 71, 80, 85}
a(13) = 134: {11, 18, 29, 30, 47, 58, 65, 76, 87, 94, 105, 123, 134}

Prog

(PARI) do1(lim, startAt, v)=for(a=startAt, lim, for(i=1, #v, if(issquare(v[i]+a), next(2))); return([a])); 0
do(N, lim, startAt=2, v=[0])=lim\=1; if(N==1, return(do1(lim, startAt, v))); for(a=startAt, lim-N+1, my(u=List()); for(i=1, #v, my(t=v[i]+a); if(issquare(t), next(2)); listput(u, t)); my(t=do(N-1, lim, a+1, Set(concat(v, Vec(u))))); if(t, return(concat(a, t)))); 0
doexact(N, lim)=if(issquare(lim), return(0)); my(t=do(N-1, lim-1, 2, [0, lim])); if(t, concat(t, lim), 0)

Crossrefs

Sequence in context: A111388 A127884 A105858 * A299731 A252864 A039899

Adjacent sequences: A372037 A372038 A372039 * A372041 A372042 A372043

Keyword

nonn,hard,more

Author

Charles R Greathouse IV, Apr 16 2024

Extensions

a(13) from Charles R Greathouse IV, Apr 21 2024

Status

approved