login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 59th year, we have over 358,000 sequences, and we’ve crossed 10,300 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A100719 Size of the largest subset of {1,2,...,n} such that no two distinct elements differ by a perfect square. 5
1, 1, 2, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 6, 6, 7, 7, 8, 8, 8, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 18, 18, 18, 19, 19, 20 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

Prompted by a question about the rate of growth of this sequence asked by Sujith Vijay (sujith(AT)EDEN.RUTGERS.EDU) to the Number Theory List.

The problem can be thought of as finding a maximum independent set in a graph with node set {1, 2, ..., n} and an edge (i, j) if |i - j| is a square. - Rob Pratt.

The index of the first occurrence of m is A210570(m). - Glen Whitney, 2015 Aug 30

REFERENCES

A. Sárközy, On difference sets of sequences of integers II, Annales Univ. Sci. Budapest, Sectio Math.

LINKS

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..410 (terms n = 1..100 from Rob Pratt)

A. Balog, J. Pelikan, J. Pintz and E. Szemeredi, Difference sets without kappa-th powers, Acta Math. Hungar. 65 (1994), no. 2, 165-187.

Fausto A. C. Cariboni, Sets of maximal span that yield a(n) for n = 3..314, Nov 28 2018.

J. Pintz, Steiger and E. Szemeredi, On Sets of Natural Numbers Whose Difference Set Contains No Squares, J. London. Math. Soc. 37, 1988, 219-231.

I. Ruzsa, Difference sets without squares, Period. Math. Hungar. 15 (1984), no. 3, 205-209.

A. Sárközy, On difference sets of sequences of integers I, Acta Mathematica Academiae Scientiarum Hungarica, March 1978, Volume 31, Issue 1, pp 125-149.

A. Sárközy, On difference sets of sequences of integers III, Acta Mathematica Academiae Scientiarum Hungarica, September 1978, Volume 31, Issue 3, pp 355-386.

FORMULA

a(n) is known to be at least O(N^0.733) (I. Ruzsa, Period. Math. Hungar. 15 (1984), no. 3, 205-209). The best upper bound appears to be O(N (log n)^(- c log log log log N)) due to Pintz, Steiger and Szemeredi (J. London. Math. Soc. 37, 1988, 219-231). - Sujith Vijay, Sep 18 2007

A. Sárközy worked on this problem. There is also the following result of A. Balog, J. Pelikan, J. Pintz, E. Szemeredi: the size of largest squarefree difference sets = O(N / (log N)^(log log log log N / 4)). - Tsz Ho Chan (tchan(AT)MEMPHIS.EDU), Sep 19 2007

CROSSREFS

Cf. A131752, A131753, A131754.

Sequence in context: A355028 A061375 A029920 * A057354 A172476 A172267

Adjacent sequences: A100716 A100717 A100718 * A100720 A100721 A100722

KEYWORD

nonn

AUTHOR

N. J. A. Sloane, Sep 17 2007

EXTENSIONS

Computed via integer programming by Rob Pratt, Sep 17 2007

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 3 07:15 EST 2022. Contains 358512 sequences. (Running on oeis4.)