Cantor set IV
Those of youse who have been following this thread will be interested to hear that the digit analysis problem at the heart of the set membership challenge indeed has a partial (very, very partial) solution, much to my surprise. Three mathematicians recently discovered an algorithm:
{digit # in expansion of pi} --> algorithm --> {value of the said digit}
So you *don't* need to crank through digits 1-99 to find digit 100. The catch? the digits in question are binary. As far as anyone knows (I think) you still need to know decimal digits 1-99 before you can get to finding decimal digit 100.
{digit # in expansion of pi} --> algorithm --> {value of the said digit}
So you *don't* need to crank through digits 1-99 to find digit 100. The catch? the digits in question are binary. As far as anyone knows (I think) you still need to know decimal digits 1-99 before you can get to finding decimal digit 100.
OK, please don't mock me if this is really dumb--I've only thought about it for a good 12 seconds. But can't we make a mapping from a given digit in base-10 to a given digit in binary? I.e. it seems their algorithm should be able to work for non-binary representations.
ReplyDelete(Basically, I'm asking if you can intuitively explain why this is wrong, since otherwise they wouldn't have done it in binary I imagine...)
No, not dumb, but...
ReplyDeleteMapping from one octal digit to three binary digits is trivial; and mapping from one decimal digit to 3+ binary digits is likewise trivial, although it reqires a bit more thought to map a sequence of n decimal digits into (3+)n binary digits.
But the algorithm in question produces binary digits, so we are concerned with mapping the other wsy, from binary to decimal.
Now suppose you use the algorithm to find binary digits 1000-1100. Clearly, once you get squared away, you can go on converting each 3 or 4 binary digits to the next decimal digit. But how do you get squared away? Is the 1000th binary digit the beginning of a new decimal digit? If not, what is the contribution of the (unknown) binary digits just preceding? To answer these questions, it is necessary to calculate the binary, or the decimal, digits of pi from the gitgo so as to get the binary digit values through the 999th.
The reason they did it in binary, as I understand it, is that that is what the algorithm they found does; they have not discovered an algorithm that works in any other base, let alone all bases, and, to repeat what I said in the post, neither has anyone else, as far as I know.
Ah, OK, cool.
ReplyDelete