In an earlier post, I had found the list of prime numbers up to about 50000 and thus determined the fraction of all positive integers that were primes.
Now let's try to evaluate the percentage of numbers that are prime theoretically. In the earlier post I had referred to a wiki link above regarding the same: that the number of prime numbers up to x is 1/ln(x) for large values of x. I couldn't understand the proof. I thought I will try to find my own way to determine the same. So here goes.
I continued from what I had done in the previous post listing prime numbers.
My method estimates the fraction of numbers that are prime by checking the fraction of numbers that have divisors or factors and then subtracting that fraction from 1.
If we can find the fraction of numbers that have some factor, then 1 minus that fraction will be the fraction of primes. The method below uses this rule to estimate the fraction of primes. I also check only for factors that are themselves primes, since there is no point checking with composite numbers as divisors.
First I found all the numbers that are not divisible by 2. This is half of all numbers. Put another way, the number of numbers that are not divisible by 2 is 0.5 of all numbers.
Then I found the number of numbers not divisible by 3. Number of numbers divisible by 3 (3, 6, 9 etc) are 1/3 of all numbers, of which 1/3*1/2 =1/6 are numbers are divisible by 2 also and are already included in the 0.5 mentioned above.
1/3-1/6= 1/6 is the fraction of numbers which are divisible by 3 but not by 2.
Hence the unique fraction of numbers which are divisible by 2 or by 3 is equal to the sum of the fraction of numbers that are divisible by 2 (=0.5) and the fraction of numbers that are divisible by 3 but not by 2 (=1/6=0.17) = 0.67. Hence the fraction of numbers that are neither divisible by 2 nor by 3 = 1-0.67 = 0.33.
Now let's extend this to find the fraction of numbers that are not divisible by 2 or by 3 or by 5.
The fraction of numbers divisible by 5 = 1/5. Of this, the fraction of numbers neither divisible by 2 nor by 3 = 1/5 * 0.33 = 1/15 = 0.07.
The total fraction of all numbers that are divisible by 2 or by 3 or by 5 = 0.67+0.07=0.73. Remember that when you add the fractions, the fractions should represent entities that are mutually exclusive.
To recap, 0.67 is fraction of all numbers divisible by 2 or by 3. 0.07 is the fraction of numbers that are divisible by 5 but not by 2 nor 3. Hence 0.67 and 0.07 are mutually exclusive.
Hence the fraction of numbers that are neither divisible by 2 nor by 3 nor 5 = 1-0.73 = 0.27.
Considering all numbers from 1 to 30, the numbers that are not divisible by 2, 3, 5 are 1, 7, 11, 13, 17, 19, 23, 29: total 8 in number. 8 out of 30 = 8/30 = 0.27. Same as the value we got theoretically from the previous step.
Continuing this way we come to the values in the table below:
A B C D
Prime Fraction of all Fraction of all numbers Fraction of all
Number numbers divisible by this prime numbers that are not
divisible by the number or by any other divisible by this prime
prime number smaller prime number nor by smaller primes
but not divisible from Column A in column A
by earlier
prime numbers
-----------------------------------------------------------------------------------------
2 0.5 0.5 1-0.5=0.5
3 1/3*0.5=0.17 0.5+0.17=0.67 1-0.67=0.33
(0.5 from col D above) (0.17 from Col B
and 0.5 from Col C)
5 1/5*0.33=0.07 0.67+0.07=0.73 1-0.74=0.27
7 1/7*0.27=0.04 0.73+0.04=0.77 1-0.77=0.23
11 1/11*0.23=0.02 0.77+0.02=0.79 1-0.79=0.21
and so on... repeating the steps for each prime number beyond 11.
4253 0.00 0.93 0.07
(to 2 decimal places)
4253 is the 607th prime number (in the series 1, 2, 3, 5, 7...). I just happened to calculate till the 607th prime number. 607 is just an arbitrary number with no significance in this method.
As we go beyond 4253 we will find that the fraction of numbers that are not divisible by any prime number keep decreasing from 0.07 towards (but never becoming) zero. And this is the value that will probably be equal to 1/ln(x) mentioned in the wiki article mentioned earlier.
The calculation is shown in the sheet"Reaction that are not primes" inhttps://docs.google.com/spreadsheets/d/1B2vJgPILb2Cm29Xvc8pa3TASfzoKa35fiiFzrdWqsm8/edit?usp=drivesdk
The calculation is shown in the sheet"Reaction that are not primes" inhttps://docs.google.com/spreadsheets/d/1B2vJgPILb2Cm29Xvc8pa3TASfzoKa35fiiFzrdWqsm8/edit?usp=drivesdk
Using notations:
Column A:
Prime number
n (2, 3, 5, 7, 11, 13...). I did not consider the number 1.
Column B
Fraction of all numbers divisible by the prime number but not divisible by earlier prime numbers:
B(n) = 1/n * D(n-1) : Equation (1)
B(n-1) = 1/(n-1) * D(n-2)
and so on
B(n) = 1/n * [1 - C(n-1)] from equation (3)
= 1/n * [1- Sigma (B(n), n running from n-1 to 2)] from equation (5)
Let's call this Equation (4)
= 1/n * [1- Sigma (B(n), n running from n-1 to 2)] from equation (5)
Let's call this Equation (4)
Note: n-1 is not an algebraic expression, instead it refers to the previous prime number; example, when n=11, n-1=7.
Column C
Fraction of all numbers divisible by this prime number or by any other smaller prime number from Column A:
C(n) = B(n) + C(n-1) : Equation (2)
C(n-1) = B(n-1) + C(n-2)
and so on
C(n) = C(2) + Sigma (B(n), n running from n to 3)
= Sigma (B(n), n running from n to 2), since B(2) = C(2): Equation (5)
This makes sense. The fraction of all numbers that are not primes is equal to the sum of B(n) where each B(1), B(2) etc are mutually exclusive.
The percentage of non-primes = the fraction of numbers divisible only by 2 + the fraction of numbers divisible only by 3 + the fraction of numbers divisible only by 5 + ...
Column D
Fraction of all numbers that are not divisible by this prime nor by smaller primes in column A:
D(n)
= 1 - C(n) : Equation (3)
= 1 - B(n) - C(n-1)
= 1 - 1/n * D(n-1) - (B(n-1) + C(n-2) )
= 1 - 1/n * D(n-1) - 1/(n-1) * D(n-2) - C(n-2)
= 1 - 1/n * D(n-1) - 1/(n-1) * D(n-2) - 1/(n-2) * D(n-3) - C(n-3)
and so on until n=2. This is another form of writing Equation (2) above.
And remember that B(2) = C(2) = D(2) = 0.5. Also when n increases, B and D decrease while C increases towards 1.
Let's now focus on Equations (2) and (4).
Equation 2: C(n) = B(n) + C(n-1)
Equation 4: B(n) = 1/n * [1 - C(n-1)]
Now if you visualize C running a race to reach the value of 1.0, and each time C is incremented by the latest value of B [=B(n)], the divisor n in Equation (4) prevents C from reaching 1. If n was less than or equal to 1, C(n) would reach 1. But n is a prime number which keeps increasing from 2 to 3 to 5 to 7 to 11 and so on. Never will C(n) reach 1. No matter how high the value of n, C(n) will still be less than 1.
Just like the series 1/2 + (1/2)^2 + (1/2)^3... is converging because each number in the series is a fraction, between 0 and 1, of the number to make the sum reach 1.
B(2) + B(3) + B(4) + ... + B(n)
Let's now focus on Equations (2) and (4).
Equation 2: C(n) = B(n) + C(n-1)
Equation 4: B(n) = 1/n * [1 - C(n-1)]
Now if you visualize C running a race to reach the value of 1.0, and each time C is incremented by the latest value of B [=B(n)], the divisor n in Equation (4) prevents C from reaching 1. If n was less than or equal to 1, C(n) would reach 1. But n is a prime number which keeps increasing from 2 to 3 to 5 to 7 to 11 and so on. Never will C(n) reach 1. No matter how high the value of n, C(n) will still be less than 1.
Just like the series 1/2 + (1/2)^2 + (1/2)^3... is converging because each number in the series is a fraction, between 0 and 1, of the number to make the sum reach 1.
B(2) + B(3) + B(4) + ... + B(n)
This is shown in the 'Fractions That are Primes' sheet in https://docs.google.com/spreadsheets/d/1B2vJgPILb2Cm29Xvc8pa3TASfzoKa35fiiFzrdWqsm8/edit?usp=drivesdk
Additional reading:
No comments:
Post a Comment