Putnam 2016, Problem B-2

Define a positive integer \( n \) to be squarish if either \( n \) is itself a perfect square or the distance from \( n \) to the nearest perfect square is a perfect square. For example, 2016 is squarish, because the nearest perfect square to 2016 is \( 45^2 = 2025 \) and \( 2025 - 2016 = 9 \) is a perfect square. (Of the positive integers between 1 and 10, only 6 and 7 are not squarish.) For a positive integer \( N \), let \( S(N) \) be the number of squarish integers between 1 and \( N \), inclusive. Find positive constants \( \alpha \) and \( \beta \) such that
\[
\lim_{N \to \infty} \frac{S(N)}{N^\alpha} = \beta,
\]
or show that no such constants exist.

Solution:
We prove that the limit exists for $\alpha = \frac{3}{4}$, $\beta = \frac{4}{3}$.

For any given positive integer $n$, the integers which are closer to $n^2$ than to any other perfect square are the ones in the interval $[n^2-n-1, n^2+n]$. The number of squareish numbers in this interval is $1 + \lfloor \sqrt{n-1} \rfloor + \lfloor \sqrt{n} \rfloor$. Roughly speaking, this means that

$$S(N) \sim \int_0^{\sqrt{N}} 2\sqrt{x}dx = \frac{4}{3}N^{3/4}.$$

To make this precise, we use the bounds $x-1 \leq \lfloor x \rfloor \leq x$, and the upper and lower Riemann sum estimates for the integral of $\sqrt{x}$, to derive upper and lower bounds on $S(N)$:

$$S(N) \geq \sum_{n=1}^{\lfloor \sqrt{N} \rfloor - 1} (2\sqrt{n-1} - 1) \geq \int_0^{\lfloor \sqrt{N} \rfloor - 2} 2\sqrt{x}dx - \sqrt{N} \geq \frac{4}{3}(\sqrt{N} - 3)^{3/2} - \sqrt{N}$$

$$S(N) \leq \sum_{n=1}^{\lceil \sqrt{N} \rceil} (2\sqrt{n} + 1) \leq \int_0^{\lceil \sqrt{N} \rceil + 1} 2\sqrt{x}dx + \sqrt{N} + 1 \leq \frac{4}{3}(\sqrt{N} + 2)^{3/2} + \sqrt{N} + 1.$$

**Remark:** John Rickert points out that when $N = n^4$, one can turn the previous estimates into exact calculations to obtain the formula

$$S(N) = \frac{4}{3}\left(n^3 + \frac{n}{2}\right) = \frac{4}{3}N^{3/4} + \frac{2}{3}N^{1/4}.$$

For general $N$, one can then use the estimates

$$\frac{4}{3}(N-1)^{3/4} + \frac{2}{3}(N-1)^{1/4} \leq S(\lfloor N^{1/4} \rfloor^4) \leq S(N) \leq S(\lceil N^{1/4} \rceil^4) \leq \frac{4}{3}(N+1)^{3/4} + \frac{2}{3}(N+1)^{1/4}$$

to obtain the desired limit.