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})$

Question

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.

Answer 1

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)$.

Answer 2

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)$