The least number of quadratic polynomials needed to cover $[1,N]$ Let $r = r(N)$ denote the least number of quadratic polynomials $f_i \in \mathbb{Z}[x]$, $1 \leq i \leq r$, each with non-negative coefficients, such that for every integer $n \in [1,N]$, there exists $1 \leq i \leq r$ such that $n = f_i(m)$ for some integer $m \in \mathbb{N}$. Clearly, $r(N) \rightarrow \infty$, since for each quadratic polynomial $f$ with non-negative coefficient the set of integral values in $[1,N]$ that can be represented by $f$ is $O(N^{1/2})$, so for any number $c$, the set of values that can be covered by $f_1, \cdots, f_c$ is also $O(N^{1/2})$. This also shows that $r(N) \gg N^{1/2}$.
In fact, $r(N) = O(N^{1/2})$ as well, since the polynomials $f_1(x) = x^2, f_2(x) = x^2 + 1, \cdots, f_r(x) = x^2 + r$ with $r = N - \lfloor N^{1/2} \rfloor^2$ will cover cover $[1,N]$.
My question is what is the smallest positive value $c$ such that $r(N) \geq cN^{1/2}$ for all $N$ sufficiently large?
Thanks for any input. 
 A: That's not an answer too, just a result of a quick and naive computation: For $k\ge1$ let $n_k$ be the largest integer such that $r(n_k)=k$. Of course then $r(m)=k$ for all $n_{k-1}+1\le m\le n_k$. We have $n_1, n_2, \ldots = 1, 2, 6, 9, 13, 19, 23, 32, 32, 37, 45, 54, 61, 72, 82, 91, 101, 114, 128, 137\ldots$. And no, OEIS does not know this sequence ...
A: A special case of this problem has been studied in the literature (and I think this work will also cover the general version).  Given $N$, what is the smallest set $B$ such that every $n\le N$ can be written as $a^2+b$ with $b\in B$.  This was first raised by Erdos.  Taking $B$ to be the numbers up to $2\sqrt{N}$ we see an upper bound of $2\sqrt{N}$.  This remains the best known upper bound.  In the other direction, it is clear that $B$ must at least have $\sqrt{N}$ elements, but it is possible to do better.  The best in this direction is due to Javier Cilleruelo (see http://www.sciencedirect.com/science/article/pii/S0022314X83710498 ), who obtained the lower bound $(4/\pi+o(1)) \sqrt{N}$.  Cilleruelo considers more generally the complements of $k$-th powers.  The techniques there would also apply to this question, and I think give the same bounds.  It's not clear what the right constant is; if all the elements in $B$ are $o(N)$ then $2\sqrt{N}$ elements are required, so maybe the upper bound is close to the truth.
A: This Not an answer but an observation about the question.
Counting the number of such polynomials which is $O(N^{1/2})$ gives a proof of Sierpinski's prime sequence theorem http://mathworld.wolfram.com/SierpinskisPrimeSequenceTheorem.html
 and if you extend your question for polynomials of higher degree you can also extend Sierpinski's theorem for $n>2$ :
for any $M>0$ there exists a $t'$ such that $x^n+t',n\geq 2$ contains at least $M$ prime numbers.
