The abstract and introduction don't explain this very well.
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.
And then he did the same thing using the digits 9 through 1 in descending order and did the same thing.
He was able to find a solution for every number except 10958 with 1-9 in ascending order.
EDIT:
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.
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.
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.
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 didn't read the article... but why 1 to 9? Is it because we have 10 fingers and 10 symbols that represent numbers? We're this numbers chosen for another reason?
Is that actually why base 10 became the norm? I've never really learned why exactly decimal was chosen, and I'd be interested in learning about what historical evidence there is for its origin.
Right, but that doesn't really say anything about causation; there is definitely a linguistic link between the body parts and numerical digits in this word, but that could have easily developed after base ten became common for other reasons.
It's often claimed, but I'm not aware of any strong evidence for it.
In particular, since our hands can show "10" the natural base this would imply is base _11_ and not 10.
Another argument I've heard presented is that since 10 is divisible by 2 and 5 this simplifies many common calculations. There were groups in the past advocating use of other bases (in particular 12 but also 16).
The mayan's number system is base 20 (though the digits are are drawn out of sub digits in base-5).
> The mayan's number system is base 20 (though the digits are are drawn out of sub digits in base-5).
I think I remember learning in school that one of the ancient Mesopotamian civilizations (Sumerian, I think, but I could be wrong) used 60 as the basis for their system because it was divisible by 1, 2, 3, 4, 5, and 6.
11? How so? If I have 10 fingers I can count from 1 to 10. When I start again I count from 11 to 20. Again from 21 to 30. In base 11 it would go 1 to A, 10 to 19, 1A to 28, etc. It doesn't make sense.
> Another argument I've heard presented is that since 10 is divisible by 2 and 5 this simplifies many common calculations.
To me, it always seemed like 5 was only a common number because of its place in base 10, not the other way around. There doesn't seem to be any reason that 2 and 5 would have been chosen as more significant than 2 and 3 or 2 and 7.
There's not a lot interesting about "facts about numbers" when you place such a low upper bound on your achievements. If he'd only done this up to 100, he'd never have had trouble finding a solution for 10958. But why 11111? Why not 111111111111?
To me this is just as interesting as any other arbitrary list of permutations of symbols.
Intuitively, this problem seems isomorphic to the famous NP-complete problem, 3SAT[1]. Instead of picking binary states, you have to pick symbols to insert, and where, that yield the desired outcome. If this intuition is true, then if you can write a program to generate these expressions (in polynomial time) then you'd have also proven P=NP. You could probably brute force it though as the difficulty scales with the length of your target number.
A lot of math results are curiosities at first but turn out to be important in unexpected ways.
The original proof of the existence of irrational numbers depends on using the Pythagorean theorem to show that the leg of an isosceles right triangle is simultaneously odd and even if irrational numbers do not exist. The proof works because somebody had thought out the seemingly trivial notions of what it means for a number to be odd and even and the effect this has on their squares and ratios. [1] I have always had this picture of somebody's spouse in 500 BC yelling at him to get in and do some useful work instead of standing around in the square drawing numbers.
Would be more interested in the script than the list and how long it took to run.
And if this is the best so far? Seems surprising given it's a popular kids game.
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.
I think there was at least one script for some of the numbers, this I would have thought the most interesting, optimisation of the script and for all numbers and proving some numbers have no solutions([edit] possibly very hard) -
"The author is thankful to xxxx in finding some difficult representations using computerized script."
"some". In previous versions of the paper, he claims to have done everything manually: "To bring these numbers, thousands of combinations are considered without use of any programming language."
Huh, he does 98 as 98=1×23+45+6+7+8+9.
Or do you mean that 23 and 45 are cheating, because they are two digit numbers? I think they rules are quite well explained and followed.
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:
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.
60 comments
[ 2.9 ms ] story [ 82.8 ms ] threadEdit: the revisions have different ranges of numbers, but they go up and down. Odd.
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.
And then he did the same thing using the digits 9 through 1 in descending order and did the same thing.
He was able to find a solution for every number except 10958 with 1-9 in ascending order.
EDIT:
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.
You can create a second version by replacing this with 1×2×3.
For example,
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.
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.
Pick at random 3 digit number and try to express using the digits 1 thru 9...loser has to drink
In particular, since our hands can show "10" the natural base this would imply is base _11_ and not 10.
Another argument I've heard presented is that since 10 is divisible by 2 and 5 this simplifies many common calculations. There were groups in the past advocating use of other bases (in particular 12 but also 16).
The mayan's number system is base 20 (though the digits are are drawn out of sub digits in base-5).
I'd disagree. Having base 10 allows us to easily imagine 60 as 6 people worth of fingers.
I think I remember learning in school that one of the ancient Mesopotamian civilizations (Sumerian, I think, but I could be wrong) used 60 as the basis for their system because it was divisible by 1, 2, 3, 4, 5, and 6.
To me, it always seemed like 5 was only a common number because of its place in base 10, not the other way around. There doesn't seem to be any reason that 2 and 5 would have been chosen as more significant than 2 and 3 or 2 and 7.
To me this is just as interesting as any other arbitrary list of permutations of symbols.
1. https://en.wikipedia.org/wiki/Boolean_satisfiability_problem
I think this was mostly just for fun/curiosity, but operation combinations are interesting -- if nothing else to show how easy numerology can be.
It's not like the author attached significance to any of the calculations.
Here is a result (we can call it Taneja's Conjecture):
The digits 1-9 in sequence can not be combined with fundamental operations (+ - / * ^) in a way that computes the value 10958.
The original proof of the existence of irrational numbers depends on using the Pythagorean theorem to show that the leg of an isosceles right triangle is simultaneously odd and even if irrational numbers do not exist. The proof works because somebody had thought out the seemingly trivial notions of what it means for a number to be odd and even and the effect this has on their squares and ratios. [1] I have always had this picture of somebody's spouse in 500 BC yelling at him to get in and do some useful work instead of standing around in the square drawing numbers.
[1] https://en.wikipedia.org/wiki/Irrational_number#Ancient_Gree...
And if this is the best so far? Seems surprising given it's a popular kids game.
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.
I think there was at least one script for some of the numbers, this I would have thought the most interesting, optimisation of the script and for all numbers and proving some numbers have no solutions([edit] possibly very hard) -
"The author is thankful to xxxx in finding some difficult representations using computerized script."
https://github.com/adtac/123456789/blob/master/output
Admittedly, it doesn't have every number. I suspect it's because I haven't included bracketed expressions.
Did a little fishing for overflow candidates with the following regex:
...caught 58 results between 266 and 10940: 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."^" 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.
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
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.
https://www.youtube.com/watch?v=xgBGibfLD-U
I would say that you need only one 2 if you replace log_2 by lg, so we should make lg taught in high schools... wink