%I #15 Apr 21 2024 00:22:11

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

%N 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.

%C 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.

%H Erdős Problems, <a href="https://www.erdosproblems.com/587">Erdős problem #587</a>

%H Hoi Nguyen and Van Vu, <a href="https://arxiv.org/abs/0811.1311">Squares in sumsets</a>, 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.

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

%e {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.

%e a(1) = 2: {2}

%e a(2) = 3: {2, 3}

%e a(3) = 5: {2, 3, 5}

%e a(4) = 8: {5, 6, 7, 8}

%e a(5) = 12: {3, 7, 8, 11, 12}

%e a(6) = 18: {2, 11, 13, 15, 17, 18}

%e a(7) = 22: {2, 13, 15, 17, 18, 20, 22}

%e a(8) = 34: {5, 6, 12, 17, 22, 23, 28, 34}

%e a(9) = 40: {6, 11, 17, 22, 23, 28, 29, 34, 40}

%e a(10) = 62: {6, 23, 29, 33, 37, 50, 54, 56, 60, 62}

%e a(11) = 76: {10, 13, 20, 33, 43, 46, 56, 59, 66, 69, 76}

%e a(12) = 85: {5, 14, 19, 33, 38, 47, 52, 61, 66, 71, 80, 85}

%e a(13) = 134: {11, 18, 29, 30, 47, 58, 65, 76, 87, 94, 105, 123, 134}

%o (PARI) do1(lim,startAt,v)=for(a=startAt,lim, for(i=1,#v, if(issquare(v[i]+a), next(2))); return([a])); 0

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

%o doexact(N,lim)=if(issquare(lim), return(0)); my(t=do(N-1,lim-1,2,[0,lim])); if(t, concat(t,lim),0)

%K nonn,hard,more

%O 1,1

%A _Charles R Greathouse IV_, Apr 16 2024

%E a(13) from _Charles R Greathouse IV_, Apr 21 2024