31
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ to be clear, is the trivial solution 11111111111 is forbidden? :D and slightly longer variants like +11111111111, (11111111111) etc. \$\endgroup\$ – innisfree Apr 22 at 6:48
  • 1
    \$\begingroup\$ @innisfree - the rules clearly say concatenation isn't valid, meaning you can't even have 11, let alone 11111111111. \$\endgroup\$ – Glen O Apr 22 at 8:50
  • \$\begingroup\$ Oh now I see, but I don’t think it’s that clearly stated \$\endgroup\$ – innisfree Apr 22 at 9:46
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Steve Bennett Apr 22 at 12:32
  • \$\begingroup\$ @steve and also weirdly stated because 1+1, which is allowed, is also a concatenation of 1, + and 1. \$\endgroup\$ – innisfree Apr 22 at 22:41
30
\$\begingroup\$

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: &[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!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ WolframAlpha. Do you have some generating code to post? \$\endgroup\$ – Jonathan Allan Apr 20 at 21:48
  • \$\begingroup\$ Is it expected that your program's solution for 111110 is worse than just doubling its solution for 55555? \$\endgroup\$ – Neil Apr 21 at 10:16
  • \$\begingroup\$ @Neil I fixed that a while ago, you must be using an old version. \$\endgroup\$ – Anders Kaseorg Apr 21 at 10:21
14
\$\begingroup\$

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)\$

| improve this answer | |
\$\endgroup\$
12
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I guess 111110 = 6 + 217*512 results in the same number of operations. \$\endgroup\$ – Neil Apr 21 at 12:42
  • \$\begingroup\$ You don't need the dot there. It's implicit. \$\endgroup\$ – S.S. Anne Apr 24 at 15:04
9
\$\begingroup\$

score = 22222222221

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

| improve this answer | |
\$\endgroup\$
8
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ 111 is an apt score :) \$\endgroup\$ – Steve Bennett Apr 21 at 7:38
4
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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 :) \$\endgroup\$ – Jonathan Allan Apr 20 at 21:28
  • \$\begingroup\$ @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. \$\endgroup\$ – Level River St Apr 20 at 21:32
  • \$\begingroup\$ With the fix I think it's 92 - WolframAlpha \$\endgroup\$ – Jonathan Allan Apr 20 at 21:38
3
\$\begingroup\$

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

1st attempt with manual calculator fiddling:

enter image description here

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

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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 \$.)

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – Sagittarius Apr 25 at 17:35
  • \$\begingroup\$ @Sagittarius I do need them: without them the exponents are done in the wrong order. \$\endgroup\$ – gadzooks02 May 3 at 12:42
  • \$\begingroup\$ how would that make a difference if there is only one exponent? I've seen other people leave them out \$\endgroup\$ – Sagittarius May 14 at 22:40
  • \$\begingroup\$ @Sagittarius Oh, yes for some parts. Honestly, I'd forgotten about this ages ago. \$\endgroup\$ – gadzooks02 May 19 at 9:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.