6
$\begingroup$

Suppose n is a perfect square. Let us look at the

set of all numbers which is the product of two numbers, not necessarily distinct, both of which are at least n.

Is it possible to find an expression for the n-th smallest number in this set in terms of n

$\endgroup$
  • 1
    $\begingroup$ When you say "all numbers" and "two numbers," are you talking about integers only. Also, are they strictly positive? $\endgroup$ – Carser Aug 15 '16 at 0:19
  • $\begingroup$ Yes I mean positive integers @ above $\endgroup$ – John Aug 15 '16 at 0:27
  • $\begingroup$ Probably , we need to use the fact that n is a perfect square in some step intermediate to finding the nth smallest number of the set. $\endgroup$ – John Aug 15 '16 at 1:05
  • 1
    $\begingroup$ Based on a quick (and hopefully correct) calculation, it looks like you get this sequence: oeis.org/A062938 which is the squares of the terms of this sequence: oeis.org/A028387 but I don’t immediately see why. $\endgroup$ – Steve Kass Aug 15 '16 at 2:00
  • $\begingroup$ Can you please explain your calculations . Probably you may want to write a detailed solution as the answer :) $\endgroup$ – John Aug 15 '16 at 2:09
1
$\begingroup$

Let's arrange the terms in the following order:

$n^2$

$n(n+1)$

$n(n+2), (n+1)^2$

$n(n+3), (n+1)(n+2)$

$n(n+4), (n+1)(n+3), (n+2)^2$

$n(n+5), (n+1)(n+4), (n+2)(n+3)$

....

Some simple remarks you can prove easily yourself:

  1. The terms are in increasing order from left to right.

  2. Suppose $n=k^2$. When $i<k$ we have $(n+i)^2 < n(n+2i+1)$, the terms are also in increasing order from up to down.

  3. The number of terms in each row are 1,1;2,2;3,3;4,4;... (notice that the general term in a row is $(n+i)(n+j)$, where $i+j$ is fixed.)

  4. The term (n+i)(n+j) lies in $(i+j+1)^{th}$-row

  5. The term $(n+k-1)^2$ lies at the end of $(2k-1)^{th}$-row, therefore, its position is:

$1+1+2+2+3+3+...+(k-1)+(k-1)+k =n^2$

So we have confirmed the observation of @Carser.

$\endgroup$
  • 1
    $\begingroup$ This isn't increasing order. The number at the end of one row is often greater than the number at the start of the next row. $\endgroup$ – user2357112 Aug 15 '16 at 3:19
  • 1
    $\begingroup$ Also, not all of these products are distinct. $\endgroup$ – user2357112 Aug 15 '16 at 3:20
  • 1
    $\begingroup$ Well, $(n+k)^2 < n(n+2k+1)$ as long as $n>k^2$, so the ordering only fails after it has reached the $n^{th}-term$ $\endgroup$ – Pluviophile Aug 15 '16 at 3:33
  • 1
    $\begingroup$ Your work is probably salvageable, but it has holes that definitely need patching. $\endgroup$ – user2357112 Aug 15 '16 at 3:37
  • $\begingroup$ @user2357112 I have edited the answer. $\endgroup$ – Pluviophile Aug 15 '16 at 3:50
3
$\begingroup$

Having written some python to pump these out (see code here: https://repl.it/CnHE/5), I get the same sequence mentioned in the comments: \begin{matrix} \\ n & n^{th} \text{ term} & n^{th} \text{ term} \\ \hline 1 & 1 & (1+0)^2 \\ 4 & 25 & (4+1)^2 \\ 9 & 121 & (9+2)^2 \\ 16 & 361 & (16+3)^2 \\ 25 & 841 & (25+4)^2 \\ 36 & 1681 & (36+5)^2 \\ 49 & 3025 & (49+6)^2 \\ 64 & 5041 & (64+7)^2 \\ 81 & 7921 & (81+8)^2 \\ 100 & 11881 & (100+9)^2 \\ \end{matrix}

We can observe that the $n^{th}$ term is $$(n+\sqrt{n}-1)^2$$ Of course this is just an observation, not a proof...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.