[Question]
  [
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](https://en.wikipedia.org/wiki/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!
  
[Answer]
# 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!](https://tio.run/##ZY9RCoMwDIbfPUXoi4kdA9nzbjIG4joUREvrxoYUdoztel7EtVG36R6ahu//85Poe1s09W5QN21gD3EcH4YUJGAoKY3f9CZ27D7NR3WOGf6N0cJFo/ItiyA3Nct452jwa0XalHWL6ppVGJbdGqWrLFcojp3YgEgSFPSFLjD6JYSMgo0oampl/b2clDcXnyxSQVF2Oq2x9FhnRtVrAYPAS52FzRujvN5xrgTOkTDOOUDmDvrHM@0fryB1wcJEzmR2898WypbW96Wx/o7hDQ "Python 3 – Try It Online")
### Search program in [Rust](https://www.rust-lang.org/)
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: &[Option<Op>], z: u32, prec: u32) {
    match ops[z as usize].as_ref().unwrap() {
        Op::One => print!("1"),
        Op::Add(x, y) => {
            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 {
                                        visit(x.checked_add(y), Op::Add(x, y));
                                    }
                                }
                            }
                        }
                    }
                }
                _ => unreachable!(),
            }
            vs.push(v);
        }
        print!("{} = ", target);
        show(&ops, target, 0);
        println!();
    }
}
```
[Try it online!](https://tio.run/##7VfbbtpAEH3nKwaqIjslLiZvJiBV7WtLpUp9QRQ5ZoFNjG15vQ4E/Ot1Z40XfA2gpFIjdaUQ2D0zO5cz47HPWRDHnBFgwcwwiBP2G4134xnxaUiUz7brkA58IXd8oU4axOErGHmwbQCuER4lXz7NZgq/6XUAP9T91lduF7e@u4/ZrajRmDvAlrjresyA9njkBdR1bkfecNKBJwMSsOcTK/mqpreuzMBaAoqMn8BkwBl9IhPNZFOfzBVV486jb3qKRCd2eoaBtsJgiNqoEzSVlt5KjZLnwoV1BzaqQB1FxaLzxAgYQrdwIpbUqLTUfu4wyv2SfnbgCq/pFrBSCXyAopqM4KYseJ5tar1tUS4KImsno6C/VhT0Z13Va13VX8NVwcaTrvZey9WbmoT/2m4vS7gUjKJWbXx6L4lPlBbmyqTOoYrmrg@B6S9IANQB7BGGgb8Ylht7oJ6iq9oKa26HezvAD80zfUYyxZitRhuVrHgASdH/JNbtseyHMICQWM3xN@w6fXmjLHIsDn3SL@kJUzXiD9vEUUkG@7ikNoGmaBoFpRONsilzVyTXMXL69@qF6grNOSRlNEDMDhPueruKLGCOBPiHuG@NzIN1BSgFruF2IENQDUqBwqt13iEH41dyqLgKcmhNYpfrFRhSXKHmcbZE@@thUeO83fxOVA6rTUJii7AzzSbIxzKCWa6PrT1FfoReHrJ/WuwP31dWRrfcADLBTdUPKpvOISIi8UoSPV3tyOdNTXyqYyMqjIri0jUtuVNjZsB9M6DOYsr4HSp@xgARiHsMwt7aazT2Gmh9esRlXFzWDtmYwhX0NC35hyXWm5ygjRAOpfD9Xvj@XGGpoL0WGvgZ6IPERkiEZ0ocs7LWrCWxHshs6mFf3aTpOXT/E1x/PmnnI6IXl0olSS6gxEV0EBQ6UkK/nBKoIEML/V@mxQpnHkmLw/zzZmhR3tHr@9n/JvPX2WTie4Rk0@Gd4g2zaSrYxB2fmNbSvLNJU8m8OJVF8DmdDAdhxuUjQg6h2whp1Oqk000Gmsy@7WT43Z/lB@BE3naacg7AWTWOY12sbqx3cem/rbltLlh8PfoD "Rust – Try It Online")
[Answer]
# 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](https://www.wolframalpha.com/input/?i=%28%28%28%281%2B1%29%5E%281%2B1%2B1%29%28%28%281%2B1%2B1%29%5E%281%2B1%29%29%5E%281%2B1%2B1%2B1%29%29%2B%28%281%2B1%2B1%29%28%28%281%2B1%2B1%29%5E%281%2B1%29%29%5E%281%2B1%29%29%29%2B%281%2B1%29%5E%281%2B1%2B1%29%29%28%28%281%2B1%29%5E%281%2B1%2B1%2B1%29%2B1%29%5E%281%2B1%29%29%2B%28%281%2B1%29%5E%281%2B1%2B1%29%29%29%28%281%2B1%2B1%29%5E%281%2B1%2B1%2B1%29%29%2B2%29%28%281%2B1%2B1%29%5E%281%2B1%29%29%2B1%2B1)**
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](https://www.wolframalpha.com/input/?i=%28%281%2B1%29%281%2B1%2B1%29%5E%281%2B1%29%29%5E%28%281%2B1%29%5E%281%2B1%2B1%29%29%2B%28%281%2B1%29*%28%281%2B1%2B1%29%5E%281%2B1%29%29*%28%281%2B1%2B1%2B1%2B1%29%5E%281%2B1%29%29%29%5E%281%2B1%2B1%29%2B%28%281%2B1%2B1%29%5E%281%2B1%2B1%29%29%5E%281%2B1%2B1%29%2B%28%28%281%2B1%29%281%2B1%2B1%29%5E%281%2B1%29%29%5E%281%2B1%2B1%29%29%2B%281%2B1%29%28%281%2B1%2B1%29%5E%281%2B1%29%2B1%29)**
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)\$
[Answer]
# 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!](https://tio.run/##XY9fCsIwDMbfd4rSlyWrCMNnbyKDMisbjK20U5RS2DH0el5kpplDGemf8Pu@pKl9jM3QH2Zzt04cRZ7np7lUQIs2BVaBzrgmS0RMIi6OfzPj1fl1VQHKX3mMONMjmXVtP4K56Q7S03tnbKdrA7IKcidkUYDEH4yJ4T9BYJRsiNnQG0/Tc6d6uFJnWUrM9Pm8xYqw1c70WwGSwENdpK8HZ0gP3FcJ7qPEUhcFMI/iPT3L9/RKUkgWJmolq5vvsTG@9ZS3ztM/5g8 "Python 3 – Try It Online")
Verifier thanks to @AndersKaseorg
34 `1`s, 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.
[Answer]
### score = 22222222221
The sequence $$1 + 1 +\ ... 1$$ where `...` is 11111111108 pairs of `1 +`. I think I can probably shorten this, though.
[Answer]
# 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!](https://tio.run/##y0osSyxOLsosKNHNy09J/e@nYPtfQ0PDUNtQU0srGkiBYKw2Oh@LCigPKofER@Ghq0KRBYujGYxqDAT@T87PK87PSdXLyU/X8NP8DwA "JavaScript (Node.js) – 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$$
[Answer]
# 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](https://www.wolframalpha.com/input/?i=%28%281%2B1%29%281%2B1%2B1%29%5E%7B1%2B1%7D%29%5E%7B%281%2B1%29%5E%7B1%2B1%2B1%7D%7D%2B%28%281%2B1%29%5E%7B%281%2B1%29%281%2B1%2B1%29%5E%7B1%2B1%7D%7D%2B%28%281%2B1%2B1%2B1%2B1%29%281%2B1%2B1%29%281%2B1%2B1%2B1%29%29%5E%7B1%2B1%7D%2B1%29%281%2B1%2B1%2B1%2B1%2B1%2B1%29%5E%7B1%2B1%2B1%7D)**
**Check calculation Link to TIO, Ruby language** (wolfram alpha website is playing up for me)
[Try it online!](https://tio.run/##KypNqvz/v0BBQ8NQ21BTC0SCaDBDE0RrIPggEW24AFYNEGltqKAGCg01EEQjC2ojmwBk/P8PAA "Ruby – Try It Online")
[Answer]
# 135 = 67 '1's + 49 '+'s + 19 parens
1st attempt with manual calculator fiddling:
[![enter image description here](https://i.stack.imgur.com/UIFaR.png)](https://i.stack.imgur.com/UIFaR.png)
### 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](https://www.wolframalpha.com/input/?i=%281%2B%281%2B1%29%5E%281%2B1%29%5E%281%2B1%29%281%2B1%2B1%29%281%2B1%2B1%2B%281%2B1%29%5E%281%2B1%2B1%29%29%281%2B%281%2B1%2B1%2B1%2B1%29%281%2B1%29%5E%281%2B1%2B1%29%29%29%281%2B%281%2B1%29%281%2B1%2B1%2B%281%2B1%29%5E%281%2B1%2B1%29%29%281%2B%281%2B1%2B1%2B1%2B1%29%281%2B1%29%5E%281%2B1%2B1%29%29%281%2B1%2B%281%2B1%2B1%29%5E%281%2B1%2B1%2B1%29%281%2B1%2B1%2B1%2B1%2B1%2B1%29%29%29)
[Answer]
# Score ~~115~~ ~~97~~ 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 \$.)
[Answer]
# Score 187 (87 `1`s, 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!](https://www.desmos.com/calculator/ezzk4gllap)
Based on the fact that $$11111111110 = 2×5×11×41×271×9091$$ The formula is that, based on powers of two.
]