# Time-efficient way of calculating the least number of 1s in a representation of $n$ using only the operations $+,!$

This was inspired by the following paper:

• J. Arias de Reyna, J. van de Lune, "How many $1$s are needed?" revisited, arXiv link.

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$?

• Do you know if there is an $n \geq 6$ such that $\| n \| \neq \| a \| + \| n-a! \|$ where $a$ is greatest such that $a! \leq n$? Apr 13, 2016 at 7:31
• Is this allowed: $720=((1+1+1)!)!$?
– joro
Apr 13, 2016 at 14:32
• Yes, it is actually, that was one of my problems with a general method
– user90242
Apr 13, 2016 at 14:36

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.
• I think you want $n_i \leq i$ instead of $n_i < i$. A slightly easier argument is to observe that $a_i!$ can occur at most $a_i$ times in any optimal representation for $n$ with the minimal number of terms. The rest follows since the base factorial representation of a number is unique. Apr 13, 2016 at 21:23