A100719 -id:A100719 - cp's OEIS frontend

A131754 Size of the largest subset of {1,2,...,n} such that no two distinct elements differ by a perfect square > 1.

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

Offset: 1

Olivier Gérard, Sep 17 2007

nonn

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..270 (terms n = 1..165 from Robert Israel)
Fausto A. C. Cariboni, Sets of maximal span that yield a(n) for n = 2..270, Nov 18 2018.

Cf. A100719, A131752, A131753.

f:= proc(n) uses GraphTheory; IndependenceNumber(Graph(n,
   {seq(seq({i,i+x^2},x=2..floor(sqrt(n-i))),i=1..n)}));
end proc:
map(f, [$1..58]); # Robert Israel, Mar 20 2017

More terms from Robert Israel, Mar 20 2017

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.

Original entry on oeis.org

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

A131752 Number of ways of choosing the largest subset of {1,2,...,n} such that no two distinct elements differ by a perfect square.

Original entry on oeis.org

1, 2, 4, 7, 10, 16, 24, 36, 56, 76, 112, 160

Offset: 1

Olivier Gérard, Sep 17 2007

nonn

Cf. A100719, A131753, A131754.

A131753 Number of ways of choosing the largest subset of {1,2,...,n} such that no two distinct elements differ by a perfect square > 1.

Original entry on oeis.org

1, 3, 7, 15, 23, 35, 53, 80, 134, 188, 266, 376

Offset: 1

Olivier Gérard, Sep 17 2007

nonn

Cf. A100719, A131752, A131754.

A362914 a(n) = size of largest subset of {1..n} such that no difference between two terms is a prime.

Original entry on oeis.org

1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 11, 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19

Offset: 1

N. J. A. Sloane, May 15 2023

nonn

Suggested by Ben Green's Number Theory Web Seminar on May 11 2023.

			The first few examples where a(n) increases are {1}, {1,2}, {1,5,9}, and {1,2,10,11}.

Martin Ehrenstein, Table of n, a(n) for n = 1..127
Ben Green, On Sarkozy's theorem for shifted primes, Number Theory Web Seminar, May 11 2023; Youtube video https://www.youtube.com/watch?v=5JH_YshJoCo.

Other entries of the form "size of largest subset of {1...n} such that no difference between two terms is ...": a square: A100719; a prime - 1: A131849; a prime + 1: A362915.

Taking numbers of the form 4k + 1 <= n gives a(n) >= 1 + floor((n - 1) / 4). - Zachary DeStefano, May 16 2023

a(12)-a(40) from Zachary DeStefano, May 15 2023

a(41)-a(75) from Martin Ehrenstein, May 16 2023

A362915 a(n) = size of largest subset of {1...n} such that no difference between two terms is a prime + 1.

Original entry on oeis.org

1, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 12, 12, 12, 12, 12, 12, 12

Offset: 1

N. J. A. Sloane, May 15 2023

nonn

Suggested by Ben Green's Number Theory Web Seminar on May 11 2023.

Ben Green, On Sarkozy's theorem for shifted primes, Number Theory Web Seminar, May 11 2023; Youtube video https://www.youtube.com/watch?v=5JH_YshJoCo.

Other entries of the form "size of largest subset of {1...n} such that no difference between two terms is ...": a square: A100719; a prime - 1: A131849; a prime: A362914.

a(1)-a(40) from Zachary DeStefano, May 15 2023, a(41)-a(100) from Rob Pratt, May 15 2023.

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

A131754 Size of the largest subset of {1,2,...,n} such that no two distinct elements differ by a perfect square > 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Extensions

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

A131752 Number of ways of choosing the largest subset of {1,2,...,n} such that no two distinct elements differ by a perfect square.

Views

Author

Keywords

Crossrefs

A131753 Number of ways of choosing the largest subset of {1,2,...,n} such that no two distinct elements differ by a perfect square > 1.

Views

Author

Keywords

Crossrefs

A362914 a(n) = size of largest subset of {1..n} such that no difference between two terms is a prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A362915 a(n) = size of largest subset of {1...n} such that no difference between two terms is a prime + 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

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