Dear Uncle Colin,

There is a famous puzzle where you’re asked to form 100 by inserting basic mathematical operations at strategic points in the string of digits 123456789. This can be achieved, for example, by writing $1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100$.

Brazilian Mathematician Inder J Taneja has found a way to represent every natural number from 0 to 11111 using the string of increasing digits 123456789 and decreasing digits 987654321 with basic maths symbols (brackets, powers, multiplication, division, addition, subtraction) inserted - except for one: while 10,958 can be written in the decreasing case, no-one’s come up with a way of expressing 10,958 in the increasing case!

I’d like to know a ballpark figure for the number of permutations are involved keeping the numbers 123456789 in a fixed position but allowing +, -, ×, ÷, brackets, concatenations, powers etc. Any ideas how you’d go about finding that?

-- Colin, Also Labelled “Chris’ Uncle”, Loves A Tough Integral Or Number Stooshie Including Zany Enigmas

Dear CALCULATIONSIZE ((Good work!)), and thanks for your message!

I don’t know for sure how many possible calculations there are, but I can put an upper bound on it.

Given an ordered list of $n$ numbers, and a set of $k$ operations you can plausibly perform on any adjacent pair, you have $(n-1)k$ plausible resulting lists from a single operation - in each of the $(n-1)$ gaps, any one of the $k$ operations could go, leaving you with a list of $n-1$ numbers.

On that list, there are $(n-2)k$ possible subsequent lists, and so on. Multiplying all of these together gives $(n-1)! k^{n-1}$ plausible routes through the calculation. In this case, that would be $8! \times 6^8 \approx 67.7$ billion routes. (By contrast, for a Countdown solver I wrote many years ago, there are around three million routes.)

Why it’s an upper bound

This is only an upper bound on the number of needed calculations, though, for two reasons: most obviously, it’s not always possible to perform an operation - for example, $(4 \div (56 - 7\times 8))$ doesn’t work - and I don’t think the rules would allow concatenating, say, 1 onto a 5 derived from 2+3.

Secondly, it is possible to get repeated lists – for example, doing 1+2 then adding 3 to the result has the same effect as doing 2+3 then adding 1. In practice, I wouldn’t expect huge reductions from either of these, and “several tens of billions” is a fair ballpark estimate.

As for 10,958… I leave that as an exercise for the reader!

Hope that helps,

-- Uncle Colin