2
$\begingroup$

I am wondering how I should express a number with a sum of factorials. I know all numbers can be expressed with $1!$ obviously, but how should I go about expressing a number as a sum of factorials $\geq 2$. For example if we take $ 10$, it can be expressed as $3!+2!+2!, 2!+2!+2!+2!+2!$ or $12 = 3!+3!, 3!+2!+2!+2!, 6 \cdot 2!$

I understand that odd numbers can't be expressed in this way at all, however what would be the technique for finding all ways to express even numbers as factorials?

Thanks!

$\endgroup$

1 Answer 1

2
$\begingroup$

a) the "compact" representation

Same as what you do in representing a number in base $10$ or $2$, etc. you can do for representing it in the "factorial" base $1,2, 6, \cdots, n!$: refer to this Wikipedia article.
Only, instead of having a fixed ratio between the terms of the base (e.g. $10$, in the decimal) you will have a variable ratio $= n$, but that does not affect the algorithm substantially.

So let's take for instance $31=3 \cdot 10^1 + 1 \cdot 10^0= 10^1+10^1+10^1+10^0$.
$4! \le 31 < 5!$ so in the factorial base we will have $$ \eqalign{ & 31 = \left\lfloor {{{31} \over {4!}}} \right\rfloor 4! + 31\bmod 4! = 1 \cdot 4! + 7 \cr & 7 = \left\lfloor {{7 \over {3!}}} \right\rfloor 3! + 7\bmod 3! = 1 \cdot 3! + 1 \cr & 1 = \left\lfloor {{1 \over {2!}}} \right\rfloor 2! + 1\bmod 2! = 0 \cdot 2! + 1 \cr & 1 = \left\lfloor {{1 \over {1!}}} \right\rfloor 1! + 1\bmod 1! = 1 \cdot 1! + 0 \cr & \quad \Downarrow \cr & 31 = 4! + 3! + 1! \cr} $$

b) how many representations

Understanding that you are asking in how many ways we can represent $x$ as a linear combination of factorials $$ x = t_2 2! + t_3 3! + \cdots + t_n n! $$ that is how many $n$-uples $(t_2 , t_3 , \cdots , t_n)$ can we find such that the above identity is satisfied, given that $n$ is the max for which $n! \le x$.

Starting from the "compact" representation $$ x = c_2 2! + c_3 3! + \cdots + c_n n! $$ you can decide to downgrade either none, or one, or two, .., or or all the $c_n$ terms in $n!$ down to $n \cdot (n-1)!$.
The choices you have are $$ \sum\limits_{0\, \le \,k_{\,n} \, \le \,c_{\,n} } {1 } = c_{n } + 1 $$

That will make $c_{n-1}$ to become $c_{n-1},\;c_{n-1}+n,\;c_{n-1}+2n,\;\cdots,c_{n-1}+c_{n}n,\;$.

Then in turn, for each of the $c_{n-1}+k_{n} n$ you can decide to downgrade none, or one, or two.. Now, the total of choices becomes $$ \eqalign{ & \sum\limits_{0\, \le \,k_{\,n} \, \le \,c_{\,n} } {\sum\limits_{0\, \le \,k_{\,n - 1} \, \le \,c_{\,n - 1} + k_{\,n} n} 1 } = \sum\limits_{0\, \le \,k_{\,n} \, \le \,c_{\,n} } {\,c_{\,n - 1} + 1 + k_{\,n} n} = \cr & = \left( {c_{\,n - 1} + 1} \right)\left( {c_n + 1} \right) + \left( \matrix{ c_n + 1 \cr 2 \cr} \right)n \cr} $$

At the next step we will have $$ \eqalign{ & \sum\limits_{0\, \le \,k_{\,n} \, \le \,c_{\,n} } {\sum\limits_{0\, \le \,k_{\,n - 1} \, \le \,c_{\,n - 1} + k_{\,n} n} {\sum\limits_{0\, \le \,k_{\,n - 2} \, \le \,c_{\,n - 2} + k_{\,n - 1} \left( {n - 1} \right)} 1 } } = \cr & = \sum\limits_{0\, \le \,k_{\,n} \, \le \,c_{\,n} } {\sum\limits_{0\, \le \,k_{\,n - 1} \, \le \,c_{\,n - 1} + k_{\,n} n} {c_{\,n - 2} + 1 + k_{\,n - 1} \left( {n - 1} \right)} } = \cr & = \sum\limits_{0\, \le \,k_{\,n} \, \le \,c_{\,n} } {\left( {c_{\,n - 2} + 1} \right)\left( \matrix{ c_{\,n - 1} + k_{\,n} n + 1 \cr 1 \cr} \right) + \left( {n - 1} \right)\left( \matrix{ c_{\,n - 1} + k_{\,n} n + 1 \cr 2 \cr} \right)} \cr} $$ which does not look that may lead to a closed form.

$\endgroup$
2
  • $\begingroup$ +1 Your example is a little too special for my taste, since all the "digits" are $0$ or $1$, and that can't always be the case. I'd have calculated $100 = 4 \times 4! + 2!$. I think you have answered the question the OP meant to ask, but not the one actually asked, which calls for all the ways. That would mean allowing "digits" greater than $n-1$ in the column preceding $n$, so, for example $100 = 16 \times 3! + 2 \times 2!$. Harder to find and count, I think. $\endgroup$ Oct 5, 2017 at 0:22
  • $\begingroup$ @EthanBolker: your comment is fully right: I overlooked the OP final question. Thanks for signalling. I added a 2nd part to my answer $\endgroup$
    – G Cab
    Oct 5, 2017 at 16:20

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.