This was inspired by the following paper:


* J. Arias de Reyna, J. van de Lune, *"How many $1$s are needed?" revisited*, [arXiv link](http://arxiv.org/abs/1404.1850).


It might help explain my question better, because my question is actually similar to those in the problem.


So, I was curious, what if we were only allowed to use the operations $+,!$.


Using the same notation as the paper, $$\|a\|$$ is the least number of 1's used to represent $a$ using the provided (above) symbols (and parentheses). If my explanation is not great, here are some values of $\|a\|$.


* $\|1\|=\|1\|=1$
* $\|2\|=\|1+1\|=2$
* $\|3\|=\|1+1+1\|=3$
* $\|6\|=\|(1+1+1)!\|=3$
* $\|121\|=\|(1+1+1+1+1)!+1\|=6$


What would be a time-efficient means of calculating $\| a \|$ for large $a$?



Time-efficient way of calculating the least number of 1s in a representation of $n$ using only the operations $+,!$
Arjafi's comment shows how to compute $\|a\|$, so this variant is much simpler than using $\{+,\times\}$.


Suppose $n = \sum\_i n\_i i!$ with $n\_i \le i$. This is the "base factorial" expression for $n$. Then $\| n\|= \sum\_i n\_i \| i!\| = \sum\_i n\_i \|i\|$.


Proof: Suppose $n$ is the smallest counterexample. For some sequence $\{a\_i\}$, $n = \sum a\_i!$ so that $\|n\| = \sum \|a\_i\|$ and among these, the number of terms is minimal. This is better than the base factorial expression for $n$, so it must be different. Consider the lowest nonzero factorial used in the base factorial expression for $n$, $m!$. This can't be in the better expression or else we could create a smaller counterexample. All higher factorials vanish mod $m!$, so it must be that our smallest counterexample $n$ equals $m!$. 


So, we have a better expression for $m!$ than as $(m)!$. Since this is the smallest counterexample, with the fewest terms, we don't have a better expression for $(m-1)!$. So, the expression for $m!$ must be $(m-1)!+(m-1)!+...+(m-1)!$. However, this is not better than $(1+1+...+1)!$ with $m$ $1$s. 


