A set of integers whose factorial can be written as a product of two factorials

Question

I am trying to collect informations concerning the set $$\mathcal{A}=\left\{n\in\mathbb{N} \mid (\exists k,l\in\{2,3,\dots,n-2\})(n!=k!l!)\right\}.$$ It seems not much is known about the set $\mathcal{A}$. Below, I mention all what I have. Any other result relating properties of $\mathcal{A}$ will be appreciated.

First, it is not known (to my best knowledge), if $\mathcal{A}$ is finite or not. Note that the range for factors $k$ and $l$ excludes values $1,n$, and also $n-1$. Clearly, I want to avoid trivial identities of the form $n!=1!n!$. Less trivially, nevertheless it not an interesting case if one factor equlas $n-1$ since for any integer $n$ which is a factorial of another integer, say $n=m!$, we have $n!=m!(n-1)!$. For example, $6!=3!5!$, but $6\notin\mathcal{A}$.

The least number and the only one I know belonging to $\mathcal{A}$ is 10 since $$10!=6!7!.$$

I can prove (and it is not hard at all) that if $n\in\mathcal{A}$ and $n!=k!l!$, then $k+l>n+1$.

Mathematicians studied a more general set allowing decomposition of $n!$ into a product of more then only two factorials (hence $\mathcal{A}$ is a subset). In $\S$B23 (page 80) of R. K. Guy, Unsolved Problems in Number Theory, 2nd ed., New York, Springer-Verlag, 1994, one finds the following:

With the aid of computer, J.Shallit and M. Easter showed that, between numbers $1,2,\dots,18160$, only the number 10 belongs to $\mathcal{A}$. This computation comes from early 90's and, as I indicated above, it treats even more general problem. So I thing that at least this result could be extended significantly with today's computers. I do not know the algorithm used by J.Shallit and M. Easter but certainly the main obstacle is that one has to check a lot of equalities between huge numbers. This could be simplified by taking a logarithm of both sides in $n!=k!l!$, for instance.

Next, it has been proved by Paul Erdős that if $$\lim_{n\to\infty}\frac{P(n(n+1))}{\ln n}=\infty,$$ where $P(n)$ is the largest prime factor of $n$, then $\mathcal{A}$ has to be finite.

Finally, by personal communications with some colleges (mathematicians, though not number theorists) I encountered also a curios opinion that $\mathcal{A}$ contains only number 10.

Answer 1

By comparing the growth of the $p$-divisibility of the factorial compared to its size, we can see that one of the numbers must be much smaller than the other.

Using Geoff's estimate at the prime $2$, we have $k+l -n = O(\log n)$. By Stirling's formula, since $kl \geq 1$:

$$k \log k + l \log l \geq n \log n$$

$$(k+l -n) \log n \geq k \log (n/k) + l \log (n/l) $$

$$ k \log(n/k) + l \log(n/l) = O( \log n)^2$$

Assume $k>l$, then $l$ cannot be much higher than $n/2$, so $\log (n/l)$ is at least a small constant. Hence $l = O( \log n)^2$. Immediately we get $n-k = O(\log n \log \log n)$.

So $l$ is small and $n$ must be very close to $k$. One could try and push this upper bound on $l$ further using number theory methods. For $l$ to be large, for all small primes $p$ there must be differences between the base $p$ digits of $k$ and $n$, despite the fact that they are not very far apart.

---

As Gjergi points out, even proving the case $n-k=2$ seems out of reach of current methods. So let's work conditionally. Conditionally on the ABC conjecture, I can prove that there are only finitely many exceptions.

Let $d=n-k$. We have $\prod_{i=1}^d (k+i) = l!$. Using this, we can observe that the largest prime factor dividing $k+i$ for any $i$ in that interval is at most $l$. Furthermore, a prime $p$ only divides $l!$ at most $l/(p-1)$ times, so it can only divide at most $l/(p-1)$ of the $k+i$.

So the average over $i$ from $1$ to $d-1$ of the log of the product of primes dividing $(k+i)(k+i+1)$ is:

$$\sum_{p<l/d} \log p + \sum_{p>l/d} \frac{l}{ d (p-1) } \log p $$

$$ \approx \frac{l}{d}+ \frac{l}{d} \int_{l/d}^l \frac{1}{x} dx = \frac{l}{d} (1 + \log d) $$

Here $\approx$ means that the ratio between the two sides is $1+ o(1)$.

For some $i$, the product of the prime divisors is at most the average. Consider the ABC triple $(1,k+i , k+i+1)$. We have given an upper bound for $rad(abc)$. $\log c \approx \log k$, so the quality of the ABC triple is:

$$ \approx \frac{ d \log k}{l (1+ \log d) }$$

We can simplify this by noting:

$$ d\log k \approx \log ( l!) \approx l \log l$$

and

$$\log l \approx \log ( d \log k) = \log d + \log \log k$$

Assuming the ABC conjecture, the quality is at most $\approx 1$, hence we have:

$$ \frac{ \log d + \log \log k}{ \log d + 1} \approx 1$$

If $d$ is bounded then $k$ must remain bounded, so $d$ goes to $\infty$ with $k$ so we have:

$$\log \log k = o(1) \log d $$

$$ d = (\log k)^{1/o(1) }$$

We already have $d = (\log k)^{O(1)}$ which is a contradiction unless there are only finitely many solutions.

So assuming the ABC conjecture, there are only finitely many solutions.

I think this is different from Erdos's result because as far as I can tell the ABC conjecture does not imply his assumption. I didn't check the literature mentioned in the question so this argument could easily be in one of those.

Answer 2

UPDATE The algorithm have been improved, and c up to 100,000,000,000 have been tested. with a billion per hour on a laptop.

The reason why this can be done so quickly looping in c, is

1. You can stop checking b's if b=p-1: a<b<p<c p divisor in c! but not in b! and certainly not in a! And as the prime-density (at least for the first few billions) is roughly 1:20, so in mean you only need about 20c tests, that is de facto LINEAR in c!!!

2. You can filter further by keeping a list of Log(a!), and only calculate Log(c!/b!). Both of these are very quickly calculated, as you can do them as adding Log(x) to the previously calculated. So this is O(1) for each I then do a binary search in the saved Log(a!) list (only up to a=1694 is even considered for the first 30 billions, so a small list to check) So only in the rare cases of large prime distances a large gap between b and c means that 'high' a's are needed, and tiny compared to b and c.

   3. Only 113 thousand of the 30 billions (or short of 4 per million) made it through this filter. So it is not really important that the accurate test of these few candidates are super fast any more.
   4. A fast algorithm for dynamically finding (and caching) primes as needed.

---

It is possible to put quite a bit of limitations on this problem, so a numerical brute force attack on this can show that only the one solution (6!7!=10!) to k!m!=n! exist where k<m<n-1<400,000,000.

The reason why this can be done reasonably quickly is that if any prime p exists in ]m,n], looping in n we can skip to the next one. So the loop it self is close to linear. as only a few m usually need to be checked for each n. Though the calculations in each step of course grows in complexity as n grows.

My method was to factorize the numbers in primes (dynamically extending the primes list as needed), and work with these factorisations. Then we are interested in the rather limited product defined by n!/m! that can easily be maintained quickly in the loop, looping m downwards, without doing the factorials fully. Then take the logarithm of this, and make a lookup into a list dynamically extended as needed with the (relatively) small potential log(k!). Find the one closest (binary search), and IF the log is quite close, do the actual prime-calculation of k! (using the prime-factorization) and see if this is actually equal to the product.

As Sterlings formula is not easily invertible, this not to much help here - though it can be used to populate the log(k!) table - but that is not where the computational time is used anyway

ADD: For anyone interested, the code can be found here: http://eskerahn.dk/wordpress/?p=1282