Breaking the code - The Moosavi Formula
I have found the formula to determine the prime at the k-th level. This formula is named as Moosavi formula formulated by Prof. SMR Hashemi Moosavi. I would say that this is the final formula that unveils the mystery of primes. You will no longer need a computer to determine the prime at the k-th level if you can do it by hands. Here's the list:
Reference:
www.primenumbersformula.com
Issue: Breaking the Code Part 2 -Which is which? The Sieve Algorithms or The Primality Test Equations
Yes, I agree with Mr. Jay that the modern sieve of Atkin is more complicated, but
faster when properly optimized.[1] Atkin's algorithm is actually more efficient than the sieve of eratosthenes when run in computers. This is somehow due to the fact the algorithm takes less memory of the computer than its predecessor the sieve of eratosthenes. This can be proven by the statement from Wikipedia that the Atkin sieve computes primes up to N using O(N/log log N) operations with only N1/2 + o(1) bits of memory. That is a little better than the sieve of Eratosthenes which uses O(N) operations and O(N1/2(log log N)/log N) bits of memory.[2] However, this does not amplify so much for there is only minor advantage when both are compared. But, what I am quite unsure of, is the findings of my pal that the sieve of Eratosthenes is useful only for relatively small primes.[3]
Before we further our discussion, friends, may I know your opinions on the following questions:
1. "Which is better?" - Which do you think is better in finding the large or very large primes: The algorithm method? or Is it the use of primality test equations?
2. "How large is your large?" - How large is your large prime that you think this is the largest prime?
3. "How fast are you?" - Which do you is more faster, the manual method or the computer generated method of locating prime?
If you have comments about my reaction on this topic. Please feel free to write me or post a comment in this site. Thanks.
References:
Jay08_20, [usepmat_group]primes, 1/19/2010 [1], [3]
http://en.wikipedia.org/wiki/Sieve_of_Atkin, (Date accessed: 01/19/2010) [2]
http://stackoverflow.com/questions/622/most-efficient-code-for-the-first-10000-prime-numbers
Issue: How can we determine large and very large primes?
This question on how to determine large and very large primes are most likely asked by most mathematicians, mathematics enthusiasts and students. Even long long time ago, the search for large primes was a focus of study and research. Fortunately, the people in the "gone but not forgotten" era came up with theorems, algorithms and formulas in getting these primes to satisfy the need. Among the contributors were Euclid who developed the Euclidian algorithm, Father Mersenne with his famous Mersenne primes, Eratosthenes with his Sieves of Eratosthenes, Fermat with his Factorization Method and Little Theorem and others like, Gauss, Reimann and Euler who belong to the antique generation. Further studies were also been conducted by enthusiasts in the middle ages and they came up to determine large primes without the help of a computer and mostly, done with their bare hands. To name few of them, they are Anton Felkel, J.P. Kulik, EDF Meissel, BK Parady, J.R. Smith and S. Zarantonello, they are the ones who used to publish tables of primes in large numbers as we say it. Most of their work were based on the theorems and correlations from the prototypes of antique generation.
So, what is the formula to determine exact large or very large primes? The answer is that based on the study, the accurate, exact and realistic method of determining large primes is by the use of Sieves of Erastosthenes. From the name itself you can think that numbers in a range are being sieved or "filtered" and that you can come up with real and exact primes. Here is an example of primes determined by the method in a range less than 100 or 10^2:
1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97....
Of course, the only problem with this method is that this is very tedious when done by hands especially when expanding in the range to 10^3, 10^4, or 10^n, where: n may be any number greater than 2. However, with the advent of computers, large primes may be generated with the Sieve of Eratosthenes faster than any publishable table may be read (Anderson and Bell, 1997, p.116). This is done by writing a program usually in high level computer language like Turbo Pascal or Turbo C using syntax such as arrays and loops that would command the computer to generate large or very large primes to a certain range. (Note: I am sorry that I could not discuss the programming technique here but I could give the key points in making a flowchart for this program.)
The second question one might ask is: What is the use of other theorems or formulas made by Mersenne, Fermat or Gauss in determining large primes? The answer to that is - the theorems or formulas made by these mathematicians were simple assumptions or estimations to get large primes and may or may not be representing exact single large primes. Let us take the definition of Mersenne which states that a Mersenne number is an integer of the form M(n) = 2^n - 1. If a Mersenne number is prime, it is called a Mersenne prime or can be stated this way "If (M(n) is prime, then n is a prime." Let us therefore prove if this is absolute.
Proof:
n 2^n - 1 = M(n) Remarks
1 2^1 - 1 = 1 Empty
2 2^2 - 1 = 3 2 is prime; M(n) = 3 prime
3 2^3 - 1 = 7 3 is prime; M(n) = 7 prime
4 2^4 - 1 = 15 = 3 x 5 4 is not prime; M(n) = 15 composite
5 2^5 - 1 = 31 5 is prime; M(n) = 31 prime
6 2^6 - 1 = 63 = 3^2 x 7 6 is not prime; M(n) = 63 composite
7 2^7 - 1 = 127 7 is prime; so M(n) = 127 prime
8 2^8 - 1 = 255 = 3 x 5 x 17 8 is not prime; M(n) = 255 composite
9 2^9 - 1 = 511 = 7 x 73 9 is not prime; M(n) = 511 composite
10 2^10 - 1 = 1023 = 3 x 11 x 31 10 is not prime; M(n) =1023 composite
11 2^11 - 1 = 2047 = 23 x 89 11 is prime; M(n) = 2047 composite ?
As you can see in the table above, when n = 11; M(n) = 2047 = 23 x 89 which does not produce a single prime but rather composite. Therefore, we can deduce that Mersenne formula is good only for assumption for predicting primes but does not determine exact single large prime. The same thing also happens when we use Fermat number which is defined as a Fermat number is an integer of the form F(n) = 2^2n + 1. If a Fermat number is prime, it is called a prime. Unfortunately, the Fermat number, F(5) = 4294967297 is divisible by 641 and therefore, not a prime number and so Fermat number is also not absolute.
The third question one might ask is: Can we assume for a large prime number using the definitions or theorems made by antique mathematicians? My answer is yes. We could use the ancient formulas to predict or test a certain large number if its a prime or composite. The method is simple you just assume a large or very large number and test it for primality. This is done using the theorem that if the positive integer n is a composite integer, then n has a prime factor p such that p^2 < n.This is also similar with the suggestion made by Dr. Wilkinson in his conversation with Mr. Ulric Cajuste ([usepmat_group]primes,1/16/10). Let us take a proof on this: ex. determine whether n = 521 is prime?
Proof:
We only need to consider primes p that are less than or equal to 2 for 22^2 = 484 which is less than 521 according to the theorem p^2 < n. If we are to use 23^2 = 529 this would be greater than 521 and therefore, does not conform to the theorem. Hence, we have to use 22. The primes less than 22 or equal to 22 are 2, 3, 5, 7, 11, 13, 17, and 19. Trying these primes to be divided to 521, we find that none of the primes divides 521. Therefore, we can say the 521 is a prime.
The only disadvantage with this method is that we just have to keep on guessing numbers until we find numbers to be prime.
Is there another formula aside from Sieves of Eratosthenes that could generate large primes? Yes, I have found one but this is subject yet to scrutiny. The equation looks like this:
P(n) = (2n + 1 - p) dN(n) + p = p (2n + 1 / p)^ dN(n)
where: N if N = 2n + 1 is prime
p if N = 2n + 1 is composite (p: arbitrary prime number)
This equation was formulated by Prof. S.M.R. Hashemi Moosavi who claimed that he solved the problem on prime number generation. To prove this formula would be for our next discussion.
What is the rationale behind why computer companies offer prices to those who can get larger primes? I believe that the rationale behind offering prices by computer companies is that 1.) as a sort of advertisement 2.) to test their product, say computer. I am convinced that the greater weight falls to the second reason since computer companies tend to test their hardware such as processors or chipsets if it can perform long and complex mathematical operations, including also is the speed and time to process instructions.
If you have comments about my reaction on this topic. Please feel free to write me or post a comment. Thanks.
References:
James A. Anderson and James M Bell, Number Theory with Applications, 1997, Prentice Hall Publishing
Prof. S.M.R. Hashemi Moosavi, The Discovery of on-to generating function of the prime numbers and its results, www.primenumbersformula.com, Date accessed: January 17, 2010
Ultima_syd, [usepmat_group]primes, 1/16/2010
