The abstract and introduction don't explain this very well.<p>My understanding is that the author wrote the digits 1 through 9 in ascending order, and then inserted parenthesis, addition, subtraction, multiplication, division and exponentiation operators between them where appropriate to get every number from 0 to 11111.<p>And then he did the same thing using the digits 9 through 1 in descending order and did the same thing.<p>He was able to find a solution for every number except 10958 with 1-9 in ascending order.<p>EDIT:<p>The paper also doesn't explain much about how or why they did this. At first glance I don't think it would be too difficult to come up with a branch and bound algorithm to search through all the solutions.
At my office we lost a lot of time because someone put up a challenge to represent all the numbers 0-99 with algebriac expressions containing exactly four digits '4'. The use of powers and radicals was allowed.<p>I myself solved several numbers before exhausting the tricks I could think of, and reverted to brute force/search with Polish/prefix notation, then realizing how massive the search space was for even just a few operators. Adding parentheses ordering further explodes the search space.<p>Finally, while this kind of concrete and explicit expression is "toy math", it is related to Godel Sentences and lexigraphic ordering of proofs used through much of the establishment of logic, the foundations of proof systems, and computer science.
It wasn't clear why this was interesting from the title. But here's an example:<p><pre><code> 0 = 12 + 34 − 56 − 7 + 8 + 9.
1 = 1^23456789.
2 = 123+4−56−78+9.
3 = 123 − 45 − 6 − 78 + 9.
</code></pre>
And then in decreasing order<p><pre><code> 0 = 98−7−6−54−32+1.
1 = 98−76−54+32+1.
2 = 9+87−65+4−32−1.
3 = 98−76−5+4+3−21.
</code></pre>
That this is possible at all is counter-intuitive to me, and hence fascinating. Even more fascinating is that he does not have a solution for 10958 in the ascending case.
I just wrote a script to do this in, like, 5 minutes :) And the whole thing runs in 7 seconds on my machine.<p><a href="https://github.com/adtac/123456789/blob/master/output" rel="nofollow">https://github.com/adtac/123456789/blob/master/output</a><p>Admittedly, it doesn't have every number. I suspect it's because I haven't included bracketed expressions.
Would be more interested in the script than the list and how long it took to run.<p>And if this is the best so far? Seems surprising given it's a popular kids game.<p>It's not really maths IMO since I think using 98 is cheating for instance, it's really (9 X 10 + 8), 10 not being allowed. So kids are not learning real maths, more arithmetic.
Maybe something neat to bring up as a "drinking game"...at my next Math Symposium<p>Pick at random 3 digit number and try to express using the digits 1 thru 9...loser has to drink
Seems related to this recent Numberphile video which does a similar thing for e and pi:<p><a href="https://www.youtube.com/watch?v=xgBGibfLD-U" rel="nofollow">https://www.youtube.com/watch?v=xgBGibfLD-U</a>