7 ms·

For the curious, the source code takes a somewhat obvious approach: http://euler.party/pi.js http://euler.party/pi.js Yep, I think that is literally pi to 6 m

For the curious, the source code takes a somewhat obvious approach: http://euler.party/pi.js http://euler.party/pi.js 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.

anfractuosity 10y ago
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.
- ilogik 10y ago
  I wonder if it includes more digits than necessary :)
  - tgb 10y ago
    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.
    - oneeyedpigeon 10y ago
      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?
  - zulln 10y ago
    It certainly does not, see this comment: https://news.ycombinator.com/item?id=13868201 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 https://news.ycombinator.com/item?id=13867324), but as it lack so many situations as it does I would not say so.
- tgb 10y ago
  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 https://en.wikipedia.org/wiki/De_Bruijn_sequence [2] http://math.stackexchange.com/questions/174674/if-n-balls-are-thrown-into-k-bins-what-is-the-probability-that-every-bin-gets-a http://math.stackexchange.com/questions/174674/if-n-balls-ar... [3] https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#Asymptotic_approximation https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second...
  - majewsky 10y ago
    > 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.
- zulln 10y ago
  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/110a1d454d07339c496cc8ec6349fe8b 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).
  - mbb70 10y ago
    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.
    - lutusp 10y ago
      > 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.
      - zulln 10y ago
        I am not sure what you are trying to say here. He did not care about probability, he tested it.
  - theden 10y ago
    Nice! That's pretty neat zulln. If you'd like to improve things, I do accept pull requests https://github.com/TheDen/PiDay https://github.com/TheDen/PiDay
- lutusp 10y ago
  > 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.
- slau 10y ago
  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/253422ac235960a0d672f9a1c3907063 https://gist.github.com/teotwaki/253422ac235960a0d672f9a1c39... Edit: - Pi to its 10 millionth digit: http://pi.karmona.com/ 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/ https://stuff.mit.edu/afs/sipb/contrib/pi/
  - theden 10y ago
    Great work slau. I do accept pull requests https://github.com/TheDen/PiDay https://github.com/TheDen/PiDay if you do want to add improvements
    - slau 10y ago
      Hey Denis, Great to hear. I'll throw something together and send it your way. Thanks!
haburka 10y ago
Warning: Viewing the js may cause your mobile viewing experience to crash!
oneeyedpigeon 10y ago
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.
- theandrewbailey 10y ago
  I think a 6MB string is preferable to calculating pi to 6+ million digits in JS on each load.
  - oneeyedpigeon 10y ago
    I certainly wasn't suggesting that! Surely there's a superior data structure than a string, though.
    - Xophmeister 10y ago
      https://en.wikipedia.org/wiki/Suffix_tree https://en.wikipedia.org/wiki/Suffix_tree

anfractuosity 10y ago

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.

ilogik 10y ago
I wonder if it includes more digits than necessary :)
- tgb 10y ago
  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.
  - oneeyedpigeon 10y ago
    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?
- zulln 10y ago
  It certainly does not, see this comment: https://news.ycombinator.com/item?id=13868201 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 https://news.ycombinator.com/item?id=13867324), but as it lack so many situations as it does I would not say so.
tgb 10y ago
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 https://en.wikipedia.org/wiki/De_Bruijn_sequence [2] http://math.stackexchange.com/questions/174674/if-n-balls-are-thrown-into-k-bins-what-is-the-probability-that-every-bin-gets-a http://math.stackexchange.com/questions/174674/if-n-balls-ar... [3] https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#Asymptotic_approximation https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second...
- majewsky 10y ago
  > 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.
zulln 10y ago
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/110a1d454d07339c496cc8ec6349fe8b 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).
- mbb70 10y ago
  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.
  - lutusp 10y ago
    > 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.
    - zulln 10y ago
      I am not sure what you are trying to say here. He did not care about probability, he tested it.
- theden 10y ago
  Nice! That's pretty neat zulln. If you'd like to improve things, I do accept pull requests https://github.com/TheDen/PiDay https://github.com/TheDen/PiDay
lutusp 10y ago
> 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.
slau 10y ago
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/253422ac235960a0d672f9a1c3907063 https://gist.github.com/teotwaki/253422ac235960a0d672f9a1c39... Edit: - Pi to its 10 millionth digit: http://pi.karmona.com/ 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/ https://stuff.mit.edu/afs/sipb/contrib/pi/
- theden 10y ago
  Great work slau. I do accept pull requests https://github.com/TheDen/PiDay https://github.com/TheDen/PiDay if you do want to add improvements
  - slau 10y ago
    Hey Denis, Great to hear. I'll throw something together and send it your way. Thanks!

haburka 10y ago

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

oneeyedpigeon 10y ago

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.

theandrewbailey 10y ago
I think a 6MB string is preferable to calculating pi to 6+ million digits in JS on each load.
- oneeyedpigeon 10y ago
  I certainly wasn't suggesting that! Surely there's a superior data structure than a string, though.
  - Xophmeister 10y ago
    https://en.wikipedia.org/wiki/Suffix_tree https://en.wikipedia.org/wiki/Suffix_tree