# Ask Uncle Colin: 10,958

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