Hacker News Reader

Comment by martin-adams | Hacker News Reader

For the curious, the source code takes a somewhat obvious approach:

Yep, I think that is literally pi to 6 million decimal places then doing an indexof of the 6 digit year and 6 digit time of day.

View on HN

I wonder if the 6 million digits cover all possible 6 digit year and time combinations, I guess it wouldn't be hard to bruteforce check.

Edit:

I just noticed for the time digits, it seemed to be reporting something like -2 a few minutes ago.

'133343' doesn't seem to be part of the digits, which would represent 13:33:43. Unless I'm misunderstanding.

I wonder if it includes more digits than necessary :)

That's easy to check even with just ctrl+f: the last six digits are 422990 which occur 8 times throughout that string. Hence, we could remove at least the last digit without losing anything.

It also includes sequences that can never match such as "999". I wonder if overwriting those with a non-digit would allow indexOf to be infinitesimally faster?

It certainly does not, see this comment: https://news.ycombinator.com/item?id=13868201

You can remove some digits and get the same result as today (see https://news.ycombinator.com/item?id=13867324), but as it lack so many situations as it does I would not say so.

What are the odds that this worked? Or, how many digits should we expect to need? Naively, you'd need at least 1 million to get all 6 digit numbers in it. If Pi happened to be a De Bruijn sequence [1], then that would suffice. However, there are only (10!)^(10^5)/10^6 ~ 2e655970 such sequences, compared to 10^(10^6) total random sequences. I.e. the probability of getting a De Bruijn at random with a million characters is about 2e-344030. I'll round that up to "ain't gunna happen". So we probably need a lot more than the naive lower estimate... but where does it start getting likely?

Edit: Here's another estimate: with 6 million digits, we can get all 6 digit possibilities by just concatenating them all together. There's then (10^6)! ways to arrange the 6 digit strings before concatenating them. So if we picked a random 6 million digit sequence, there's (10^6)!/10^(6e6) ~ 10^(-10^5.6) chance of getting one of those. So the chance that a random 6 million digit string contains all subsequences is at least that high. But that's not saying very much!

This is related to the question: how many balls do I need to thrown randomly into N buckets so that the each bucket gets at least one ball (with high probability)? I was amused to learn recently that the answer must be more than linear in N. You might think that throwing a billion times N balls would suffice, but for very large N it won't. Even though you're throwing a billion times more balls than there are buckets! The probabalists I was talking to about this didn't know off-hand what the exact asymptotic of "enough balls" to throw was. That answer appears to depend upon the asymptotics of the second Stirling number based off this stack exchange [2]. But to complicate matters, the approximation given by the Wikipedia page [3] is precisely insufficient to answer the question! We'd need to know how it approaches that asymptotic.

[1] https://en.wikipedia.org/wiki/De_Bruijn_sequence [2] http://math.stackexchange.com/questions/174674/if-n-balls-ar... [3] https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second...

> Naively, you'd need at least 1 million [digits] to get all 6 digit numbers in it.

How naive do you do it? :)

When I just concatenate all possible 6-digit numbers (of which there are 1e6 = 1 million), I get 6 million digits total. You could of course overlap them partially to save space, but that does not count as "naive" anymore.

Your 6 million digits isn't a lower bound though: it's just demonstrating that 6 million digits can suffice, but there could be shorter ways to do it. In particular, none of your million 6 digit strings are overlapping. My estimate was the following. If you take a million digit string, then there are 1 million six digit substrings (actually you need 1 million and 5 digits * ). I.e. a 6 digit substring is specified by choosing where it starts, and there are 1 million places to do that. So if each of these were distinct, you'd get it. But any shorter string just doesn't have enough substrings in it to possibly get them all!

But it's not clear that it's possible to overlap all possible substrings in the right way: that's what De Bruijn sequences do but I don't consider them to be naively obvious at all.

* This is where I overlooked in my last post that De Bruijn sequences (which achieve this lower estimate) are actually for cyclic strings, allowing the subtrings to go past the end and back to the start of million digits. That allows 1 million digits to suffice. We'd actually need that 1000005 digits.

I wrote a quick script to test it. It does not take leap seconds into consideration and assumes all months to have 31 days (would be easy to modify, but it is sufficient for the task).

https://gist.github.com/zulln/110a1d454d07339c496cc8ec6349fe...

This means this does not work about 200 times a day in addition to about hundred whole days (for every hundred years).

A quick script from me determined you need 10,524,628 decimals of pi for this to work for all dates and times, with the limiting time being 16:25:42.

> A quick script from me determined you need 10,524,628 decimals of pi for this to work for all dates and times ... (emphasis added)

For a finite, normally distributed digit sequence (as Pi is thought to be), the probability is always less than 1.0 for finding a particular sequence within it. But if you mean a specially engineered sequence designed to include all possible 6-digit sequences, then we've left the question of whether a given finite Pi sequence includes it.

I am not sure what you are trying to say here. He did not care about probability, he tested it.

Nice! That's pretty neat zulln. If you'd like to improve things, I do accept pull requests https://github.com/TheDen/PiDay

> I wonder if the 6 million digits cover all possible 6 digit year and time combinations

Only an infinite sequence of normal digits can be assured (probability: 1.0) of matching a test digit sequence within it, even a trivial one. For all other normal digit sequences, there's a probability less than 1.0 for finding an example sequence within it.

> '133343' doesn't seem to be part of the digits, which would represent 13:33:43. Unless I'm misunderstanding.

Good example. One would think that a relatively short test sequence would be a shoo-in for being located somewhere within 100 million normal digits, but that's by no means assured.

Edit: the sequence '133343' appears 80 times in the first 100 million digits of Pi.

pi to the 10 millionth digit was not enough. I had to use the billionth (didn't try anything between those two). Mind you, the 10 millionth only had 3 times that didn't match.

I've uploaded[1] the reverse system, which is quite a bit more efficient. It's a 600KB JSON array with every second in a day and its corresponding offset in Pi.

https://gist.github.com/teotwaki/253422ac235960a0d672f9a1c39...

Edit:

- Pi to its 10 millionth digit: http://pi.karmona.com/ (warning, this will severely slow down or crash your browser)

- Pi to its billionth digit: https://stuff.mit.edu/afs/sipb/contrib/pi/

Great work slau. I do accept pull requests https://github.com/TheDen/PiDay if you do want to add improvements

Hey Denis,

Great to hear. I'll throw something together and send it your way.

Thanks!

Wow, not even an efficient data structure, just an almighty string! On one hand, that's pretty disgusting. On another, it's an impressive demonstration of just how fast everything is nowadays; I wonder if the javascript interpreter in my browser does any kind of optimisation on that string in order to perform such gargantuan indexOfs.

I think a 6MB string is preferable to calculating pi to 6+ million digits in JS on each load.

I certainly wasn't suggesting that! Surely there's a superior data structure than a string, though.

https://en.wikipedia.org/wiki/Suffix_tree

Warning: Viewing the js may cause your mobile viewing experience to crash!

Reply on news.ycombinator.com