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.