3
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ 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$? $\endgroup$
    – user642796
    Commented Apr 13, 2016 at 7:31
  • 1
    $\begingroup$ Is this allowed: $720=((1+1+1)!)!$? $\endgroup$
    – joro
    Commented Apr 13, 2016 at 14:32
  • $\begingroup$ Yes, it is actually, that was one of my problems with a general method $\endgroup$
    – user90242
    Commented Apr 13, 2016 at 14:36

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ 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. $\endgroup$
    – Tony Huynh
    Commented Apr 13, 2016 at 21:23
  • $\begingroup$ @Tony Huynh: Yes, thanks, I'll correct that. $\endgroup$
    – Douglas Zare
    Commented Apr 14, 2016 at 1:00

You must log in to answer this question.