A210380 Consider all n-tuples of distinct positive integers for which no two different elements add up to a square. This sequence gives the smallest maximal integer in such tuples.

1, 2, 4, 6, 9, 10, 11, 15, 18, 20, 21, 24, 26, 28, 32, 34, 36, 38, 40, 42, 50, 52, 54, 56, 58, 60, 62, 64, 72, 74, 76, 78, 80, 82, 84, 86, 88, 99, 101, 103, 105, 107, 109, 111, 114, 116, 118, 129, 130, 133, 135, 137, 139, 141, 143, 145, 152, 159, 160, 163, 167

Offset: 1

Author

Charles R Greathouse IV, Mar 27 2012

Keywords

• nonn
• nice

Examples

			For a(29)=72 one sequence is 8, 10, 12, 14, 19, 21, 23, 25, 27, 29, 31, 32, 34, 36, 38, 40, 42, 44, 46, 48, 51, 53, 55, 57, 59, 61, 63, 65, 72. - _Giovanni Resta_, Dec 24 2012
The above example sequence is the lexicographically first 29-tuple of distinct positive integers for which no two different elements add up to a square and the maximal integer is a(29). For such sequences for a(1)..a(100), see the "Lexicographically first sequences for n = 1..100" link. - _Jon E. Schoenfield_, Jan 31 2014
		

References

• J. P. Massias, Sur les suites dont les sommes des termes 2 à 2 ne sont pas des carrés, Publications du département de mathématiques de Limoges, 1982.

Links

• Giovanni Resta, Table of n, a(n) for n = 1..175 (first 100 terms from Jon E. Schoenfield)
• Ayman Khalfalah, Sachin Lodha, and Endre Szemerédi, Tight bound for the density of sequence of integers the sum of no two of which is a perfect square, Discr. Math. 256 (2002) 243 [DOI]
• J. C. Lagarias, A. M. Odlyzko, J. B. Shearer, On the density of sequences of integers the sum of no two of which is a square. I. Arithmetic progressions, Journal of Combinatorial Theory. Series A, 33 (1982), pp. 167-185.
• J. C. Lagarias, A. M. Odlyzko, J. B. Shearer, On the density of sequences of integers the sum of no two of which is a square. II. General sequences, Journal of Combinatorial Theory. Series A, 34 (1983), pp. 123-139.
• Jon E. Schoenfield, Lexicographically first sequences for n = 1..100
• Jon E. Schoenfield, Excel/VBA macro

Crossrefs

See A099107 for another version.

Cf. A210570 (no two elements differ by a square).

Programs

Mathematica

CZ[v_List] :=
   Block[{u = Most[v]}, If[Length[u] > 0 && Last[u] == 0, CZ[u], u]]
ev[v_List] := ev[v] =
   Module[{h = Plus @@ v, u = v}, If[h < 2, h, h = ev[CZ[u]];
    For[k = Floor[Sqrt[Length[u]]] + 1, k < Sqrt[2*Length[u]], k++,
     u[[k^2 - Length[u]]] = 0]; Max[h, 1 + ev[CZ[u]]]]]
a[n_] := Module[{k = n, t}, While[True, t = ev[Table[1, {k}]];
   If[t == n, Return[k], k += n - t]]]

PARI

most(v)=my(h=sum(i=1,#v,v[i]),m,u);if(h<2,return(h));m=#v;while(v[m]==0,m--);u=vector(m-1,i,v[i]);h=most(u);for(k=sqrtint(m)+1,sqrtint(2*m-1),u[k^2-m]=0);max(h,1+most(u))
a(n)=my(k=n,t);while(1,t=most(vector(k,i,1));if(t==n,return(k));k+=n-t)

Formula

a(n) ~ (32/11)*n.

a(n) <= (32/11)*n - 2. Erdős conjectured that a(n) >= (32/11)*n - k for some fixed k.

Extensions

a(25)-a(29) from Giovanni Resta, Dec 24 2012

More terms from Jon E. Schoenfield, Dec 28 2013