# Express the $n$th smallest number in this set in terms of $n$

Suppose $n$ is a perfect square. Consider the set of all numbers which are the product of two numbers, not necessarily distinct, both of which are at least $n$. Express the $n$th smallest number in this set in terms of $n$.

If, for example, $n = 4$, then the numbers are $4^2, 4 \cdot 5, 4 \cdot 6, 5^2$. If $n = 9$, then the numbers are $9^2,9 \cdot 10, 9 \cdot 11, 10^2, 9 \cdot 12, 10 \cdot 11,9 \cdot 13, 10 \cdot 12, 11^2$. Thus we conjecture the answer is $(n+\sqrt{n}-1)^2$, but how do we prove this?

• that number isn't an integer for most $n$ I think. – Jorge Fernández Hidalgo Jan 18 '17 at 3:39
• @JorgeFernándezHidalgo Recall that $n$ is a perfect square. – Puzzled417 Jan 18 '17 at 3:39
• oh, my bad.${}{}{}$ – Jorge Fernández Hidalgo Jan 18 '17 at 3:39
• Why do you think that number works? – Jorge Fernández Hidalgo Jan 18 '17 at 3:46
• @JorgeFernándezHidalgo Because I tested it for some examples and it was true. – Puzzled417 Jan 18 '17 at 3:48

Clearly there $w=(n+\sqrt n -1)^2$ is at least the $n$'th number in the list.
We must only prove that $w<ab$ if $a+b>2n+2\sqrt{n}-2$, with both $a$ and $b\geq n$.
Clearly this product is minimized in the case $a=n$, Which leaves $b>n+2\sqrt{n}-2$, since $b$ is an integer we can take the minimal case $b=n+\sqrt{2n}-1$.
So we must only prove $n(n+2\sqrt{n}-1)\geq (n+\sqrt{n}-1)^2\iff -n>-2n-2\sqrt{n}+n+1=-n-2\sqrt{n}+1$.
• Why is $w$ at least the $n$th number in the list? – Puzzled417 Jan 18 '17 at 15:35