7 ms·
What is the longest known sequence that repeats in Pi? (homelab)
- mihaic 2y agoThis can easily be optimized to use less memory, since pi is thankfully random. Do N passes over the data, and at each pass only put in your hashmap the values that mod N equal the current iteration. If you take N~100, the runtime would probably be in the same ballpark, since the only thing that increase is streaming all the data N times. With a fast SSD, that's not that much.
- tfehring 2y agoIsn't this functionally the same thing that the author already did, just with N=10 and filtering on the first digit instead of the last?
- mihaic 2y agoSure, I did read it too quickly, but why didn't he simply extend the generalized implementation instead of saying at the end that he was limited by the amount of RAM he has? Those runtimes seem quite a lot slower than what I would have expected, and I'm pretty sure they could be optimized by a lot, especially since he sounds like he has enough RAM to hold the entire file. Not trying to be dismissive, but this doesn't sound like that great of an implementation.
- sponaugle 2y agoIndeed no worries about pointing that out! - there are lots of things that could optimize the RAM requirements, and especially reduce the runtime. Since the overall runtime is pretty quick to getting a single answer (3 hours) vs spending more time optimizing.. but absolutely there is a lot left on the table. I think with some good optimization you could reduce the runtime significantly, especially on modern hardware. As for RAM limitations - You are correct the only limitation is just that with the RAM I have I would need to do more iterations. It would be possible to do this in much less RAM with more iterations, or the reverse of course. I was fond of solving the problem in RAM just as a way to limit the scope of the problem... but SSDs are indeed pretty fast at streaming data like this.
- ForOldHack 2y agoHow odd. You have to read and copy the data from the web to your hard disk, to the SSD. Why not just run the program on the web copy, streaming. Tiny amount of ram for all the hash tables, and you do not need to move the data around. Multi threading would improve the runtime, but reading the table is the bottle neck. He makes a great optimization, by using hash tables, but I was wondering about optimizing about the evaluation of the Chi-Square Test for Equal Proportions. If the Chi-Square test diverges from the Chi-Square Test for e, then there is little likely hood for pi+e to ever converge on rationality. My hypothesis is that because Pi is cyclical, and e is exponentially transcendental, that their sum and product are not rational, and nether are their respective powers ( Pi^e and e^Pi ), but those will take a much larger homelab than I have access to.
- sponaugle 2y agoI have a local copy of 10 trillion digits of Pi on the math cluster, so no web access needed.
- altruios 2y agoPedantic point here. PI isn't random. It is exactly the ratio of a radius and the circumference of the circle. Incommutability is not the same thing as 'random'. PI does not follow any sort of probability or statistical algorithm to be generated. Nothing inside PI is random... Now... if you take a random number (introducing randomness in the first place) representing the position and another random number to represent the length. From PI those two random numbers will generated a random sequence. But the 'randomness' is not IN PI, the random elements are only in the 2 chosen numbers. I understand this is colloquially what people mean when they say PI is 'random'... Randomness can only come about from choice, and the digits of PI have no choice as to what they will be. You can not read out a deterministic sequence of numbers in order and expect randomness. The randomness must come from some choice interacting with that defined sequence of numbers.
- flir 2y agoNot taking issue with you, slightly different question: Do the digits of Pi pass statistical tests for randomness? Uniform distribution, etc?
- p4bl0 2y agoThis reminds me of Chaitin's work on the nature of randomness and his halting probability constant: https://en.wikipedia.org/wiki/Chaitin's_constant https://en.wikipedia.org/wiki/Chaitin's_constant
- nobrains 2y agoOK cool. But... Finding random numbers repeating is a simple brute force problem. It is cool, but slightly boring. Related to this, what I cannot wrap my head across, is the Infinite monkey theorem. Is it not possible that we keep expanding the numbers and never reach a complex enough set of values?
- clueless 2y agoin a pure infinite monkey scenario, works of Shakespeare would be generated at some point
- ryanmcbride 2y agoYou can't guarantee that monkeys are typing perfectly randomly. We may never see better than "it was the best of times it was the blurst of times"
- scarmig 2y agoIt doesn't need to be perfectly random; you just need every sequence to have a nonzero probability of being generated. "to be or not to be" may be more likely for a monkey on a keyboard to generate than a random string, actually. The keys to generate it are highly repetitive and relatively close together. That's true for any NL string: the lower entropy of NL strings are reflected in the keyboard layout. If the monkeys switch to Dvorak, they could probably generate Shakespeare even faster.
- tacoooooooo 2y agoyou misunderstand infinity
- clueless 2y agohow so?
- chowells 2y agoSo if I randomly type letters from the top row of my keyboard forever, I'll eventually type the entire works of Shakespeare? Of course not. There are lots of ways you can bias random that remain random, but prevent every possible output from being generated. That's all GP was saying. You can't just say "infinite time", you need to rule out biases that would prevent the desired result.
- Beijinger 2y agoPi is normal https://www.unige.ch/~mccoid/presentations/TALK_piday_2019_pi.pdf https://www.unige.ch/~mccoid/presentations/TALK_piday_2019_p...
- danbruc 2y agoConjectured to be normal.
- sponaugle 2y agoYep - This really is just a random number problem.. it is only interesting in the sense that Pi is something that has been captivating in public math perception. Any random number would have the same characteristics.. It is however something fun to do in a homelab outside of the normal learning and playing around, and that has merit for me. Hobbies are hobbies in part because of the interest, joy and appreciation they drive.
- Spivak 2y agoIn one sense you're right. The set of normal numbers has measure 1 so if you choose a real number randomly it will be normal and have the same properties. In another sense you're very wrong. The set of uncomputable numbers also has measure 1. So while there are lots of normal numbers Pi belongs to a pretty exclusive club of numbers we can actually look at. It's not a particularly deep result but the fact that the set of computable numbers is countable will never not make me existential. Every number that we can actually express, that we will ever know, is no bigger than the whole numbers.
- drexlspivey 2y agoHow do you generate a random irrational number?
- chowells 2y agoGenerate a random Cauchy sequence. One trivial way to do this is to output a random string of digits. It's not perfect, but it works. Approximately 0% of random Cauchy sequences will be computable, so long as your random number generator doesn't have self-correlations.
- kstrauser 2y agoI wonder if you could do something with Bloom filters similar to: filters = {} candidates = [] for i in range(len(pi)): block = pi[i:i+10] hash_prefix = block[:4] try: bloom = filters[hash_prefix] except KeyError: filters[hash_prefix] = BloomFilter().add(block) candidates.append((i, block)) continue if block in bloom: candidates.append((i, block)) else: bloom.add(block) Basically, make one pass through to build a list of statistically likely candidates to evaluate later. Then use full string matching on those candidates to find the real matching sequences. That might be helpful here because Bloom filters can say "we might have seen this string before" or "we definitely have not seen it before". That may greatly reduce the amount of storage you need.
- sponaugle 2y agoOh that is interesting!.. and indeed I did consider doing a 'hash compression' where I would generate offsets to numbers that might be similar, then do direct comparison on those ones that are similar. I'll take a crack at doing this - It could certainly be an improvement and would just be fun to try out.
- kstrauser 2y agoPlease let us know!
- ted_dunning 2y agoExactly this. Use a Bloom filter to find candidate solutions, write those out and review them later. Since you can write the entire candidate and its location, the review consists of a simple sort. Digging in to estimate the speed, if your Bloom filter has a 0.1% chance of a collision then a trillion digits of pi will result in a billion candidates. This requires ~15 bits per entry or about 2TB of memory for the full Bloom filter. Using multiple passes on subsets of the data allows you to trade speed for space. Note also that a 128 bit integer has room for 38 digits. This means that you can do all of the shifting using modulo, multiplication and addition operations. I would be very surprised if the cost of the disk I/O to read the raw digits is as fast as the sieving of candidates. As such, the speed of a single pass should be about the cost of reading about 500GB of data which means that multi-threading will be of limited use. This should be less than an hour on most machines. That means that one of my ancient Intel NUCs with 32GB should be able to scan the entire range in about a day no matter what size sequence we are looking for.
- 34679 2y agoAssuming that pi has an infinite number of digits, then the answer to "What is the longest known sequence that repeats in Pi?" is "The longest known sequence of Pi".
- sponaugle 2y agoHa! Yea, that is true.. now if we only had a printout of it!
- Misdicorl 2y agoThis isn't true as you can build an infinite sequence that never repeats. An example sequence in binary is (the number of 0s between each 1 increases by 1 every time) 01001000100001...
- poizan42 2y agoExactly. A number with the property that every sequence occurs is called a rich or disjunctive number - a number can be rich in s specific bases or rich for all bases we don't know whether pi is any if that. A number where every sequence occurs equally often (scaled to the length of the sequence) is called a normal number, which is an even stronger property.
- sponaugle 2y agoWhile Pi is not proven to be a disjunctive number, nor the stronger condition of being normal, it is generally believed to be normal. That being said we don't have a proof of Pi being normal, nor disjunctive. I am not familiar with how a proof of that would be constructed, as clearly numerical or computational measurements could never be conclusive.
- 0points 2y agoOn a side note (it's mentioned in the article), it has been a while since I last visited OEIS (Online Encyclopedia of Integer Sequences), which has been of use over the years. Very much appreciate the amazing effort that is OEIS! I thought I should mention it to raise awareness: https://oeis.org/ https://oeis.org/ The sequence in the article: https://oeis.org/A197123 https://oeis.org/A197123
- sponaugle 2y agoOEIS is amazing to say the least. It is such an interest collection of sequences as well as a great collection of editors that are willing to keep it all in order! Certainly worth a mention and a contribution.
- zimpenfish 2y agoThere's a Neil Sloane (OEIS creator/curator) playlist from Numberphile which, unsurprisingly, often feature OEIS sequences. https://www.youtube.com/playlist?list=PLt5AfwLFPxWJXQqPe_llzWmTHMPb9QvV2 https://www.youtube.com/playlist?list=PLt5AfwLFPxWJXQqPe_llz...
- TacticalCoder 2y agoOEIS is amazing and in the same "spirit" I also love factordb. Another "Web 1.0" look which also exists since immemorial times. It contains, well, factorization of many numbers. For example here's RSA-250: https://factordb.com/index.php?query=2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937 https://factordb.com/index.php?query=21403246502407449612644... I hope sites like these continue to exists for a very long time. I'd link to one or two other useful oldschool sites that I do still use but I'm not sure they could handle the /. (well, HN) effect.
- cheeze 2y agoCan you do something fancy with FFTs and convolution here? I _think_ you can but my brain doesn't have the bandwidth to think past that.
- amelius 2y agoThe binary representation of Pi contains both the MIT license and the GPL. I'm confused.
- ZiiS 2y agoIsn't the entire known sequence of pi also known to repeat due to its nature?
- IngoBlechschmid 2y agoYou mean because the entire known sequence is finite, and every finite sequence occurs in pi infinitely often? This is suspected but currently not yet proven. In fact, we don't even have a proof yet that the digit 7 occurs infinitely often in pi. (Same for any other digit.) Right now it's conceivable, but very unlikely, that there is some final 7 in pi.
- deleted 2y ago[deleted]
- drpixie 2y agoI suspect not. Pi is known to be irrational, and repeating sequences are known to be rational. So pi cannot be truely repeating.
- cperciva 2y agoThe right algorithm for this problem starts with a linear time suffix sort.
- qingcharles 2y agoThis one is fun too: https://en.wikipedia.org/wiki/Six_nines_in_pi https://en.wikipedia.org/wiki/Six_nines_in_pi
- amingilani 2y agoIs there a research paper is this? Seriously, I find the most interesting works self-published in people’s personal blogs and I often wonder if there’s a paper in there and why it didn’t make it into a paper. Maybe there’s a paper in finding the largest repeating sequence in Pi. There have certainly been more niche papers than that.
- marginalia_nu 2y agoThere isn't much incentive to publish academic papers outside of academia. It's a huge hassle and the juice generally isn't worth the squeeze.
- lifthrasiir 2y agoExtending that to all known digits would be a fun technical challenge. I once wrote a code to calculate positions where k subsequent decimal digits equal to the position index itself [1], but I had no storage to spare so I instead used a stream of digits from the public GCP dataset [2]. You would eventually want to try this approach if you are like me (i.e. don't want to pay for two-digit-TB storage). [1] https://github.com/lifthrasiir/remote-pi-reader/ https://github.com/lifthrasiir/remote-pi-reader/ [2] https://storage.googleapis.com/pi100t/index.html https://storage.googleapis.com/pi100t/index.html (used to be `pi50t` back then)
- sponaugle 2y agoNice... I did that same problem as it was a numberphile episode. Very cool! Fortunately I have over a PB of local storage at home which helps out.
- csense 2y agoBreaking news: As of this writing, OP is 23 hours old. OEIS has already been updated with the new terms OP discovered.