17
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ math.stackexchange.com/questions/112670/… $\endgroup$ – Carlo Beenakker Mar 9 '15 at 21:27
  • $\begingroup$ As a matter of interest ( though it must be well-known), you need for every prime $p$ that $ k+\ell - n = \sigma_{p}(k)+\sigma_{p}(\ell) - \sigma_{p}(n),$ where $\sigma_{p}(t)$ denotes the sum in $\mathbb{Z}$ of the digits in the base $p$ expression for $t$ when $t$ is a positive integer. $\endgroup$ – Geoff Robinson Mar 9 '15 at 21:33
  • $\begingroup$ A more general question is here: mathoverflow.net/questions/17058/factorials-in-pascals-triangle . The present question could be considered as a partial duplicate. $\endgroup$ – The Masked Avenger Mar 9 '15 at 21:45
  • $\begingroup$ Did you know, Twi, that there's a 3rd edition of Guy's book? $\endgroup$ – Gerry Myerson Mar 9 '15 at 22:19
  • $\begingroup$ Do you have a citation for the Erdős result? I'm interested... $\endgroup$ – Charles Mar 10 '15 at 20:49
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Some equations of the form $k!=P(n)$ ca be solved, but the case $P(n)=n(n-1)$ is still out of reach, I believe. mathoverflow.net/questions/39210/… $\endgroup$ – Gjergji Zaimi Mar 9 '15 at 22:20
  • $\begingroup$ Considering large prime divisors, one sees that the larger of k and l is no smaller than the largest prime less than n ( and n itself must be composite). Size considerations show that the numbers m between that largest prime and n cannot have large prime factors. Indeed, it might be proven that each such m must have three or more prime factors. $\endgroup$ – The Masked Avenger Mar 9 '15 at 23:02
  • $\begingroup$ @GjergjiZaimi: Yes, though Luca has reduced a broad class of them to the abc conjecture: web.math.pmf.unizg.hr/glasnik/37.2/37%282%29-04.pdf $\endgroup$ – Charles Jul 9 '15 at 13:58
3
$\begingroup$

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.

    1. 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.
    2. 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

$\endgroup$
  • $\begingroup$ You might find the following a fast preprocessing step: for each n from 2 to LIM^2, store each prime factor f at most LIM of n in a list for n+f. If n has no list, it is prime. Then for d from 0 to n-bigprime, build a list L of prime factors by adding those of n-d. If L misses a prime (e.g. L has 11 but not 7), n...(n-d) cannot be a product of factorials. You may find this divisionless method a quick preprocessing step to generate candidate pairs (n,d) for further testing. Look up "Happy New Prime Year" for an implementation. Gerhard "Loves Doing Prototypes In AWK" Paseman, 2016.04.23. $\endgroup$ – Gerhard Paseman Apr 23 '16 at 22:45
  • $\begingroup$ Thanks for the tip. I currently store the first first 26 millions primes less than 22222², found by the Sieve of Atkin. And then have both a bool-array and a list of prime to speed up things. It only take about 5 secs to calculate these / so well worth the effort. $\endgroup$ – Eske Rahn Apr 24 '16 at 0:30
  • $\begingroup$ You're welcome. I have not calculated the extra time for creating the list L, but the main loop is O(LIM^2*loglog(LIM^2)) time, and the memory used is O(LIM) bits. Also, except for the indices n of the factor lists, you can use 16 bit unsigned ints for LIM=2^16 - 1, so the arithmetic should be fast. Gerhard "Likes Low-Precision Methods For Accuracy" Paseman, 2016.04.23. $\endgroup$ – Gerhard Paseman Apr 24 '16 at 1:03
  • $\begingroup$ BTW, if the code is interesting to anyone in here, should I post it on "Mathoverflow" or "Stackoverflow", or just leave a link as i did? It is sort of in-between stuff - "code for math"... I would guess than an accurate struct for working in Q could be useful to others. Most likely I will 'nurse' it a bit further (just for fun), to see if I can make it run better. $\endgroup$ – Eske Rahn Apr 24 '16 at 1:38
  • $\begingroup$ Different forums have different conventions. If your code were as short as mine, it might be accepted if it were novel. I think the link instead was a good choice in your case for this forum. Gerhard "More Math Than Code Here" Paseman, 2016.04.23. $\endgroup$ – Gerhard Paseman Apr 24 '16 at 1:42

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.