# Make 1s using a bunch of 1s

Your task is to form an expression equaling $$\ 11111111111 \text{ (11 ones)} \$$ using only the following characters: 1+(). Keep in mind that the result is in base 10, and not some other base like binary. Of course, these expressions should follow the order of operations.
Furthermore, the only operations which should be performed are addition, multiplication, and exponentation.

Some examples of valid expressions include

$$1 + 1 + 1 = 3$$ $$(1 + 1)(1 + 1) = 4$$ $$(1 + 1)^{1 + 1 + 1} = 8$$ $$1 + (1 + 1(1 + 1)^{1 + 1^{1 + 1}}) = 6$$

Some examples of invalid expressions include

$$11 + 11 \quad | \quad \text{concatenation of ones}$$ $$1 + ((1) \quad | \quad \text{unbalanced parentheses}$$ $$\displaystyle\binom{1}{1 + 1} \quad | \quad \text{disallowed operation}$$

## Scoring

After forming an expression which equals $$\ 11111111111 \$$, your score will be calculated by the sum of the $$\ \text{no. of 1} \$$, the $$\ \text{no. of +} \$$, and the $$\ \text{no. of} \$$ pairs of parentheses. For example, $$\ (1 + 1)(1 + 1)^{1 + (1)} \$$ has a score of $$\ 12 \$$, because it has $$\ 6 \$$ $$\ 1 \$$s, $$\ 3 \$$ pluses, and $$\ 3 \$$ pairs of parentheses.

The submission with the lowest score wins!

• to be clear, is the trivial solution 11111111111 is forbidden? :D and slightly longer variants like +11111111111, (11111111111) etc. Apr 22, 2020 at 6:48
• @innisfree - the rules clearly say concatenation isn't valid, meaning you can't even have 11, let alone 11111111111. Apr 22, 2020 at 8:50
• Oh now I see, but I don’t think it’s that clearly stated Apr 22, 2020 at 9:46
• It's clear (it's the first example of an invalid expression), it's just a bit weirdly stated, since "concatenation" wouldn't normally be thought of as an operation. Apr 22, 2020 at 12:32
• @steve and also weirdly stated because 1+1, which is allowed, is also a concatenation of 1, + and 1. Apr 22, 2020 at 22:41

# score = 8271 69 (34 ‘1’s + 23 ‘+’s + 12 parenthesis pairs)

$$\begin{multline*} 11111111111 = 1 + (1 + 1) \cdot {} \\ (1 + 1 + 1 + (1 + 1)^{(1 + 1)^{1 + 1 + 1}}(1 + ((1 + 1)(1 + 1 + 1))^{1 + 1 + 1})) \cdot {} \\ (1 + (1 + (1 + 1 + 1)^{1 + 1})^{1 + (1 + 1)^{1 + 1}}) \end{multline*}$$

Try it online!

### Search program in Rust

This finds optimal solutions for up to about 8 digit numbers. Don’t try it on anything larger—it will eat all your memory.

I constructed the above solution by manually writing $$\11111111111 = 1 + 111110 \cdot 100001\$$ and searching for optimal solutions to $$\111110\$$ and $$\100001\$$.

use std::env;

#[derive(Clone, Debug)]
enum Op {
One,
Mul(u32, u32),
Pow(u32, u32),
}

fn show(ops: &[Option<Op>], z: u32, prec: u32) {
match ops[z as usize].as_ref().unwrap() {
Op::One => print!("1"),
if prec > 0 {
print!("(");
}
show(ops, *x, 0);
print!(" + ");
show(ops, *y, 0);
if prec > 0 {
print!(")");
}
}
Op::Mul(x, y) => {
if prec > 1 {
print!("(");
}
show(ops, *x, 1);
show(ops, *y, 1);
if prec > 1 {
print!(")");
}
}
Op::Pow(x, y) => {
if prec > 2 {
print!("(");
}
show(ops, *x, 3);
print!("^{{");
show(ops, *y, 0);
print!("}}");
if prec > 2 {
print!(")");
}
}
}
}

fn main() {
for target in env::args().skip(1).map(|arg| arg.parse().unwrap()) {
let mut ops: Vec<Option<Op>> = vec![None; target as usize + 1];
let mut vs: Vec<Vec<u32>> = vec![];
while !ops[target as usize].is_some() {
let mut v: Vec<u32> = vec![];
let mut visit = |x, op| {
if let Some(x) = x {
if x <= target {
if ops[x as usize].is_none() {
ops[x as usize] = Some(op);
v.push(x);
}
}
}
};
let level = vs.len();
let score = level / 2;
match level % 2 {
0 => {
if score == 1 {
visit(Some(1), Op::One);
}
for i in 1..score.saturating_sub(1) {
let j = score - 1 - i;
for u in &vs[i * 2..i * 2 + 2] {
for v in &vs[j * 2..j * 2 + 2] {
for &x in u {
for &y in v {
visit(x.checked_pow(y), Op::Pow(x, y));
}
}
}
}
}
for i in 1..score {
let j = score - i;
for u in &vs[i * 2 - 1..i * 2 + 1] {
for v in &vs[j * 2 - 2..j * 2 + 1] {
for &x in u {
for &y in v {
visit(x.checked_mul(y), Op::Mul(x, y));
}
}
}
}
}
}
1 => {
for i in 1..score.saturating_sub(1) {
let j = score - 1 - i;
for u in &vs[i * 2..i * 2 + 2] {
for v in &vs[j * 2..j * 2 + 2] {
for &x in u {
for &y in v {
}
}
}
}
}
}
_ => unreachable!(),
}
vs.push(v);
}
print!("{} = ", target);
show(&ops, target, 0);
println!();
}
}


Try it online!

• WolframAlpha. Do you have some generating code to post? Apr 20, 2020 at 21:48
• Is it expected that your program's solution for 111110 is worse than just doubling its solution for 55555?
– Neil
Apr 21, 2020 at 10:16
• @Neil I fixed that a while ago, you must be using an old version. Apr 21, 2020 at 10:21

# By hand -  118 112 111  82

$$(1+(1+1)^{(1+1)^{1+1}}(1+(1+1)(1+(1+(1+1)^{1+1})^{1+1})^{1+1}))(1+(1+1+(1+1+1)^{1+1})(1+1+(((1+1)(1+1+1))^{1+1})^{1+1+1}))$$

Try it at Wolfram Alpha

This was found by working my way down from $$\11111111111\$$ looking for close divisibility considering factors which are close in construction to powers and is:

$$(((8(9^4)+(3(9^2))+8)((16+1)^2)+8)81+2)9+2$$

There are $$\16\$$ parentheses pairs, $$\40\$$ ones, and $$\26\$$ additions.

Previous @111

$$((1+1)(1+1+1)^{1+1})^{(1+1)^{1+1+1}}+((1+1)(1+1+1)^{1+1}(1+1+1+1+1)^{1+1})^{1+1+1}+((1+1+1)^{1+1+1})^{1+1+1}+((1+1)(1+1+1)^{1+1})^{1+1+1}+(1+1)((1+1+1)^{1+1}+1)$$

Try it at Wolfram Alpha

This is $$18^8+450^3+(3^3)^3+18^3+20$$ Where:
$$\18 = 2\times 9 = (1+1)(1+1+1)^{1+1}\$$
$$\8 = 2^3 = (1+1)^{1+1+1}\$$
$$\450 = 18\times 25 = (1+1)(1+1+1)^{1+1}(1+1+1+1+1)^{1+1}\$$ $$\20 = 2\times (9+1) = (1+1)((1+1+1)^{1+1}+1)\$$

# 69 operations

$$1+(1+((1+1+1)^{1+1}+1)^{1+1+1+1+1})(1+1)\\ \cdot(1+1+1+(1+((1+1+1)(1+1))^{1+1+1})(1+1)^{(1+1)^{1+1+1}})$$

Try it online!

Verifier thanks to @AndersKaseorg

34 1s, 24 +s, 11 ()s.

Decomposition, by layers:

• 11111111111 = 100001 * 111110 + 1
• 100001 = 10^5+1
• 111110 = 55555*2
• 55555 = 3 + 217*256
• 217 = 6^3+1
• 256 = 2^2^3

I wrote a program to brute-force this, but I'm still working on the program.

• I guess 111110 = 6 + 217*512 results in the same number of operations.
– Neil
Apr 21, 2020 at 12:42
• You don't need the dot there. It's implicit. Apr 24, 2020 at 15:04

### score = 22222222221

The sequence $$1 + 1 +\ ... 1$$ where ... is 11111111108 pairs of 1 +. I think I can probably shorten this, though.

# Score:  113  111

Breakdown:

• ones: $$\56\$$
• plus signs: $$\45\$$
• pairs of parentheses: $$\10\$$
• no multiplication

The expression below is in JS syntax, with $$\p^q\$$ computed as p**[q].

(((1+1)**[1+1+1+1]+1+1)**[1+1+1+1]+((1+1)**[1+1+1+1]+1)**[1+1]+((1+1+1)**[1+1]+1+1+1)**[1+1])**[1+1]+((1+1+1+1+1+1)**[1+1+1]+(1+1)**[1+1+1+1])**[1+1]+1+1+1+1+1+1


Try it online!

## Formula

$$(((1+1)^{1+1+1+1}+1+1)^{1+1+1+1}+((1+1)^{1+1+1+1}+1)^{1+1}+((1+1+1)^{1+1}+1+1+1)^{1+1})^{1+1}+((1+1+1+1+1+1)^{1+1+1}+(1+1)^{1+1+1+1})^{1+1}+1+1+1+1+1+1$$

which simplifies down to:

$$\big((2^4+2)^4+(2^4+1)^2+(3^2+3)^2\big)^2+(6^3+2^4)^2+6$$ $$=(18^4+17^2+12^2)^2+232^2+6$$ $$=105409^2+232^2+6$$ $$=11111057281+53824+6$$ $$=11111111111$$

• 111 is an apt score :) Apr 21, 2020 at 7:38

# Score 92 (46 1's, 33 +'s, 13 parentheses)

$$((1+1)(1+1+1)^{1+1})^{(1+1)^{1+1+1}}$$

$$+$$

$$((1+1)^{(1+1)(1+1+1)^{1+1}}+((1+1+1+1+1)(1+1+1)(1+1+1+1))^{1+1}+1)$$

$$*$$

$$(1+1+1+1+1+1+1)^{1+1+1}$$

18^8 + (2^18+60^2+1) * 7^3

18^8 + 91,150,535 Similar to Jonathan Allen but I factorize the 91,150,535.

Try at wolfram Alpha

Check calculation Link to TIO, Ruby language (wolfram alpha website is playing up for me)

Try it online!

• You have a typo (twice) -- 91,150,535. Also, I think you have 30 rather than 60. Other than that I think this will be crushing :) Apr 20, 2020 at 21:28
• @JonathanAllan yeah typing this up is almost as hard as solving it! I was already working on the 18^8 when I saw your answer, but you got it out first. Apr 20, 2020 at 21:32
• With the fix I think it's 92 - WolframAlpha Apr 20, 2020 at 21:38

# 135 = 67 '1's + 49 '+'s + 19 parens

1st attempt with manual calculator fiddling:

### Method

• 11111111111 = 21649*513239
• 21649 = 1 + ((2^4)*3*11*41)
• 513239 = 1 + (2*11*41*569)
• 569 = 2 + (3^4)*7
• then the small numbers are built up manually

Try it on Wolfram-Alpha

# Score 11597 93

$$\ ((1+1)^{(1+1+1)^{1+1+1}}+((1+1+1)^{1+1+1}+1+1)((1+1+1)^{1+1}(((1+1)^{(1+1)^{1+1}}+1)^{1+1+1}+1+1+1+1+1)+1))((1+1+1)^{1+1+1+1}+1)+1 = (2^{3^3}+(3^3+2)(3^2((2^{2^2}+1)^3+5)+1))(3^4+1)+1 = (2^{27}+29(9(17^3+5)+1)))(82)+1 = (2^{27}+29(44263))(82)+1 = 135501355(82)+1 = 11111111111\$$

Found by using @AndersKaseorg's Rust program to generate a solution for $$\ 44263 \$$. (I was using an old version of his program when I created my previous answer; the current version also finds this answer when I plug in $$\ 1283627 \$$.)

# Score 187 (87 1s, 68 +s, 32 () pairs)

$$\begin{multline*} \left(1+1\right)\left(1+1+1+1+1\right)\left(\left(1+1\right)^{\left(1+1+1\right)}+1+1+1\right) \\ \left(\left(1+1\right)^{\left(1+1+1+1+1\right)}+\left(1+1\right)^{\left(1+1+1\right)}+1\right) \\ \left(\left(1+1\right)^{\left(\left(1+1\right)^{\left(1+1+1\right)}\right)}+\left(1+1\right)^{\left(1+1+1\right)}+1+1+1+1+1+1+1\right) \\ \left(\left(1+1\right)^{\left(\left(1+1\right)^{\left(1+1+1\right)}+1+1+1+1+1\right)}+\left(1+1\right)^{\left(\left(1+1\right)^{\left(1+1+1\right)}+1\right)} \right. \\ \left. {} +\left(1+1\right)^{\left(\left(1+1\right)^{\left(1+1+1\right)}\right)}+\left(1+1\right)^{\left(1+1+1+1+1+1+1\right)}+1+1+1\right)+1 \end{multline*}$$

Try it online!

Based on the fact that $$11111111110 = 2×5×11×41×271×9091$$ The formula is that, based on powers of two.

• this could be optimized a fair bit, for example you could replace each instance of (1+1)^(1+1+1) + 1 with (1+1+1)^(1+1) and subtract 2 from your score each time - EDIT: you also don't need the parentheses in the exponents Apr 25, 2020 at 17:35
• @Sagittarius I do need them: without them the exponents are done in the wrong order. May 3, 2020 at 12:42
• how would that make a difference if there is only one exponent? I've seen other people leave them out May 14, 2020 at 22:40
• @Sagittarius Oh, yes for some parts. Honestly, I'd forgotten about this ages ago. May 19, 2020 at 9:52