3
$\begingroup$

Find all pairs $(k, n)$ of positive integers such that $$k! = (2^n − 1)(2^n − 2)(2^n − 4) · · · (2^n − 2^{n−1})$$

I tried to solve this problem but only found one solution $(1,1)$. Please help me to solve this problem.

$\endgroup$
  • 5
    $\begingroup$ This is 2019 IMO Q4 - if you knew that it was a contest problem, please use the [contest-math] tag in the future. Also, what have you tried? $\endgroup$ – user574848 Jul 21 '19 at 10:59
  • $\begingroup$ I have tried to find odd and even parts of L.H.S and R.H.S and by comparing them I have tried to figure out the solution. I am new at here so pardon me for the tagging problem. Thanks. $\endgroup$ – moriarty Jul 21 '19 at 11:05
  • 2
    $\begingroup$ That's ok, just a tip for the future. It's a good idea to include your work in the question so that others can see what you've done and give you specific pointers in your direction, or appropriately gauge your familiarity with certain concepts (e.g. in number theory). For more info on how to ask a good question, see here $\endgroup$ – user574848 Jul 21 '19 at 11:21
  • 1
    $\begingroup$ The "$-1$" part of the last factor was rendered incorrectly, so I edited. $\endgroup$ – Jeppe Stig Nielsen Jul 21 '19 at 11:49
  • 2
    $\begingroup$ If you try $n=2$, the right-hand side becomes $(2^2-1)(2^2-2)=3\cdot 2=6$, and you recognize $6$ as a factorial number, so that gives you another example. If you evaluate the right-hand side for $n=1,2,3,\ldots$ (I did that on a computer), you get $1, 6, 168, 20160, 9999360, 20158709760, 163849992929280, \ldots$, and if you search for that on OEIS, you get A002884. $\endgroup$ – Jeppe Stig Nielsen Jul 21 '19 at 11:58
6
$\begingroup$

Find the exponent of the largest power of 2 that divides both sides. In RHS it is $0 + 1 + \ldots + (n-1) = \frac{(n-1)n}{2}$. In LHS it can be found with Legendre's formula, which gives $\sum_{i=1}^{\infty} \lfloor \frac{k}{2^i} \rfloor$. Since $\sum_{i=1}^{\infty} \lfloor \frac{k}{2^i} \rfloor < \sum_{i=1}^{\infty} \frac{k}{2^i} = k$ (the inequality is strict because at least one term in the bracket is not an integer), we have $k > \frac{(n-1)n}{2}$, or $k \ge \frac{(n-1)n}{2}+1$.

Since $RHS < 2^{n^2}$, and factorial grows faster than any exponential function, for large values of $n$, LHS will be larger than RHS. We need to find out an upper bound for $n$.

When $n \ge 6$, $$k! \ge (\frac{(n-1)n}{2}+1)! \ge 7! \cdot 8^{\frac{(n-1)n}{2}-6} > 2^{12} \cdot 2^{\frac{3}{2}n^2 - \frac{3}{2}n - 18} = 2^{n^2} \cdot 2^{\frac{1}{2}n^2 - \frac{3}{2}n - 6}$$

And $\frac{1}{2}n^2 - \frac{3}{2}n - 6 > 0$, so LHS > RHS. Therefore there are no solutions with $n \ge 6$. Manually checking the remaining cases gives the only solutions $(1, 1)$ and $(3, 2)$.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

Via Legendre's formula, we have for any prime number $p$ $$ \nu_p(k!)=\sum_{i=1}^{\infty}\left \lfloor \frac{k}{p^i} \right \rfloor \le \sum_{i=1}^{\infty} \frac{k}{p^i} =\frac{k}{p-1} $$

Note that $\nu_2(2^n-2^i)=i$, and hence $$\nu_2(k!)=\nu_2\left(\prod_{i=0}^{n-1}({2^n-2^i})\right)=\sum_{i=0}^{n-1}i=\frac{n(n-1)}{2}$$ Thus $$\frac{n(n-1)}{2}\le k \tag{1}$$

Note that $\nu_3(2^n-2^i)=\nu_3(2^{n-i}-1)$ and $3\nmid 2^m-1$ if $m$ is odd. In addition $$\nu_3(2^{2m}-1)=\nu_3(m)+1$$ which is a corollary of lifting the exponent lemma.

Thus

$$\nu_3(k!)=\nu_3\left(\prod_{i=0}^{n-1}({2^n-2^i})\right) = \left [ \frac{n}{2} \right] + \sum_{i=1}^{\left [ \frac{n}{2} \right]} \nu_3(i) =\nu_3 (\left[ \frac{n}{2} \right]!) + \left [ \frac{n}{2} \right] \le \frac{\frac{n}{2}}{2} +\frac{n}{2} =\frac{3n}{4}$$

Note that $\nu_3(k!)\ge \left[ \frac{k}{3} \right] >\frac{k}{3}-1$. Thus $$\frac{k}{3}-1<\frac{3n}{4} \tag{2}$$ From $(1)$ and $(2)$ we know $n \in \{1,2,3,4,5,6\}$. Via verification we get the solutions are $(k,n)=(1,1)$ or $(3,2)$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I think the $\nu_3(m)$ should be $\nu_3(m) + 1$. It may also help to clarify this step as it is not very obvious. $\endgroup$ – infmagic2047 Jul 21 '19 at 13:25
  • $\begingroup$ @infmagic2047 Thanks for reminding me of that. It's a corollary of lifting the exponent lemma. I will re-edit it $\endgroup$ – Chiquita Jul 21 '19 at 14:15

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.