Re:Finding Waldo in π
by mcbuilder on Friday April 01, 2022 @01:49AM
(#30875517)
Dumb question, but is any arbitrary string of digits with length N, somewhere in pi?
[ Parent
| on HN ]
Re:Finding Waldo in π
by mcpherrinm on Friday April 01, 2022 @01:58AM
(#30875554)
Not exactly the same thing, but related: I think everyone believes Pi is a Normal Number, but it isn’t proven. https://en.m.wikipedia.org/wiki/Normal_number
I think if we could prove Pi is normal, we could probably also prove your statement to be true (but I’m not sure about that)
Normal is actually a stronger claim than "contains any finite string as a substring". That normal numbers contain any finite string as a substring is a straightforward consequence of the infinite monkey theorem: https://en.wikipedia.org/wiki/Infinite_monkey_theorem
To see that the converse does not always hold, you could take something like the Champernowne constant https://en.m.wikipedia.org/wiki/Champernowne_constant and pad it with 9s between each integer, ie
.192939495969798999109911991299...
so that you still contain every finite substring, but you have a >50% chance of a randomly selected digit being 9.
I think there is a subtlety here that makes this fail. Normal does not imply that any finite substring exists, just that the probability of such a string existing is uniformly distributed within the space of possible values. There isn't any guarantee that you will actually see such a string, though you almost surely will.
Re:Finding Waldo in π
by 6gvONxR4sf7o on Friday April 01, 2022 @02:23AM
(#30875668)
At the very least, it doesn’t follow from the fact that it’s infinite and nonrepeating.
Re:Finding Waldo in π
by phantomherman on Friday April 01, 2022 @09:27AM
(#30877846)
I'm struggling to wrap my head around this: why doesn't it follow from that fact?
You can have infinite and nonrepeating sequences which don't contain every possible subsequence. For instance, 1010010001000... (where there is one more zero each time) never repeats itself, but it never even has the digit 2 in it.
Re:Finding Waldo in π
by phantomherman on Friday April 01, 2022 @12:14PM
(#30879803)
Aha, makes sense, thank you!
Not dumb at all, an area of open research actually. The answer is that this is not known and you will be math-famous if you figure it out.