What are some other ways to compute the factorials using addition only?

Does it count if it uses circling? I did a Google search and found some pages from The Book of Numbers about Alfred Moessner's theorem which I read long ago and forgot about.

$$\begin{array}{c} \fbox{1} & 2 & \fbox{3} & 4 & 5 & \fbox{6} & 7 & 8 & 9 & \fbox{10}\\ & \fbox{2} & & 6 & \fbox{11} & & 18 & 26 & \fbox{35}& \\ & & & \fbox{6} & & & 24 & \fbox{50} & & \\ & & & & & & \fbox{24} & & & \\ \end{array}$$

To figure out $n!$, figure out what the $n$th triangular number $T_n$ is. For this example, that would be 10. Write the integers from 1 to $T_n$ in a line and circle the triangular numbers.

Then on the next line, add up the numbers that have not been circled so far, writing the running sum in the appropriate spots. Now circle the first number of this second line, the third number, the sixth number, and so on according to the triangular numbers.

On the third line, add up the numbers from the second line that have not been circled so far, writing the running sum in the appropriate... you get the idea. Repeat the process until you have a line with a single number: $n!$

For very small $n$, Moessner's algorithm should deliver results almost instantaneously. But even then it should benchmark slower than the usual recursion algorithm.


$n! = \sum_{k_1=1}^1 \sum_{k_2=1}^2 \cdots \sum_{k_n=1}^n 1\;$ is similar to your example except using summation notation. in $\;\texttt{PARI/GP}\;$ it looks like $\texttt{sum(k_1=1, 1, sum(k_2=1, 2, sum(k_3=1, 3, 1)))}\;$ for $n=3$ and similar code in other programming languages. The general case is very similar using recursion: $\texttt{f(n) = if( n<1, n==0, sum(k=1, n, f(n-1)))}\;$ and similar code in other programming languages. The key idea is exactly that multiplication is repeated addition, however, implicit in this is that there is a way to control the number of additions. We use the index $k$ of $\;n\cdot m=\sum_{k=1}^n m\;$ to accomplish this and similarly in a programming language.

The Moessner algorithm described in another answer is based on a triply indexed recursion such as $f(n,i,j) = 0\;$ if $\;n<i,\; i<j,\;$ or $\;j<0.$ $\quad f(n,i,0) = 1\;$ if $\;0\le i\le n.$ $f(n,i,i) = f(n,i\!-\!1,i\!-\!1)+f(n\!-\!1,n\!-\!1,i).\quad$ $f(n,i,j) = f(n,i\!-\!1,j\!-\!1)+f(n,i\!-\!1,j).\quad$ Here $\;n!=f(n,n,n).\;$ Notice that OEIS sequence A094638 is $f(n,n,j)$ and A096747 is $f(n,j,j)$.

This is only one out of many multiply indexed recursions which can compute $\;n!\;$ by addition only. However, they are all more complicated than the simple doubly indexed recursion $f(n,k) = 0\; \text{ if } \;n<k\; \text{ or }\;k<0. \quad f(0,0) = 1. \quad f(n,0) = 0,\; \text{ if } \;n>0.$ $f(n,k) = f(n,k\!-\!1)+f(n\!-\!1,n\!-\!1),\; \text{ if } \;k>0.\;$ Here $\;n! = f(n,n).$

In more generality, this question is related to Addition chains for positive integers, and with even more generality, to the topic of Straight-line programs for finite group elements.


Take an $n$ letter word with distinct letters. Use casework to find the number of cases there are, adding by $1$ for each case. That number is $n!$.