A210380 -id:A210380 - cp's OEIS frontend

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

Charles R Greathouse IV, Apr 02 2012

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

			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}

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.

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.

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

Cf. A224839.

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)

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

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

A099107 a(n) is the least M such that there are n values in 0..M with no two values summing to a square.

Original entry on oeis.org

0, 2, 3, 5, 8, 10, 11, 14, 18, 20, 21, 24, 26, 28, 32, 34, 36, 38, 40, 42, 48, 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

Jean-Charles Meyrignac (euler(AT)free.fr), Nov 14 2004

nonn

Examples where the solution is unique:
(14,28) 2 4 6 9 11 13 15 17 18 20 22 24 26 28
(16,34) 3 5 8 10 12 14 16 18 19 21 23 25 27 29 32 34
(17,36) 3 5 8 10 12 14 16 18 19 21 23 25 27 29 32 34 36
(18,38) 3 5 8 10 12 14 16 18 19 21 23 25 27 29 32 34 36 38
(19,40) 3 5 8 10 12 14 16 18 19 21 23 25 27 29 32 34 36 38 40
(20,42) 3 5 8 10 12 14 16 18 19 21 23 25 27 29 32 34 36 38 40 42

Rob Pratt, Table of n, a(n) for n = 1..100

If the numbers are taken from 1..M instead of 0..M, we get A210380.

Definition clarified and sequence extended by Don Reble and M. F. Hasler, Jul 08 2014

More terms from Rob Pratt, Jul 11 2014

A304868 Numbers x satisfying x == 1 (mod 4) or x == 14, 26, 30 (mod 32).

Original entry on oeis.org

1, 5, 9, 13, 14, 17, 21, 25, 26, 29, 30, 33, 37, 41, 45, 46, 49, 53, 57, 58, 61, 62, 65, 69, 73, 77, 78, 81, 85, 89, 90, 93, 94, 97, 101, 105, 109, 110, 113, 117, 121, 122, 125, 126, 129, 133, 137, 141, 142, 145, 149, 153, 154, 157, 158, 161, 165, 169, 173, 174, 177

Offset: 1

Michel Marcus, May 20 2018

The sum of two distinct terms of this sequence is never a square.

Sequence has density 11/32, the maximal density that can be attained with such a sequence.

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.

Colin Barker, Table of n, a(n) for n = 1..1000
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.
Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,0,0,0,0,0,0,1,-1).

Cf. A016777 (another such sequence), A210380.

isok(n) = ((n%4)==1) || ((n%32)==14) || ((n%32)==26) || ((n%32)==30);

Vec(x*(1 + 4*x + 4*x^2 + 4*x^3 + x^4 + 3*x^5 + 4*x^6 + 4*x^7 + x^8 + 3*x^9 + x^10 + 2*x^11) / ((1 - x)^2*(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^10)) + O(x^40)) \\ Colin Barker, May 20 2018

From Colin Barker, May 20 2018: (Start)
G.f.: x*(1 + 4*x + 4*x^2 + 4*x^3 + x^4 + 3*x^5 + 4*x^6 + 4*x^7 + x^8 + 3*x^9 + x^10 + 2*x^11) / ((1 - x)^2*(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^10)).
a(n) = a(n-1) + a(n-11) - a(n-12) for n>12.
(End)

A363069 Size of the largest subset of {1,2,...,n} such that no two elements sum to a perfect square.

Original entry on oeis.org

1, 1, 1, 2, 2, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, 7, 8, 8, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 18, 19, 19, 19, 20, 20, 20, 20, 21, 21, 22, 22, 23, 23, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 26, 27, 27

Offset: 1

Zachary DeStefano, May 16 2023

nonn

			The first few examples where a(n) increases are {1}, {1,4}, {1,4,6}, and {1,4,6,7}.

Z. DeStefano, Maximum Sized Sets With Sums That Avoid Squares

Cf. A100719, A210380.

The set: {k | k <= n, k == 1 (mod 3)} provides a lower bound: a(n) >= floor((n+2)/3).

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A099107 a(n) is the least M such that there are n values in 0..M with no two values summing to a square.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A304868 Numbers x satisfying x == 1 (mod 4) or x == 14, 26, 30 (mod 32).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

PARI

Formula

A363069 Size of the largest subset of {1,2,...,n} such that no two elements sum to a perfect square.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula