Squares

Let the highest perfect square below the sequence be $n^2$ and the lowest perfect square above the sequence be $(n+1)^2$ , and assume that $1000N$ is the least multiple of $1000$ that is greater than $n^2$ (we want it minimized), so that our sequence should look a little like this: $...,n^2,...,1000N,1000N+1,...,1000N+999,...,(n+1)^2,...$ It is clear that $n\geq{500}$ , otherwise there are less than $1000$ terms in the sequence. Letting $n=500+x$ for some non-negative integer $x$ we have $n^2=(500+x)^2=250000+1000x+x^2 (*)$ Now observe that the difference between $n^2$ and $(n+1)^2$ for $n\in{[500,549]}$ is $\leq{1099}$ $(**)$ . Taking $n^2$ (see $(*)$ ) $\mod{1000}$ the two terms on the left end disappear and we're left with $n^2\equiv{x^2}\pmod{1000}.$ We want to add the minimum possible number to $n^2$ to get $1000N$ , thus, we need $x^2$ to be as close to $1000$ as possible otherwise $(n+1)^2$ will be a member of the sequence $\{1000N+k\}_{k=0}^{999}$ rather than strictly above it as required; this can be seen by considering $(**)$ : if $x\leq{30}$ then we need to add $\geq{100}$ to $n^2$ to get $1000N$ , but that would mean that for $n\in{[500,549]}$ (we want to keep $n$ as low as possible), $(n+1)^2-n^2\leq{1000}$ which we certainly don't want! (Why?) Thus, we must have $x\geq{31}.$ So the least possible value of $x=31$ , and trying this yields the sequence: $...,531^2,...,1000\times{282},1000\times{282}+1,...,1000\times{282}+999,...,532^2,...$ It follows that the least possible value of $1000N=1000\times{282}$ $\implies$ $\min\{N\}=\boxed{282}.$