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!
score = 82 71 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,
    Add(u32, u32),
    Mul(u32, u32),
    Pow(u32, u32),
}

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

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


Try it online!