Q: Is there a formula for finding primes? Do primes follow a pattern?

Physicist: Primes are, for many purposes, basically random.  It’s not easy to “find the next prime” or determine if a given number is prime, but there are tricks.  Which trick depends on the size of the number.  Some of the more obvious ones are things like “no even numbers (other than 2)” and “the last digit can’t be 5”; but those just eliminate possibilities instead of confirming them.  Confirming that a number is prime is a lot more difficult.

Small (~10): The Sieve of Eratosthenes finds primes and also does a decent job demonstrating the “pattern” that they form.

Starting with 2, remove every multiple. The first blank is a new prime. Remove every multiple of that new prime. Repeat forever or until bored.

The integers come in 4 flavors: composites, primes, units (1 and -1), and zero.  2 is the first prime and every multiple of it is composite (because they have 2 as a factor).  If you mark every multiple of 2, you’ll be marking only composite numbers.  The first unmarked number is 3 (another prime), and every multiple of 3 is composite.  Continue forever.  This makes a “map” of all of the primes up to a given number (in the picture above it’s 120).  Every composite number has at least one factor less than or equal to its square root, so if the largest number on your map is N, then you only need to check up to √N.  After that, all of the remaining blanks are primes.

This algorithm is great for people (human beings as opposed to computers) because it rapidly finds lots of primes.  However, like most by-hand algorithms it’s slow (by computer standards).  You wouldn’t want to use it to check all the numbers up to, say, 450787.

Eratosthenes, in a completely unrelated project, accurately calculated the circumference of the Earth around 2200 years ago using nothing more than the Sun, a little trigonometry, and some dude willing to walk the ~900km between Alexandria and Syene.  This marks one of the earliest recorded instances of grad student abuse.

Medium (~1010): Fermat’s Little Theorem or AKS.

Fermat’s little theorem (as opposed to Fermat’s theorem) works like this: if N is prime and A is any number such that 1<A< N, then if $A^{N-1} \, mod \, N\ne1$, then N is definitely composite and if $A^{N-1} \, mod \, N=1$ then N is very likely to be prime.  “Mod N” means every time you have a value bigger than N, you subtract multiples of N until your number is less than N.  Equivalently, it’s the remainder after division by N.  This test has no false negatives, but it does sometimes have false positives.  These are the “Carmichael numbers” and they’re more and more rare the larger the numbers being considered.  However, because of their existence we can’t use FLT with impunity.  For most purposes (such as generating encryption keys) FLT is more than good enough.

For a very long time (millennia) there was no way to verify with certainty that a number is prime in an efficient way.  But in 2002 Primes is in P was published, which introduced AKS (Agrawal–Kayal–Saxena primality test) that can determine whether or not a number is prime with complete certainty.  The time it takes for both FTL and AKS to work is determined by the log of N (which means they’re fast enough to be useful).

Stupid Big (~101010): Even if you have a fantastically fast technique for determining primality, you can render it useless by giving it a large enough number.  The largest prime found to date (May 2014) is N = 257,885,161 − 1.  At 17.4 million digits, this number is around ten times longer than the Lord of the Rings, and about twice as interesting as the Silmarillion.

Number of digits in the largest known prime vs. the year it was verified.

To check that a number this big is prime you need to pick the number carefully.  The reason that 257,885,161 − 1 can be written so succinctly (just a power of two minus one) is that it’s one of the Mersenne primes, which have a couple nice properties that make them easy to check.

A Mersenne number is of the form Mn = 2n -1.  Turns out that if n isn’t prime, then neither is Mn.  Just like FLT there are false positives; for example M11 = 211 -1 = 23×89, which is clearly composite even though 11 is prime.  Fortunately, there’s yet another cute trick.  Create the sequence of numbers, Sk, defined recursively as Sk = (Sk-1)2 – 2 with S0 = 4.  If $S_{p-2} = 0\,mod\,M_p$, then Mp is prime.  This is really, really not obvious, so be cool.

With enough computer power this is a thing that can be done, but it typically requires more computing power than can reasonably be found in one place.

Update (Jan, 2016): The largest known prime is now 274,207,281 – 1.

Answer Gravy: Fermat’s little theorem is pretty easy to use, but it helps to see an example.  There’s a lot more of this sort of thing (including a derivation) over here.

Example: N=7 and A=2.

[27-1]7 = [26]7 = [64]7 = [64-9×7]7 = [64-63]7 = 1

So, 7 is mostly likely prime.

Example: N=9 and A=5.

[58-1]9 = [57]9 = [25x25x25x5]9 = [7x7x7x5]9 = [49×35]9 = [4×8]9 = [32]9 = 5

Astute readers will note that 5 is different from 1, so 9 is definitely not be prime.

For bigger numbers a wise nerd will typically exponentiate by squaring.

Example: N=457 and A=2.  First, a bunch of squares:

$\begin{array}{ll}\left[2^2\right]_{457}=\left[4\right]_{457}\\\left[2^4\right]_{457}=\left[4^2\right]_{457}=\left[16\right]_{457}\\\left[2^8\right]_{457} =\left[16^2\right]_{457}=\left[256\right]_{457}\\\left[2^{16}\right]_{457}=\left[256^2\right]_{457}=\left[185\right]_{457}\\\left[2^{32}\right]_{457}=\left[185^2\right]_{457}=\left[407\right]_{457}\\\left[2^{64}\right]_{457}=\left[407^2\right]_{457}=\left[215\right]_{457}\\\left[2^{128}\right]_{457}=\left[215^2\right]_{457}=\left[68\right]_{457}\\\left[2^{256}\right]_{457}=\left[68^2\right]_{457}=\left[54\right]_{457}\end{array}$

As it happens, 457-1 = 456 = 256 + 128 + 64+8.

$\begin{array}{ll}\left[2^{456}\right]_{457}\\[2mm] =\left[2^{256}\cdot2^{128}\cdot2^{64}\cdot2^{8}\right]_{457}\\[2mm] =\left[54\cdot68\cdot215\cdot256\right]_{457}\\[2mm] =\left[202106880\right]_{457}\\[2mm] =1\end{array}$

So 457 is very likely to be prime (it is).  This can be verified with either some fancy algorithm or (more reasonably) by checking that it’s not divisible by any number up to √457.

This entry was posted in -- By the Physicist, Math, Number Theory. Bookmark the permalink.

30 Responses to Q: Is there a formula for finding primes? Do primes follow a pattern?

1. Flavian Popa says:

Which makes it even more interesting is the way primes behave at ever bigger and bigger values. Bigger they become, the scarcer they will get, and still no proof of a so called “vanishing point”. I guess working with primes in clever ways is of the essence for cryptographers.

2. The Physicist says:

@Flavian Popa
If you’re interested, the prime number theorem describes how the density of primes decreases at higher values.

3. Dana Jacobsen says:

For numbers less than 2^64, in fact Miller-Rabin is all one needs for no false results, if the right bases are used. The relatively simple BPSW test also has been shown to have no false results below 2^64, and there are still no known counterexamples of any size. AKS was important for proving the problem is deterministic polynomial time, but the algorithm itself is very slow and not used in practice. We have other proof methods (ECPP and APR-CL) that are millions of times faster as well as showing better growth rates at any sizes we would be considering.

4. Hilário Fernandes de Araújo says:

One interesting and constant-independent formula was “discovered” by C.P. Willans (the fifth formula).

http://mathworld.wolfram.com/PrimeFormulas.html

5. Amir Jr says:

C’mon, Silmarillion is waaaaaaaay better than LoTR. The dude really knew how to make something sound epic.

6. Allra Vinur says:

I am interested in the connection between a useful(*) formula for the primes and the Riemann hypothesis (RH). I therefore have 2 questions.

1. Would a prove of RH indicate or even prove that a useful formula for the primes exists?
2. Would the existence of a useful formula prove the RH?

Any references would also be highly appreciated.

(*) By useful formula I am not necessarily referring to a calculation effective formula but rather a structural formula that shows the interconnection of the primes.

7. Kelvin says:

Prime numbers are like “axioms” for numbers, they form the basic building blocks of number, much like maths theorems derived from basic sets of logical axioms. Axioms are so-called facts that known to be TRUE but unprovable. Prime numbers are there but not “generatable”. If the fact that we can generate prime number from any forms of formulas means it’s no longer prime and hence, it can further generated from more basic “prime” numbers…

So, it would seems that most unsolvable mathematical theorem that deals with prime numbers may never able to be solved due to the basic nature of primes, as the Physicist says, are RANDOM.

8. Carl Jalal says:

While you can’t predict when the next prime number is, you can certainly create infinitely many prime numbers as you want.

for example, 2x3x5x7x11x13+1 is a prime number, even though I don’t know what that is.
so multiplying all the primes up to a certain point and adding one to the end always makes a new prime. Which is how you prove that there are infinitely many prime numbers.
2+1 = 3, a prime
2×3+1 = 7, a prime
2x3x5+1 = 31, a prime
2x3x5x7+1 = 211, a prime

9. The Physicist says:

@Carl Jalal
What that technique does is generate numbers that always at least contains a prime that isn’t found in the original product. Sometimes that’s a new prime but, for example, $2\cdot3\cdot5\cdot7\cdot11\cdot13+1 = 30031 = 59\cdot509$. 59 and 509 are both prime, and neither of them are 2, 3, 5, 7, 11, or 13.

10. Dylan says:

@Carl Jahal @Physicist

Could that formula be improved by subtracting the product of some of the chosen primes from the product of the rest of the primes? For instance, by arranging all of the primes up to some value as P*P*P*P . . . -P*P*P . . . . so that the result is less than the largest of these primes squared?

11. K says:

The sequence {15 (n!!)/ 2n+1} appears to return either a whole number, or an irreducible fraction with a prime in the denominator, which remains 2n + 1 if 2n + 1 is prime, for n > 2.

I have no proof, so maybe there is a composite number the thing doesn’t eat.

12. Simran says:

Why is 2^(2^57,885,161 – 1) – 1 not the largest Mersenne prime number??

13. Rajesh Swarnkar says:

How do prime numbers relate to nature? Example? (E.g. Fibonacci series is related with spirals that occur in nature/life.)

14. Boris Sklyar says:

“Physicist: Primes are, for many purposes, basically random.”
Absolutely not.
Fully deterministic algorithm for finding prime numbers:
Positive integers not contained in both 2-dimensional arrays
P1(i,j)=6i^2-1+(6i-1)(j-1) and P2(i,j)=6i^2-1+(6i+1)(j-1)
are indexes p of primes in the sequence S1(p)=6p+5, p=0,1,2,…;
Positive integers not contained in both 2-dimensional arrays
P3(i,j)=6i^2-2i-1+(6i-1)(j-1) and P4(i,j)=6i^2+2i-1+(6i+1)(j-1)
See: http://ijmcr.in/index.php/archive/41-volume-3-issue-3-march-2015/86-title-matrix-sieve-new-algorithm-for-finding-prime-numbers
are indexes p of primes in the sequence S2(p)=6p+7, p=0,1,2,…;

Do you know any attempted prime number formulas that failed? It would help me a lot in my search for creating a formula that generates only primes.

P.S. To everybody: if any of you think there is already a formula for that, There isn’t. The closest are the failed formulas and the formula that either generates a number that is a multiple of a new prime number or a prime number.

16. Boris Sklyar says:

There are two 2-dimensional arrays:
……………………………|5 10 15 20 ..|
6i^2-1+(6i-1)(j-1)= |23 34 45 56…|
……………………………|53 70 87 104…|
……………………………|95 118 141 164…|
……………………………|149 178 207 236…|
……………………………|… … … … |

…………………………….| 5 12 19 26 ..|
6i^2-1+(6i+1)(j-1)= |23 36 49 62..|
…………………………….|53 72 91 110…|
…………………………….|95 120 145 170…|
……………………………..|149 180 211 242..|
…………………………….|… … … … |
Positive integers not contained in these arrays are indexes p of all prime numbers in the sequence S1(p)=6p+5
, i.e. p=0, 1, 2, 3, 4, , 6, 7, 8, 9, , 11, , 13, 14, , 16, 17, 18, , , 21, 22, , 24, , , 27, 28, 29, …
and primes are: 5, 11, 17. 23, 29, , 41, 47, 53, 59, , 71, , 83, 89, , 101, 107, 113, , , 131, 137, , 149, , , 167, 173, 179, ….

There are two 2-dimensional arrays:
………………………………..| 3 8 13 18 ..|
6i^2-1-2i+(6i-1)(j-1)= | 19 30 41 52…|
………………………………..| 47 64 81 98…|
………………………………..| 87 110 133 156…|
………………………………..|139 168 197 226..|
………………………………..|… … … … |

………………………………….| 7 14 21 28 ..|
6i^2-1+2i+(6i+1)(j-1)= |27 40 53 66…|
………………………………….|59 78 97 116..|
………………………………….|103 128 153 178…|
………………………………….|159 190 221 252…|
………………………………….|… … … … |
Positive integers not contained in these arrays are indexes p of all prime numbers in the sequence S2(p)=6p+7, i.e. p=0, 1, 2, , 4, 5, 6, , , 9, 10, 11, 12, , , 15 , 16, 17, , , 20, , 22, , 24, 25 , 26, , , 29, …
and primes are: 7, 13, 19. , 31, 37, 43, , , 61, 67, 73, 79, , , 97, 103, 109, , , 127, , 139, , 151, 157, 163, , , 181 ….

http://www.planet-source-code.com/vb/scripts/ShowCode.asp?txtCodeId=13752&lngWId=3

17. Alberto Einsteino says:

What is a prime?

¿Qué es un número prime?

18. Boris Sklyar says:

Prime numbers (primes) – integers divisible only by 1 and themselves.

19. Psycho-metric says:

New largest prime announced today. (2^74,207,281)-1. http://www.mersenne.org/primes/

20. sagar Agrahari says:

Prime numbers?

21. Anthony Browne says:

Is there a formula for greatest prime factor of n? I’m not referring to the golden goose here, just a formula, summation or otherwise. But, a formula either way. I’m specifically interested in one that does not include other prime formulas such as the prime counting formula. Just a formula in n, maybe including an index of summation if its a sum. I don’t care if it is efficient or not. It just has to equal gpf(n).

22. Boris Sklyar says:

I’m afraid, such a formula does not exist

23. Anthony Browne says:

Interesting. I have one, and several other formulas for prime functions in number theory, all very simple and easily provable. However, I am self taught and have no connections within academia and so I find it impossible to even post a paper. I am ready to share my work with the world. I haven’t the slightest idea how unfortunately. Perhaps we can begin a correspondence. You would be the first to see some of my work and actually understand it. I offer a real and new mathematical body of work with no crackpot or extreme amateur material to waste your time. This seemed as good a place as any. Please email me.

24. Boris Sklyar says:

Thank You .
I’m interesting in number theory and I have proposed so called “matrix sieve” , which for my vew is the simplest algorithm for finding primes ( see: comment above and http://www.planet-source-code.com/vb/scripts/ShowCode.asp?txtCodeId=13752&lngWId=3).
My email: [email protected]

25. Nicholas2030 says:

Dear Anthony Browne,
if you like please send me your results! I am interested to have a look, even I am a Physicist. Best, N

26. Euler was wrong
“Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers and we have reason to believe that it is a mystery into which the mind will never penetrate”

27. Udo Krampe says:

If I found a programm or formula for prime number what shall I do with it and is it something worth, althoug i did not find solution for riemann or goldbach questions. The formula is about 4 rows.

with kind regards

Udo Krampe

28. Rino Squinzani says:

It is now available in English my algebraic proof of the non-existence of a law for prime numbers : tesisuinumeriprimi.blogspot.it
(The paradoxical randomness of prime numbers: an informal introduction.)

29. Russell Lee says:

Hello,
I would like to explain the Prime Locomotive. The locomotive runs on the tracks, the numbers are the ties. The locomotive starts at #1 and finds no number, there so it places the #1 into the prime folder. It then moves on to tie #2 and finds no number there also, so it places #2 into the prime folder, then multiplies the #2 tie down the tracks to place numbers at all even numbered ties. Then the locomotive moves to tie #3 location, finds nothing and places #3 into the prime folder and multiplies 3 down the tracks to put a number at all locations that are multiples of 3. Then on to tie #4, finds a number there so it cannot be a prime, and moves on to tie #5. Finding nothing at tie #5 it places #5 in the prime folder and multiplies 5 down the tracks. As the locomotive travels eternally down the tracks it periodically comes across empty tie locations and places those numbers in the prime folder. Regards, Russell Lee

30. Tom Gilbert says:

Prime Number Theory Postulated Using Set Theory

N = P + nP, where N (all natural whole numbers) equals P (all Primes) plus nP (all non-Primes).
P = N – nP, where P (all primes) equals N (all natural whole numbers) minus nP (all non-Primes).

P = N – {2(N + 1)} – {3(2N + 1)} – {(6N-1)((6N-1) + (12N-1) + (18N-1) + (24N-1)+ …(6(∞)N-1))}
– {(6N+1)((6N-1) + (12N-1) + (18N-1) + (24N-1)+ …(6(∞)N-1))}
– {(6N+1)((6N+1) + (12N+1) + (18N+1) + (24N+1)+…(6(∞)N+1))} ,

where P is all primes, nP is all non-primes, N is all natural whole numbers, and P≠ 0,1.