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
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
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