There are 9592 prime numbers less than 100,000. Assuming the test suite only tests numbers 1-99999, the accuracy should actually be only 90.408%, not 95.121%
The density of primes can be approximated using the Prime Number Theorem: 1/ln(x).
Solving 99.9995 = 100 - 100 / ln(x) for x gives e^200000 or 7.88 × 10^86858. In other words, the universe will end before any current computer could check that many numbers.
I found a list of prime numbers, which states that the 50,000,000th prime number is 982,451,653, which means 5.08930896% of the numbers up to 982,451,653 are prime. That’s unfortunate, as it means the accuracy is actually lower than the original post we go further - down from 95.121% accuracy to 94.921%. Bummer!
Out of curiosity, I then whipped up a quick program in rust that starts from those numbers, crunching forward through the primes while prime_count asf32 / total_count asf32 > 0.05, using 16 CPU cores to divide-and-conquer and check whether a number is prime. There’s probably a better way to do that, but meh. Such a check will essentially only get me back above 95% though, and based on the rate of change, I suspect it would take an exponentially higher amount of time than whatever it takes to get to 99.5%.
In the time it’s taken me to write this, it’s calculated just over 330,000 more primes, reaching ~0.050874 hit rate for primes.
This has led me down a small rabbit hole, in which it turns out there are plenty of folks who have approached the topic of “what percentage of numbers are prime?” - and the answer is essentially “it will eventually round to 0%”. Because of you, I remain curious to know when that crosses the threshold of 99.5% though - and I’ll at least leave it running for the next day or two to see how close it gets.
Unfortunately though, at the rate my PC can calculate, I don’t think I’m personally gonna be hitting an answer to this any time soon. If I ever do manage to figure it out, I’ll be sure to update… because hell, why not.
I’ve also considered trying to find bigger lists of primes, but meh. I’ve already spent an hour on this that I intended to spend playing D&D so … meh. =]
We got nerd sniped at almost the exact same time, but approached this in very different ways. I applaud your practical approach, but based on what I calculated, you should stop now. It will never reach 99.999%
99.5% would still be e^200 numbers checked (7x10^86). According to the Quora link in my other comment, we’ve only calculated primes in sequence up to 4x10^18 as of 7 years ago. 95% is very doable though.
Edited to correct first N primes vs primes up to N.
How long would this have to run for it to round up to 100%?
A few calculations:
1/ln(x). Solving99.9995 = 100 - 100 / ln(x)for x givese^200000or7.88 × 10^86858. In other words, the universe will end before any current computer could check that many numbers.they did the math!
This is a really fun question and now I’m nerd sniped
As an update to my earlier nerd-sniped-ness:
I found a list of prime numbers, which states that the 50,000,000th prime number is 982,451,653, which means 5.08930896% of the numbers up to 982,451,653 are prime. That’s unfortunate, as it means the accuracy is actually lower than the original post we go further - down from 95.121% accuracy to 94.921%. Bummer!
Out of curiosity, I then whipped up a quick program in
rustthat starts from those numbers, crunching forward through the primeswhile prime_count as f32 / total_count as f32 > 0.05, using 16 CPU cores to divide-and-conquer and check whether a number is prime. There’s probably a better way to do that, but meh. Such a check will essentially only get me back above 95% though, and based on the rate of change, I suspect it would take an exponentially higher amount of time than whatever it takes to get to 99.5%.In the time it’s taken me to write this, it’s calculated just over 330,000 more primes, reaching ~0.050874 hit rate for primes.
This has led me down a small rabbit hole, in which it turns out there are plenty of folks who have approached the topic of “what percentage of numbers are prime?” - and the answer is essentially “it will eventually round to 0%”. Because of you, I remain curious to know when that crosses the threshold of 99.5% though - and I’ll at least leave it running for the next day or two to see how close it gets.
Unfortunately though, at the rate my PC can calculate, I don’t think I’m personally gonna be hitting an answer to this any time soon. If I ever do manage to figure it out, I’ll be sure to update… because hell, why not.
I’ve also considered trying to find bigger lists of primes, but meh. I’ve already spent an hour on this that I intended to spend playing D&D so … meh. =]
We got nerd sniped at almost the exact same time, but approached this in very different ways. I applaud your practical approach, but based on what I calculated, you should stop now. It will never reach 99.999%
Whew. I’m only going for 99.5%, which according to your other comment is doable!.. But impractical
99.5% would still be
e^200numbers checked (7x10^86). According to the Quora link in my other comment, we’ve only calculated primes in sequence up to4x10^18as of 7 years ago. 95% is very doable though.Edited to correct first N primes vs primes up to N.
Incredible amounts of numbers. Crazy.