3 = 123+4+5-6*7^89

First verifiable instance of error?

Did a little fishing for overflow candidates with the following regex:

  [1-9]{3,}\^[1-9]{3,}

...caught 58 results between 266 and 10940:

  266 = 123^456-78-9
  ...
  10940 = 12345^6789

My kung fu isn't Python so I don't know how types are handled. That eval() function sure smells suicidal for anything remotely serious though.

No, Python doesn't have integer overflow.

"^" is the XOR operator. GP's code has that bug.

> That eval() function sure smells suicidal for anything remotely serious though.

Yes, ast.literal_eval() should be used.

Ugh, fixed it.

Using * * is not really an option now because it takes insane amounts of time to compute something like `123456789`.

And this is just a tiny script - `eval` shouldn't really be an issue. And yes, I know it's evil, generally. But if you think about it, Python itself is just one big eval loop :P

I added division and brackets. This gets every number up to 5397, with only about 400 numbers still missing overall (<5%), but run time goes up to 40 minutes.

Potentiation is a problem though (particularly when combined with brackets) as Python becomes impossibly slow using bignums. (I estimate it will take several days of compute time to test all 250 million possibilities, unless I put some effort into speeding it up significantly.) But at least it would prove definitively whether 10958 is possible.

If the only goal were to search for a solution to 10958 though, it should be fairly straightforward to re-order the search in approximately ascending order of compute cost so that if a simple solution exists it will be found quickly.

I think a good idea might be to do it for postfix/prefix notation, rather than infix. This will also get rid of the need for parentheses.

The ordering of numbers will be different between infix, prefix, and postfix representations.

Reminds me so much of competitive programming

What happens if you allow for 0?

For ascending solution taking a lazy approach, it appears to be a trivial inclusion, considering for any n with a solution using 1-9, a solution which includes 0 will simply take the form:

  n = 0 + <ascending_solution_n>

without any additional consideration. Similarly for descending solution:

  n = <descending_solution_n> + 0

The descending case also looks like it'll produce a crap ton of solutions for n = 1 of the form:

  1 = <arbitrary_descending_permutation> ^ 0

Multiplication makes a difference here