Re:Dreaming of prime numbers in short intervals
by xyzzyz on Thursday July 20, 2017 @03:29PM
(#14815566)
Why log_2? It should be natural logarithm.
Re:Dreaming of prime numbers in short intervals
by wickawic on Tuesday July 25, 2017 @12:11PM
(#14848894)
You're totally right, I was stuck in CS world and write log_2 instead of ln absent mindedly
Re:Dreaming of prime numbers in short intervals
by bonzini on Thursday July 20, 2017 @05:34PM
(#14816487)
It only differs by a constant factor, so in the end it doesn't matter when you want the asymptotic complexity of storing all primes up to x.
Re:Dreaming of prime numbers in short intervals
by xyzzyz on Thursday July 20, 2017 @07:38PM
(#14817090)
Sure, you would still get that the space needed grows linearly, but you're off by almost 50% in your storage requirements. More importantly, you're confusing people with explicitly wrong statement for no benefit, people who might not realize that it's actualy ln, not log_2, and spread the mistake to other people.
Re:Dreaming of prime numbers in short intervals
by jacobolus on Thursday July 20, 2017 @10:44PM
(#14817699)
The bound we have is apparently: https://en.wikipedia.org/wiki/Prime-counting_function#Inequa...
x/log x < π(x) < 1.25506x/log x
If you want to rewrite that using log2, you get:
1.44270x/log2 x < π(x) < 1.81067x/log2 x
I would hardly call the previous poster’s comment an “explicitly wrong statement for no benefit”. We’re talking about number of bits here.
Re:Dreaming of prime numbers in short intervals
by xyzzyz on Friday July 21, 2017 @02:46AM
(#14818549)
You're missing the point. Asymptotically, we have much better bound than 1.25506 -- the asymptotic bound is indeed 1+e for any e > 0, as the prime number theorem explicitly says that lim pi(n)/(n/log n)) = 1. The constant 1.25506... = 30 * log(113)/113 is only relevant because that's the the smallest global bound, which is there to take care of n = 113.
If you rewrite it to log_2, you get the 1.442... constant, which throws your calculations off by "almost 50%" I mentioned in my comment above. And yeah, it doesn't change anything in the qualititative analysis of storage needs, but that's not my point -- my point is that in math, you should avoid saying things that are explicitly wrong, unless there are very good reasons to do so.
So to implement this approach you would need to store and search a space that grows linearly with the size of the largest number you expect to encounter. However, this is unnecessary because we have faster ways of telling a number is prime other than storing all the prime numbers up to that point.