Q:

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.

A:

Given numbers from $1$ to $N$, there are $\sqrt{N}$ squares (to be precise, we need to use a floor function, but this should be fine for dealing with a limit. Then, we consider perfect squares like $x^2$:

\[ 1, … , {(x-1)}^2, …, x^2, …, {(x+1)}^2, \dots, N \]

We notice that the difference between the squares $x^2$ and $(x-1)^2$ is given by:

\[ x^2 - (x-1)^2 = x^2 - x^2 + 2x - 1 = 2x - 1 \]

which means that there are $2x - 2$ numbers strictly between the two perfect squares, and which means that the upper $x - 1$ squares are closer to $x^2$ than ${(x-1)}^2$. Similarly, there are $2x$ numbers strictly between $x^2$ and $(x+1)^2$, and so $x$ are closer to $x$.

If we count from $x$ going down, the number of squarish numbers will just be $x$ minus the perfect squares up until $x^2 - (x-1)$, so there are $\sqrt{x-1}$ squarish numbers below $x$. Similarly, there will be $\sqrt{x}$ squarish numbers above $x$. Again, necessary floor functions are omitted for asymptotic analysis. This holds for all $x$ except for 1 and the final $x$, but that should not matter once we take the limit.

Thus, we have:

\[ S(N) \approx \sqrt{N} + \sum_{x =1}^{\sqrt{N}}(\sqrt{x} + \sqrt{x - 1}) \approx \sqrt{N} + \sum_{x = 1}^{\sqrt{N}}2\sqrt{x} \]

Now, how do we evaluate the sum, taking $N$ to infinity? Well, this actually brings up an old physics trick that is used in a very similar calculation. It really isn’t a “trick” so much as it is sloppy math that gets the right answer, and I imagine it could be made rigorous. But a brief detour.

In calculating the energy of a Fermi gas in 2-D, which is just a bunch of quantum particles in their energy states, you get by particles filling up the lowest energy levels up to a certain energy, essentially occupying a lattice of points in the x-y plane, subject to some constraint that looks like a circle:

\[ n_x^2 + n_y^2 \leq N \]

You then want to sum up a function (energies at each point), $f(n_x, n_y)$, over these allowed energies, and take the limit for large $N$ (total energy for a large, macroscopic $N$). The trick is to wave your hands and call the discrete sum an integral, which really “isn’t so bad” when N is large, and the tiny granular points look continuous, and you get something like:

\[ \int_{Circle}f(n_x, n_y) dA = E \]

This is essentially what we want to do here, only in 1-D.

We have, in the limit as N approaches infinity:

\[ \sum_{x = 1}^{\sqrt{N}}2\sqrt{x} \approx \int_1^{\sqrt{N}}2\sqrt{x}dx = \frac{3}{2}x^{\frac{3}{2}}\Biggr\rvert_1^{\sqrt{N}} = \frac{4}{3}N^{\frac{3}{4}} - \frac{4}{3} \approx \frac{4}{3}N^{\frac{3}{4}} \]

\[ S(N) \approx \sqrt{N} + \sum_{x = 1}^{\sqrt{N}}2\sqrt{x} \approx N^{\frac{1}{2}} + \frac{4}{3}N^{\frac{3}{4}} \]

Then, we can see that if we set:

\[ \alpha = \frac{3}{4} \]

\[ \beta = \frac{4}{3} \]

Then we do get:

\[ \lim_{N \to \infty}\frac{N^{\frac{1}{2}} + \frac{4}{3}N^{\frac{3}{4}}}{N^{\frac{3}{4}}} = \frac{4}{3} \]

I guess a more rigorous approach would do the same thing, but use some kind of Riemann sums/floor functions/bounds to make the argument airtight.