# Solution to Putnam problem?

I think my solution must be wrong because it's way too simple and it disagrees with other solutions I have seen online. But I really can't figure out where the mistake is.

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.

Since $S(N)$ just counts some of the numbers between $1$ and $N$, we have $0 \le S(N) \le N$ for any $N$. So for any $N$,

$$\dfrac {0}{N^{\alpha}} \le \frac{S(N)}{N^{\alpha}} \le \dfrac {N}{N^{\alpha}}$$

$$0 \le \frac{S(N)}{N^{\alpha}} \le \dfrac {1}{N^{\alpha-1}}$$

Let $\alpha = 2$

$$0 \le \frac{S(N)}{N^{2}} \le \dfrac {1}{N}$$

By the Squeeze (Sandwich?) Theorem,

$$\lim_{N\to\infty}\frac{S(N)}{N^{2}}=0$$

So $\alpha = 2$, $\beta = 0$ (or $\alpha=$ any number $>2, \beta = 0$)

• You've ignored the requirement that $\beta>0$. Given that those constants are asked to be positive, what they're really trying to get you to do is to say that $S(n)\approx\beta N^{\alpha}$ for some $\alpha,\beta>0$; they're asking you to find the asymptotically most important term in describing the sequence's behavior. – Nick Peterson Dec 5 '16 at 15:01
• @NickPeterson Ouch I completely missed that the constants have to be positive! – Ovi Dec 5 '16 at 15:02
• @amWhy I don't see any requirement for $\alpha$ being a squarish number. – Ovi Dec 5 '16 at 15:03
• @amWhy: The nearest perfect square to $2$ is $1$, which is distant from $2$ by a perfect square ($1=1^2$), so $2$ is squarish. – Steve Kass Dec 5 '16 at 15:05
• Got it Steve, I was thinking in term of being with respect to the "next" perfect square – Namaste Dec 5 '16 at 15:07

For a positive integer $m$, we say that $n\in\mathbb{Z}_{>0}$ is its center if $n^2$ is the closest perfect square to $m$, in which case, we say that $m$ is a neighbor of $n$. First, it is easy to see that, for any positive integer $m$ with center $n$, $$n^2-n\leq m\leq n^2+n\,.$$ Note that a positive integer $m$ is squarish if and only if $$m=n^2\pm k^2\text{ for some }k\in\big\{0,1,2,\ldots,\lfloor\sqrt{n}\rfloor\big\}\,,$$ where $n$ is the center of $m$.
Now, let $a_n$ denote the number of squarish neighbors of a given positive integer $n$. From the result above, we see that $$a_1=2\text{ and }a_n=2\,\lfloor\sqrt{n}\rfloor+1\text{ for each }n\in\mathbb{Z}_{>1}\,.$$ Thus, $$S(n^2+n)= \sum_{r=1}^n\,a_r=-1+\sum_{r=1}^n\,\big(2\,\lfloor \sqrt{r}\rfloor+1\big)\tag{*}$$ for every positive integer $n$. That is, $$-1+\sum_{r=1}^n\,(2\sqrt{r}-1)<S(n^2+n)\leq -1+\sum_{r=1}^n\,(2\sqrt{r}+1)\,.$$
Using Bernoulli's Inequality, we have $$\left(1+\frac{1}{j}\right)^{\frac{3}{2}}\geq 1+\frac{3}{2j}\text{ for all }j\in\mathbb{Z}_{>0}\,.$$ That is, $$\sqrt{j}\leq \frac{2}{3}\,\left((j+1)^{\frac{3}{2}}-j^{\frac{3}{2}}\right)\,.$$ Likewise, $$\left(1-\frac{1}{j}\right)^{\frac{3}{2}}\geq 1-\frac{3}{2j}\text{ for all }j\in\mathbb{Z}_{>0}\,.$$ This implies $$\sqrt{j}\geq \frac{2}{3}\,\left(j^{\frac{3}{2}}-(j-1)^{\frac{3}{2}}\right)\,.$$
From (*), we get that $$\frac{4}{3}\,n^{\frac{3}{2}}-n-1< S(n^2+n)\leq \frac{4}{3}\,\left((n+1)^{\frac{3}{2}}-1\right)+n-1\,.$$ Thus, for any positive integer $N$ with center $n$, we have $n^2-n\leq N$, so that $$n\leq \sqrt{N+\frac{1}{4}}+\frac{1}{2}<\sqrt{N}+1$$ and $$S(N)\leq S(n^2+n)<\frac{4}{3}\,\left(\left(\sqrt{N}+2\right)^{\frac{3}{2}}-1\right)+\sqrt{N}$$ for all integers $N>0$. Similarly, $N\leq n^2+n$ implies that $$n\geq \sqrt{N+\frac{1}{4}}-\frac{1}{2}>\sqrt{N}-1$$ and $$S(N)\geq S\big((n-1)^2+(n-1)\big)>\frac{4}{3}\,\left(\sqrt{N}-2\right)^{\frac{3}{2}}-\sqrt{N}-1\,,$$ for all integers $N\geq 4$.
Consequently, we have proven that, for all integers $N\geq 4$, $$\frac{4}{3}\,\left(\sqrt{N}-2\right)^{\frac{3}{2}}-\sqrt{N}-1< S(N)< \frac{4}{3}\,\left(\left(\sqrt{N}+2\right)^{\frac{3}{2}}-1\right)+\sqrt{N}\,.$$ Ergo, $$\frac{4}{3}\,\left(1-\frac{2}{\sqrt{N}}\right)^{\frac{3}{2}}-\frac{1}{N^{\frac14}}-\frac{1}{N^{\frac{3}{4}}}< \frac{S(N)}{N^{\frac{3}{4}}}< \frac{4}{3}\,\left(\left(1+\frac{2}{\sqrt{N}}\right)^{\frac{3}{2}}-\frac{1}{N^{\frac34}}\right)+\frac{1}{N^{\frac{1}{4}}}\,.$$ By the Squeeze Theorem, $$\lim_{N\to\infty}\,\frac{S(N)}{N^{\frac{3}{4}}}=\frac{4}{3}\,,$$ whence $\alpha=\dfrac{3}{4}$ and $\beta=\dfrac{4}{3}$.