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
Thomas Bloom, Problem 587, Erdős Problems.
Erdős problems database contributors, Erdős problem database, see no. 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