Can the factorial of $N$ always be expressed by the sum(addition and subtraction) or the product of two other factorials?
Do there always exist integer $A$ and $B$ such that $N! = A! + B!$, or $N! = A! – B!$, or $N! = A!\cdot B!$ ?
elementary-number-theoryfactorial
Can the factorial of $N$ always be expressed by the sum(addition and subtraction) or the product of two other factorials?
Do there always exist integer $A$ and $B$ such that $N! = A! + B!$, or $N! = A! – B!$, or $N! = A!\cdot B!$ ?
Below is a sketch of a little-known purely arithmetical proof that binomial coefficients are integral. I purposely constructed the proof so that it would be comprehensible to an educated layperson. The proof gives an algorithm to rewrite a binomial coefficient as a product of fractions whose denominators are coprime to any given prime. The method of proof is best comprehended by applying the algorithm to a specific example.
[Note: It may prove helpful to first read this simpler example before proceeding to the exposition below].
E.g. consider $\ \ \binom{39}{17}\: =\: \frac{39!}{22! \; 17!}\: =\: \frac{23 \cdot 24 \cdots\; 39}{1 \cdot 2 \cdots\; 17}.\, $ When this fraction is reduced to lowest terms $\rm\:a/b,\, $ no prime $\rm\ p > 17\ $ can divide its denominator $\rm\: b,\: $ since $\rm\ b\:|\:17\:!\ \:$ Hence, to show that $\rm\ a/b\ $ is an integer, it suffices to show that no prime $\rm\ p \le 17\ $ divides its denominator $\rm\: b$.
E.g. we show that $2$ doesn't divide $\rm b$. The highest power of $2$ in the denominator terms is $16 < 17$. Align the numerators & denominators $\rm (mod\ 16)$ by shifting the 1st numerator term so it lies above its value $\!\bmod 16,\,$ viz. $\,\color{#c00}{23 \equiv 7} \pmod{\!16}$ so right-shift the numerator terms until $23\:$ lies above $7$
$$\color{#0a0}{\frac{}{1}\frac{}{2}\frac{}{3}\frac{}{4}\frac{}{5}\frac{}{6}}\color{#c00}{\frac{23}{7}}\frac{24}{8}\frac{25}{9}\frac{26}{10}\frac{27}{11}\frac{28}{12}\frac{29}{13}\frac{30}{14}\frac{31}{15}\frac{32}{16}\frac{33}{17}\color{#0a0}{\frac{34}{}\frac{35}{}\frac{36}{}\frac{37}{}\frac{38}{}\frac{39}{}}$$
We claim that $2$ doesn't divide the reduced denominator of each aligned fraction. Indeed $\ 24/8 = 3$, $\: 26/10 = 13/5 $, $\:\ 28/12 = 7/3 $, $\:\ 30/14 = 15/7 $, $\:\ 32/16 = 2$. This holds because these fractions $\rm\; c/d \;$ satisfy $\,\rm c \equiv d\ (mod\ 16)\:$ i.e. $\rm c = d + 16\: n \;$ so $\,\rm 2|d \Rightarrow 2|c$, $\rm\; 4|d \Rightarrow 4|c$, $\:\cdots $, $\rm\; 16|d \Rightarrow 16|c$, i.e. any power of $2\:$ below $16$ that divides $\rm d$ must also divide $\rm c$, so it cancels out upon reduction.
Therefore to prove that $2$ doesn't divide the reduced denominator of $\binom{39}{17}$ it suffices to prove the same for the "leftover" fraction $\,\color{#0a0}{(34 \cdots 39)/(1 \cdots 6) = \binom{39}{6}}\,$ composed of the above non-aligned terms. Being an $\rm\binom{n}{k}$ with smaller $\rm k = 6 < 17,\,$ this follows by induction.
Since the same proof works for any prime $\rm p$, we conclude that no prime divides the reduced denominator of $\binom{39}{17}$, therefore it is an integer.$\quad$ QED
Informally, the reason that this works is because the denominator sequence starts at $1$, which is coprime to every prime $\rm p$. This ensures that it is the "greediest" possible contiguous sequence of integers, in the sense that its product contains the least power of $\rm\:p\:$ compared to other contiguous sequences of equal length.
The algorithm extends to multinomials by using the simple reduction of multinomials to products of binomials mentioned in my prior post here.
EDIT: Wrote a command to do sum of distinct factorials by greedy algorithm; here are the perfect powers I have, not allowing $0!$.
jagy@phobeusjunior:~$ ./greedy_factorial
Sat Dec 13 12:25:29 PST 2014
0
1 1
8 3 2
9 3 2 1
25 4 1
27 4 2 1
32 4 3 2
121 5 1
128 5 3 2
144 5 4
729 6 3 2 1
841 6 5 1
5041 7 1
5184 7 5 4
45369 8 7 3 2 1
46225 8 7 6 5 4 1
363609 9 6 3 2 1
403225 9 8 4 1
3674889 10 8 7 6 3 2 1
1401602635449 15 14 13 12 11 10 9 8 7 3 2 1
Sat Dec 13 12:26:23 PST 2014
Did not get any more cubes yet.
jagy@phobeusjunior:~$ ./greedy_factorial
0 square root 0 =
1 square root 1 = 1
8 = 2^3
9 square root 3 = 3
25 square root 5 = 5
27 = 3^3
32 = 2^5
121 square root 11 = 11
128 = 2^7
144 square root 12 = 2^2 3
729 square root 27 = 3^3
841 square root 29 = 29
5041 square root 71 = 71
5184 square root 72 = 2^3 3^2
45369 square root 213 = 3 71
46225 square root 215 = 5 43
363609 square root 603 = 3^2 67
403225 square root 635 = 5 127
3674889 square root 1917 = 3^3 71
1401602635449 square root 1183893 = 3 394631
Allowing $0!$ adds in the square $4,$ I'm not sure i see any other change. Not sure why the program is so very slow. As I said, if all you want is cubes, you can program in a greedy algorithm which, for each cube, will rapidly attempt a decomposition as distinct factorials (with repeat 1 for $0!$ if you wish ) and report success.
ALLOWING 0! = 1 ***+++***
jagy@phobeusjunior:~$ ./greedy_factorial
Sat Dec 13 11:46:03 PST 2014
0 eleventh root 0
1 eleventh root 1
4 square root 2
8 cube root 2
9 square root 3
25 square root 5
27 cube root 3
32 fifth root 2
121 square root 11
128 seventh root 2
144 square root 12
729 cube root 9
841 square root 29
5041 square root 71
5184 square root 72
45369 square root 213
46225 square root 215
363609 square root 603
403225 square root 635
3674889 square root 1917
1401602635449 square root 1183893
Sat Dec 13 11:46:36 PST 2014
jagy@phobeusjunior:~$
Best Answer
If you want $N! = A! + B!$, then $A,B <N$. Hence, $N! = A! + B! \leq 2(N-1)!$. This is possible only if $N =2$.