12-04-2003
Prime quantities II
I decided not to append this additional article on prime quantities as a 6th part to the other "prime quantities" article, because then it will probably be read quite rarely, although it is more important than the approximation formulas to be found there - besides, I think that five parts are more than enough for one article.
Some readers may be familiar with the original approximation formulas for the amount of prime numbers as well as the nth prime:
1.) Between 1 and n there are approximately n / ln(n) prime numbers 2.) On average the n-th prime number is approximately n * ln(n)
If one tries these formulas, however, one realizes relatively soon that they are not really suitable for everyday mathematical use, because they become more accurate only with very large numbers. For smaller numbers, therefore, there are other approximation formulas, which overshoot the target for those larger numbers and become less accurate, but which are significantly more useful for "human" numbers. Those alternatives can be found in the first "prime quantities" article.
However, since the above approximations are extremely fundamental in nature, which are also proven, it occurred to me to check them for other properties that might have something to do with prime numbers. So I first had the idea to simply combine both opposite approximations - so let's put n / ln(n) inside n = m * ln(m), which then looks like this:
Now we start with m = 5. We'll see what the prime quantity approximation tells us and then double the m in each case. The following table is the result:
In the third column, the blue numbers to the right illustrate that the number of primes between m * ln(m) and 2m * ln(2m) practically doubles, apart from minor deviations. That doesn't sound very spectacular so far - and it isn't yet, because the results are as inaccurate in case of small numbers as they are with the approximation n / ln(n). The trick now lies more in this: if you know how many primes there are between 1 and a number x = n * ln(n), you can estimate that there must be almost twice as many primes between 1 and a number y = 2n * ln(2n). You can also take any other factor in place of 2, but the accuracy is still enormous. I show this by some examples in on the one hand different orders of magnitude and on the other hand with different factors.
1. We know that there are exactly four prime numbers between the numbers 1 and 8, namely 2, 3, 5 and 7. Now we only need to know how 8 can be written approximately as n * ln(n). For this, 5 * ln(5) = 8.0472 fits quite well. Using this method, we can now multiply the number 5, for example, by a factor of 10 and thus estimate that between 1 and the number 50 * ln(50) = 195.6 there must be about 40 (ten times as many) prime numbers. Exactly 44 prime numbers exist between 1 and 195, so we have a deviation of four here.
2. Between 1 and 100 there are exactly 25 prime numbers. To write 100 approximately as n * ln(n), we simply put 30 for n - this gives us 30 * ln(30) = 102.0359. If we now multiply this 30 by a factor of 3 to get 90, we can estimate that there should be around 25 * 3 = 75 primes between 1 and 90 * ln(90) = 404.983. The exact number of primes in this range is 79, so again an estimation error of four.
3. In the number range between 1 and 10000 there are precisely 1229 prime numbers. To write 10000 approximately as n * ln(n), I estimate n to be 1390 after 5 tries, which gives us 1390 * ln(1390) = 10059.51. If we double the 1390 now, there should be about twice as many primes between 1 and 2780 * ln(2780) = 22045.97, so 1229 * 2 = 2458. In fact, there are exactly 2471 primes between 1 and 22045, so an error of 13 in this case.
In principle, I could show countless other examples. There are also examples with larger errors, which however are practically not significant due to correspondingly large orders of magnitude. Bottom line is: you only really need rough approximations if you want to know the amount of primes between two numbers. You only have to multiply the n of n * ln(n) by an arbitrary factor, which doesn't even need to be an integer - after that, you just multiply the already known amount of primes within the given number range (e.g. 25 primes between 1 and 100) by the same factor and thus have a very accurate estimate. Thus, it is not necessary to perform extraordinarily complicated arithmetic operations. Only some approximations. Below is a table with more examples. Note that the number of prime numbers almost doubles from row to row, except for the small, obviously chaotic deviation, which is always given relative to the number of prime numbers of the respective row above.
F(n) = int[n * ln(n)]
Some readers may be familiar with the original approximation formulas for the amount of prime numbers as well as the nth prime:
1.) Between 1 and n there are approximately n / ln(n) prime numbers 2.) On average the n-th prime number is approximately n * ln(n)
If one tries these formulas, however, one realizes relatively soon that they are not really suitable for everyday mathematical use, because they become more accurate only with very large numbers. For smaller numbers, therefore, there are other approximation formulas, which overshoot the target for those larger numbers and become less accurate, but which are significantly more useful for "human" numbers. Those alternatives can be found in the first "prime quantities" article.
However, since the above approximations are extremely fundamental in nature, which are also proven, it occurred to me to check them for other properties that might have something to do with prime numbers. So I first had the idea to simply combine both opposite approximations - so let's put n / ln(n) inside n = m * ln(m), which then looks like this:
Now we start with m = 5. We'll see what the prime quantity approximation tells us and then double the m in each case. The following table is the result:
In the third column, the blue numbers to the right illustrate that the number of primes between m * ln(m) and 2m * ln(2m) practically doubles, apart from minor deviations. That doesn't sound very spectacular so far - and it isn't yet, because the results are as inaccurate in case of small numbers as they are with the approximation n / ln(n). The trick now lies more in this: if you know how many primes there are between 1 and a number x = n * ln(n), you can estimate that there must be almost twice as many primes between 1 and a number y = 2n * ln(2n). You can also take any other factor in place of 2, but the accuracy is still enormous. I show this by some examples in on the one hand different orders of magnitude and on the other hand with different factors.
1. We know that there are exactly four prime numbers between the numbers 1 and 8, namely 2, 3, 5 and 7. Now we only need to know how 8 can be written approximately as n * ln(n). For this, 5 * ln(5) = 8.0472 fits quite well. Using this method, we can now multiply the number 5, for example, by a factor of 10 and thus estimate that between 1 and the number 50 * ln(50) = 195.6 there must be about 40 (ten times as many) prime numbers. Exactly 44 prime numbers exist between 1 and 195, so we have a deviation of four here.
2. Between 1 and 100 there are exactly 25 prime numbers. To write 100 approximately as n * ln(n), we simply put 30 for n - this gives us 30 * ln(30) = 102.0359. If we now multiply this 30 by a factor of 3 to get 90, we can estimate that there should be around 25 * 3 = 75 primes between 1 and 90 * ln(90) = 404.983. The exact number of primes in this range is 79, so again an estimation error of four.
3. In the number range between 1 and 10000 there are precisely 1229 prime numbers. To write 10000 approximately as n * ln(n), I estimate n to be 1390 after 5 tries, which gives us 1390 * ln(1390) = 10059.51. If we double the 1390 now, there should be about twice as many primes between 1 and 2780 * ln(2780) = 22045.97, so 1229 * 2 = 2458. In fact, there are exactly 2471 primes between 1 and 22045, so an error of 13 in this case.
In principle, I could show countless other examples. There are also examples with larger errors, which however are practically not significant due to correspondingly large orders of magnitude. Bottom line is: you only really need rough approximations if you want to know the amount of primes between two numbers. You only have to multiply the n of n * ln(n) by an arbitrary factor, which doesn't even need to be an integer - after that, you just multiply the already known amount of primes within the given number range (e.g. 25 primes between 1 and 100) by the same factor and thus have a very accurate estimate. Thus, it is not necessary to perform extraordinarily complicated arithmetic operations. Only some approximations. Below is a table with more examples. Note that the number of prime numbers almost doubles from row to row, except for the small, obviously chaotic deviation, which is always given relative to the number of prime numbers of the respective row above.
F(n) = int[n * ln(n)]
- Between 1 and F(____4) = _____5 there are ____3 prime numbers
- Between 1 and F(____8) = ____16 there are ____6 prime numbers (Deviation 0)
- Between 1 and F(___16) = ____44 there are ___14 prime numbers (Deviation 2, denn 6 * 2 = 12)
- Between 1 and F(___32) = ___110 there are ___29 prime numbers (Deviation 1)
- Between 1 and F(___64) = ___266 there are ___56 prime numbers (Deviation -2)
- Between 1 and F(__128) = ___621 there are __114 prime numbers (Deviation 2)
- Between 1 and F(__256) = __1419 there are __223 prime numbers (Deviation -5)
- Between 1 and F(__512) = __3194 there are __452 prime numbers (Deviation 6)
- Between 1 and F(_1024) = __7097 there are __909 prime numbers (Deviation 5, denn 452 * 2 = 904)
- Between 1 and F(_2048) = _15615 there are _1820 prime numbers (Deviation 2)
- Between 1 and F(_4096) = _34069 there are _3644 prime numbers (Deviation 4)
- Between 1 and F(_8192) = _73817 there are _7286 prime numbers (Deviation -2)
- Between 1 and F(16384) = 158991 there are 14597 prime numbers (Deviation 25)
- Between 1 and F(32768) = 340695 there are 29239 prime numbers (Deviation 45, denn 14597 * 2 = 29194)
- Between 1 and F(____8) = ____16 there are ____6 prime numbers (Deviation 0)
- Between 1 and F(___16) = ____44 there are ___14 prime numbers (Deviation 2, denn 6 * 2 = 12)
- Between 1 and F(___32) = ___110 there are ___29 prime numbers (Deviation 1)
- Between 1 and F(___64) = ___266 there are ___56 prime numbers (Deviation -2)
- Between 1 and F(__128) = ___621 there are __114 prime numbers (Deviation 2)
- Between 1 and F(__256) = __1419 there are __223 prime numbers (Deviation -5)
- Between 1 and F(__512) = __3194 there are __452 prime numbers (Deviation 6)
- Between 1 and F(_1024) = __7097 there are __909 prime numbers (Deviation 5, denn 452 * 2 = 904)
- Between 1 and F(_2048) = _15615 there are _1820 prime numbers (Deviation 2)
- Between 1 and F(_4096) = _34069 there are _3644 prime numbers (Deviation 4)
- Between 1 and F(_8192) = _73817 there are _7286 prime numbers (Deviation -2)
- Between 1 and F(16384) = 158991 there are 14597 prime numbers (Deviation 25)
- Between 1 and F(32768) = 340695 there are 29239 prime numbers (Deviation 45, denn 14597 * 2 = 29194)