Tessellate S.T.E.M.S - Mathematics - College - Set 1 - Problem 5

If $n = a^2 - b^2 = (a+b)(a-b)$ can be written as the difference of two squares (of positive integers) in at least two different ways, there must be at least two different ways of factorising $n$ as the product of two (positive) integers of the same parity. Thus, to be a "good" number, there are three options:

• odd "good" numbers are odd primes. There are $\pi(n) - 1$ of these between $1$ and $n$ .
• all numbers congruent to $2$ modulo $4$ are "good". There are $\lfloor \tfrac{n-2}{4}\rfloor + 1$ of these between $1$ and $n$ .
• multiples of $4$ of the form $4p$ where $p$ is prime are "good". There are $\pi(\lfloor \tfrac{n}{4}\rfloor)$ of these between $1$ and $n$ .

Thus there are $\pi(n) + \lfloor \tfrac{n-2}{4}\rfloor + \pi(\lfloor \tfrac{n}{4}\rfloor)$ "good" numbers, and so $p(n) \; = \; \frac{1}{n}\left(\pi(n) + \lfloor \tfrac{n-2}{4}\rfloor + \pi(\lfloor \tfrac{n}{4}\rfloor) \right) \; \sim \; \frac{1}{\ln n} + \frac14 + \frac{1}{4\ln(\frac14n)} \; \to \; \boxed{\frac14}$ as $n \to \infty$ . Since the terms like $\frac{1}{\ln n}$ tend to $0$ as $n \to \infty$ , they can be ignored.