A210570 Consider all sequences of n distinct positive integers for which no two different elements have a difference which is a square. This sequence gives the smallest maximal integer in such sequences.

1, 3, 6, 8, 11, 13, 16, 18, 21, 23, 35, 38, 43, 48, 53, 58, 66, 68, 71, 73, 81, 86, 92, 97, 102, 107, 112, 118, 120, 125, 131, 133, 138, 144, 146, 151, 157, 159, 164, 189, 199, 203, 206, 208, 219, 223, 236, 242, 248, 253, 258, 263, 266, 269, 283, 285, 288, 293, 311, 314, 323, 328, 331, 334, 343, 346

Offset

1,2

Comments

László Lovász conjectured, and Hillel Furstenberg and András Sárközy (1978) independently showed that a(n) is superlinear. Erdős conjectured that a(n) >> n^2/log^k n for some k. Sárközy proved that a(n) = o(n^2/log^k n) for all k, but still conjectured that a(n) >> n^(2-e) for all e > 0. Ruzsa showed that in fact a(n) << n^1.365.

a(n) is the least m such that A100719(m) = n. - Glen Whitney, Aug 30 2015

References

András Sárközy, On difference sets of sequences of integers, II., Annales Universitatis Scientarium Budapestinensis de Rolando Eötvös Nominatae Sectio Mathematica 21 (1978), pp. 45-53.

Links

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..74

Fausto A. C. Cariboni, Sets that yield a(n) for n = 2..74, Feb 03 2019

Hillel Furstenberg, Ergodic behaviour of diagonal measures and a theorem of Szemeredi on arithmetic progressions, J. Analyse Math. 31 (1977), pp. 204-256.

Ben Green and Mehtaab Sawhney, Improved bounds for the Furstenberg-Sárközy theorem, arXiv preprint arXiv:2411.17448 [math.NT], 2024.

Janos Pintz, W. L. Steiger and Endre Szemerédi, On sets of natural numbers whose difference set contains no squares, J. London Math. Soc. 37:2 (1988), pp. 219-231.

I. Z. Ruzsa, Difference sets without squares, Periodica Mathematica Hungarica 15:3 (1984), pp. 205-209.

András Sárközy, On difference sets of sequences of integers, I., Acta Mathematica Academiae Scientiarum Hungaricae 31:1-2 (1978), pp. 125-149.

Formula

n * (log n)^((1/12) * log log log log n) << a(n) << n^k with k = 2/(1+log(7)/log(65)) = 1.364112553....

Green & Sawhney improve the lower bound to n * exp((log n)^c) for any c < 1/4. - Charles R Greathouse IV, Nov 27 2024

Example

There are no nontrivial differences in {1}, so a(1) = 1. {1, 2} contains the square 2-1 as a difference, but {1, 3} is valid so a(2) = 3.
a(3) = 6: {1, 3, 6}
a(4) = 8: {1, 3, 6, 8}
a(5) = 11: {1, 3, 6, 8, 11}
a(6) = 13: {1, 3, 6, 8, 11, 13}
a(7) = 16: {1, 3, 6, 8, 11, 13, 16}
a(8) = 18: {1, 3, 6, 8, 11, 13, 16, 18}
a(9) = 21: {1, 3, 6, 8, 11, 13, 16, 18, 21}
a(10) = 23: {1, 3, 6, 8, 11, 13, 16, 18, 21, 23}
a(11) = 35: {1, 3, 6, 8, 11, 13, 16, 18, 21, 23, 35}
a(12) = 38: {1, 4, 6, 9, 11, 14, 16, 21, 28, 33, 35, 38}
a(13) = 43: {1, 3, 6, 9, 11, 14, 16, 21, 33, 35, 38, 40, 43}

Prog

(PARI) ev(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=ev(u); for(k=1, sqrtint(m-1), u[m-k^2]=0); max(h, 1+ev(u))
a(n)=my(k=(5*n-3)\2, t); while(1, t=ev(vector(k, i, 1)); if(t==n, return(k)); k+=n-t)
(Python)
from itertools import count, islice
from sympy.ntheory.primetest import is_square
from networkx import empty_graph, find_cliques
def A210570_gen(): # generator of terms
    c, G = 0, empty_graph([])
    for n in count(1):
        G.add_node(n)
        G.add_edges_from((a, n) for a in G if a!=n and not is_square(n-a))
        if (m:=max(len(c) for c in find_cliques(G, nodes=[n])))>c:
            yield n
            c = m
A210570_list = list(islice(A210570_gen(), 20)) # Chai Wah Wu, Jan 11 2026

Crossrefs

Cf. A210380 (no two elements sum to a square).

Cf. A224839.

Sequence in context: A358844 A047219 A139477 * A224839 A122437 A286988

Adjacent sequences: A210567 A210568 A210569 * A210571 A210572 A210573

Keyword

nonn,nice

Author

Charles R Greathouse IV, Apr 02 2012

Extensions

a(17)-a(31) from Giovanni Resta, Dec 21 2012

a(32)-a(58) from Jon E. Schoenfield, Dec 28 2013

a(59)-a(66) from Fausto A. C. Cariboni, Nov 28 2018

Status

approved