# The 1-expression

A "1-expression" is a formula in which you add ($$+$$) or multiply ($$\times$$) the number 1 any number of times to create a natural number. Parentheses are allowed.

For example, you can create $$22$$ as follows:
$$1 + 1 + ((1 + 1 + 1 + 1) × (1 + 1 + 1 + 1 + 1)) = 22$$.
This is a 1-expression with 11 times a 1 in it.

You could also have done:
$$1 + ((1 + 1 + 1) × (1 + ((1 + 1) × (1 + 1 + 1)))) = 22$$.
This is a 1-expression with "1" only used ten times. Therefore, 10 is the minimum "1-value" of 22—that is, there is no 1-expression with which you can make 22 where you use a 1 less than 10 times.

• Is concatenating allowed (e.g. combining 2 1s to form an 11)? Commented Oct 16, 2018 at 13:39
• @ExcitedRaichu I'd assume not or else the minimum 1s for the example with 22 would be 4 instead of 10, (11 +11) Commented Oct 16, 2018 at 13:42
• @gabbo1092 oh right lol Commented Oct 16, 2018 at 13:42
• See oeis.org/A005245 — the “minimal 1-value” there is called the complexity of the number. Commented Oct 16, 2018 at 16:05

I may as well throw this out there:

$$((1 + 1)*(1+1)*(1+1)*(1+1+1)*(1+1+1))+1$$, for a total of 13 ones.

This was accomplished by multiplying together the prime factors of 72, and adding one.

• How do you verify that $13$ is minimal?
– Surb
Commented Oct 16, 2018 at 19:06
• @Surb To be honest — I'm not entirely sure. I kinda guess-and-checked with aimless logic here and there. I guess my only proof is: "nobody has found one for 12". Commented Oct 16, 2018 at 20:01
• @Surb if you're interested, check out oeis.org/A005245, posted by celtschk. It has some references to existing proofs. Commented Oct 16, 2018 at 20:04

I got this:

$$(1+1)\times(1+1)\times(1+1)\times(1+1+1)\times(1+1+1)+1 = 73$$ The minimum 1 value of 73 is 13

• Sadly, Hugh was 10 seconds quicker... Commented Oct 16, 2018 at 13:49
• Good job though. I guess we both went for the prime-factor-plus-one route. Commented Oct 16, 2018 at 13:50

Hugh and Keelhaul have already given correct solutions to the specific problem posed. If anyone wants to experiment with this, here's some fairly dumb Python code to find optimal solutions by brute force.

cache = {1: (1, '1')}
def best(n):
try: return cache[n]
except:
cache[n] = best1(n)
return cache[n]
def best1(n):
(cost,expr) = (n*n,'fail')
for m in range(1,n):
c0,c1 = best(m),best(n-m)
if c0[0]+c1[0]<cost: cost,expr = c0[0]+c1[0],c0[1]+'+'+c1[1]
d = round(n/m)
if m>1 and m*d==n:
c0,c1 = best(m),best(d)
if c0[0]+c1[0]<cost: cost,expr = c0[0]+c1[0],'('+c0[1]+')*('+c1[1]+')'
return (cost,expr)


A few empirical observations: when n is composite the best solution is usually the product of solutions for some factors of n. For n=10, n=22, n=25, n=28, n=33 there are equally good solutions using factorizations of n-1 instead. I think n=46 is the first time it's strictly better not to factorize n: 2*(2+3*(1+2*3)) costs 13, while 1+3*3*5 costs only 12. I bet there are n for which the best solution is of form a*b+c*d, but after a small amount of experimenting I haven't found one yet.

• For best(14) I get (8, '(1+1)*1+(1+1)*1+1+1))') with your code. While OEIS confirms the 8, the expression seems not quite right. Commented Oct 16, 2018 at 16:20
• Oops, there's a missing open-parenthesis. Copy-and-paste error. Will fix. [EDITED to add:] Fixed now. Sorry about that. Commented Oct 16, 2018 at 17:00
• Now the expression makes more sense. Thanks. Commented Oct 16, 2018 at 18:47
• From OEIS, we know that for $n=73$, the minimal number $\ge3\log_373$, or at least $12$. Commented Oct 16, 2018 at 19:41
• @TheSimpliFire: Actually, from OEIS we know that for $n=73$ the value is exactly 13. Commented Oct 16, 2018 at 20:55