MHB How Can We Find All Integer Pairs (k, n) That Satisfy This Factorial Equation?

[anemone]

Here is this week's POTW:

-----

Find all pairs of positive integers $(k,\,n)$ such that $k!=(2^n-1)(2^n-2)(2^n-4)\cdots(2^n-2^{n-1})$.

-----

 

[haruspex]

Here is this week's POTW:

-----

Find all pairs of positive integers $(k,\,n)$ such

-----

LHS= $k! >(\frac ke)^k\sqrt{2\pi k}\frac 1{e^{12k+1}}$
RHS$=(2^n-1)(2^n-2)(2^n-4)\cdots(2^n-2^{n-1})$
$=(2^n)^n\Pi_1^n(1-2^{-r})$
$=2^{n^2}e^{\Sigma_1^n\ln(1-2^{-r})}$
$<2^{n^2}e^{\Sigma_1^n-2^{-r}}$
$=2^{n^2}e^{-1}$
So $(\frac ke)^k\sqrt{2\pi k}\frac 1{e^{12k+1}}<2^{n^2}e^{-1}$
$(\frac ke)^k<2^{n^2}$
Define $d_2(m)$ as the number of times 2 divides m.
$\frac 12k<d_2(LHS)<k$
$d_2(RHS)=\frac 12n(n-1)$
Hence $k<n(n-1)<2k$
If $n\geq N$ then $n^2\frac{N-1}N<n(n-1)<2k$.

$(\frac ke)^k<2^{2k\frac N{N-1}}$
$k<2^{2\frac N{N-1}}e$
With N=5 this yields
$k\leq 15$
$n<6$
Thus, if $n\geq 5, n\leq 5$, hence $n\leq 5$.

I haven't been through all the possibilities yet.. no time now … but the only two solutions that are obvious are n=1, k=1; n=2, k=3.

 

[PeroK]

Here's an informal argument:

Spoiler

Let $$a(n) =(2^n-1)(2^n-2)(2^n-4)\cdots(2^n-2^{n-1})$$And note that$$a(n) = (2^n-1)(2^{n-1})a(n-1)$$If we let $t(n)$ be the powers of $2$ in the prime factorisation for $a(n)$ then we see that:$$t(n) = \frac{n(n-1)}{2}$$And note that $t(n)$ increases rapidly with $n$.

Now we look at the powers of $2$ in $k!$ and we note that this increases much less rapidly.

In any case, we can look for the factorials that have the same power of $2$ for the relevant $n$. E.g:
$$n = 5, t(n) = 10, k = 12 \ \text{or} \ 13$$We can check that $a(n) \ne k!$ in these cases. The next cases are:
$$n = 6, t(n) = 15, k = 16 \ \text{or} \ 17$$$$n = 7, t(n) = 21, k = 24 \ \text{or} \ 25$$And for this value of $n$ the possible values of $k!$ are already much greater than $a(n)$. If we keep going:
$$n = 8, t(n) = 28$$ there are no possible values of $k$
$$n = 9, t(n) = 36$$ there are also no possible values of $k$. Moreover, for the nearest values of $k$ we see that $k!$ is now much larger than $a(n)$ it's clear that there can be more solutions.

You could look more formally at how $a(n)$ and the possible values of $k$ are increasing to formalise the argument somewhat.

 

[Office_Shredder]

I only came up with this after reading the other solutions, so it's not very original but I think hits the heart of the problem.

Spoiler

for $0<j<2^{n-1}$, $j$ and $2^{n-1}+j$ have the same number of factors of $2$ - if $2^a|j$ then $j<n-1$ so $2^a | 2^{n-1}$, and hence $j = j+2^{n-1}$ mod $2^a$

Matching $2^{n-1}+1$ with $1$ all the way through $2^{n}-1$ with $2^{n-1}-1$, we see the product in the question has the same number of 2s as $2^{n-1}!$This doesn't agree with perok's numbers, for $n=7$ this gives $k=64$, but wolfram alpha agrees these both are divisible by $2^{63}$

https://www.wolframalpha.com/input?i=factor+(2^6)!

https://www.wolframalpha.com/input?i=factor+(2^7-1)!/(2^6-1)!

So $k$ must be $2^{n-1}$ or $2^{n-1}+1$. For $k=1$ these products are the same. For $k=3$ you also get equality. In general in our mapping of numbers in the $(2^n-1)!/(2^{n-1}-1)!$ to the numbers in $2^{n-1}!$ to establish the power of 2 correpondence, each number in the former was at least twice as large as the latter except for the $2^{n-1}$ which we didn't map to a smaller number since it's in both products, so to get equality you need $k=1$, or you need$k=2^{n-1}+1$ to get an extra factor to try to catch up. But even then we just get an extra factor of $2^{n-1}+1$ when we're trying to compete with $2^{n-1}-1$ extra powers of two (so a factor of 2 raised to that quantity). So we need $n-1 \geq 2^{n-1}-1$ which is only true for $n=1$ or $n=2$.

 

[PeroK]

Here's a simpler informal argument:

Spoiler

Let $$a(n) =(2^n-1)(2^n-2)(2^n-4)\cdots(2^n-2^{n-1})$$And note that$$a(n) = (2^n-1)(2^{n-1})a(n-1)$$We can now analyse the prime factors of $a(n)$ recursively by looking at the sequence $2^n-1$:
$$3, 7, 15, 31, 63, 127 \dots$$Immediately, we see that prime numbers like $31$ and $127$ appear early in the factorisations. But, don't appear in $k!$ until $k =31$ or $k = 127$ respectively.

It's clear (although not so easy to prove formally) that this sequence can never produce another factorial for larger $n$. It has far too many powers of $2$ compared to the other primes and has larger primes appearing too early in the sequence.