Following combinatorics problem is claimed to be an open problem in "[The Princeton Companion to Mathematics](https://books.google.com/books/princeton?hl=en&q=%22Will%20there%20always%20be%20a%20positive%20integer%22&vid=ISBN9781400830398&btnG.x=0&btnG.y=0&btnG=Search%20This%20Book#v=snippet&q=%22Will%20there%20always%20be%20a%20positive%20integer%22&f=false)" (pp. 6)



> 
> Let $a\_1,a\_2,a\_3,...$ be a sequence of positive integers, and suppose that each $a\_n$ lies between $n^2$ and $(n+ 1)^2$. Will there always be a positive integer that can be written in a thousand different ways as a sum of two numbers from the sequence?
> 
> 
> 


I am curious to know current status and references for this problem.



Combinatorics problem about sum of natural numbers
If the sequence $a\_1, a\_2,\dots$ has the property that each integer can be written in at most $g$ ways (counting order and allowing repetition), then we call the set $\{a\_1,a\_2,\ldots\}$ a $B^\ast[g]$ set. I wrote an extensive bibliography about 10 years ago, and published it in the [Electronic Journal of Combinatorics](http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS11) section on hot bibliographies. Unfortunately, I've never gotten around to updating it. For some reason, Math Sci-Net never cataloged it, either.


A related and more famous question, asked by Erdos and Turan, is if it is possible for a $B^\ast[g]$ set of nonnegative integers to also be a basis, that is, is it possible for every positive integer to have a representation while no positive integer has more than $g$ representations? The answer is known to be "no" for small $g$; the proofs are essentially a depth first search through $B^\ast[g]$ sets.


To answer the Shahrooz Janbaz's question, there is nothing too special about 1000 except that it removes "just compute all possibilities" as a possible strategy. That is, if "1000" is replaced by 4 or 5 or 6, then we could perhaps just search through all possibilities. Perhaps a clever program (SAT solver?) could handle 10 or 20. But 1000 clearly requires a deeper understanding of addition.


