2
$\begingroup$

Recently I was thinking about this problem:

Consider only positive integers. Given $N$, find the largest $U$ which can be expressed as the product of two integers less than or equal to $N$, in at least two different ways.

It turns out that such $U$ must be of this form:

$U=p(q-1)\times q(p-1)=pq\times (p-1)(q-1)$

where $pq\leq N$. Let $n^2\leq N<(n+1)^2$. If $N=n^2$ or $N=n(n+1)$ or $N=n(n+2)$, it is easy to figure out that one of $p,q$ is $n$ and the other is $N/n$. The problem arises when

1) $n^2<N<n^2+n$;

2) $n^2+n<N<n^2+2n$.

I analyzed case 2). Let $\alpha=N-n^2-n$. It seems $p,q$ should be of this form: $n+1+k+j$ and $n-j$ with $k\geq 1$ and

$j=\lceil-\frac{k+1}{2}+\sqrt{kn+(\frac{k+1}{2})^2-\alpha}\rceil$

To find the optimal $k$, let $k=1$ and $j=\lceil -1+\sqrt{n+1-\alpha}\rceil$ and search if there is any $k,j$ with larger $pq$.

For example, when $N=435$, take $k=1$ we get $24*18$ but there is a better one, $k=3$ with $29*15$.

Anybody has thought about this problem before? Is there anything more we can do about it?

$\endgroup$
3
  • $\begingroup$ With these type of problems what one should usually try to do is fix $U$ and find $N$ based on $U$. $\endgroup$
    – Zetapology
    Oct 10, 2017 at 4:30
  • $\begingroup$ Do you mean $U$ is bounded above and find the upper estimate of $N$? $\endgroup$ Oct 11, 2017 at 14:21
  • $\begingroup$ Yes. I do mean that. Thanks for clarifying. $\endgroup$
    – Zetapology
    Oct 11, 2017 at 14:34

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.