A Challenge: Uncovering the Pattern of Prime Numbers

[ƒ(x)]

Ok, here's a challenge for you guys.

Lets figure out a pattern for prime numbers.

 

[HallsofIvy]

Right. Get back to you with the solution as soon as I have a moment.

 

[Hurkyl]

Ooh, I've figured it out. The prime numbers appear precisely at those integers that have exactly two positive factors!

 

[ƒ(x)]

Do you mean besides 1 and the number itself?

 

[ƒ(x)]

Ooh, I've figured it out. The prime numbers appear precisely at those integers that have exactly two positive factors!

Um, correct me if I'm wrong, but prime numbers don't have factors.

 

[epkid08]

Um, correct me if I'm wrong, but prime numbers don't have factors.

How can a number not have factors?

 

[CRGreathouse]

Um, correct me if I'm wrong, but prime numbers don't have factors.

Chime in, everyone:

A prime number is divisible by precisely two positive factors, one and itself.

 

[CRGreathouse]

Ok, here's a challenge for you guys.

Lets figure out a pattern for prime numbers.

They're all either of the form 30a + b, where b is in {1, 7, 11, 13, 17, 19, 23, 29}, or in the 'exceptional set' {2, 3, 5}.

 

[dodo]

Of course, a lot of non-primes like 49 or 77 fit the pattern as well. :)

There should be some sort of FAQ on these forums, since this subject (and others) repeat very often, and I believe you (CR) posted a 'prime formula' just a few months ago.

Nor I can say I understand the OP's motivation. This ain't no circus, yo.

 

[Almanzo]

Prime numbers have exactly two (positive integer) divisors: 1, and the number itself. after all, N = 1 * N, and N = N * 1.

As far as I know, some patterns have been found which generate only prime numbers, but no pattern has been found which generates all of them. In general, to see if some large numer is prime, one has to try all possible divisors. (In practice some divisors, such as 2, 3 and 5, are readily discernible if the number is written in base 10.)

One interesting pattern is the following. If the last prime number found is M, calculate N = M! + 1, or 1 * 2 * 3 *...*(M-1) * M + 1. Now, either N is itself prime, or else it has a prime divisor larger than M. This recipe generates an infinite number of primes, therefore proving that there is no largest prime.

Starting with 1, the recipe gives the sequence 2, 3, 7, 71... and already misses 5.

 

[CRGreathouse]

Of course, a lot of non-primes like 49 or 77 fit the pattern as well. :)

Asymptotically, almost all numbers of the form I posted are composite.

There should be some sort of FAQ on these forums, since this subject (and others) repeat very often, and I believe you (CR) posted a 'prime formula' just a few months ago.

The only people who would read the FAQ are those who don't need to read it.

I did post a formula for primes not too long ago.

Nor I can say I understand the OP's motivation. This ain't no circus, yo.

It's widely-believed, though absolutely false, that it is a 'great unsolved problem' in math to find patterns in prime numbers or a formula for primes. Amusingly, little is further from the truth -- any person can easily find patterns in the primes, and formulas/algorithms for the primes are a dime a dozen.

 

[ramsey2879]

As far as I know, some patterns have been found which generate only prime numbers, but no pattern has been found which generates all of them. In general, to see if some large numer is prime, one has to try all possible divisors. (In practice some divisors, such as 2, 3 and 5, are readily discernible if the number is written in base 10.)

One interesting pattern is the following. If the last prime number found is M, calculate N = M! + 1, or 1 * 2 * 3 *...*(M-1) * M + 1. Now, either N is itself prime, or else it has a prime divisor larger than M. This recipe generates an infinite number of primes, therefore proving that there is no largest prime.

Starting with 1, the recipe gives the sequence 2, 3, 7, 71... and already misses 5.

Show us an infinite pattern which generates ONLY PRIME numbers and you will be famous.

 

[Hurkyl]

Show us an infinite pattern which generates ONLY PRIME numbers and you will be famous.

The prime numbers appear precisely at those integers that have exactly two positive factors!

When do I get my accolades?

 

[CRGreathouse]

Show us an infinite pattern which generates ONLY PRIME numbers and you will be famous.

My mousepad (an old sheet of scrap paper) lists nine different infinite patterns that generate only prime numbers: the sieves of Eratosthenes, Pritchard (x2), Dunten-Jones-Sorenson, Atkin-Bernstein, Galway (x2), and Sorenson, along with Bernstein's version of AKS. (It also mentions the Miller-Rabin test, but that generates infinitely many composites -- though it still produces mostly primes.) I could probably list ten more prime-generating patterns/methods/algorithms off the top of my head.

Admittedly, all of these people are famous to some degree. But less complicated or worthwhile methods are created all the time. Further, there are methods (like the LL test for Mersenne primes) that are conjectured to produce infinitely many primes but no one has proven it yet.

 

[dodo]

I believe the 'great unsolved problem' is a closed form for the sequence of primes. This thread won't rest in peace until you copy it *again*, or paste a link, or something.

In the meantime, Google is wise, Google is good. http://mathworld.wolfram.com/PrimeFormulas.html

 

[CRGreathouse]

I believe the 'great unsolved problem' is a closed form for the sequence of primes.

Yes, because an amazing achievement like Sorenson's pseudosquare sieve (deterministically detecting primes in log-squared space as fast as Miller-Rabin!) is somehow less meaningful than some computationally worthless double summation based on Wilson's theorem.

 

[nomentanus]

There are a number of algorithms to derive primes, it goes without saying - but these don't resolve to, or immediately suggest any simple predictable "pattern". Yet the distribution of the primes does have what seems to be apparent "pattern", it could be said, anyway. Against this, Mandlebrot patterns aren't apparent by just glancing at the equation for that set, either.

 

[soandos]

what exactly is Sorenson's pseudosquare sieve?

 

[CRGreathouse]

The basic idea doesn't actually come from Sorenson but from the pseudosquare primality test of Lukes-Patterson-Williams. Most of the basic ideas can be found here:
http://www.ams.org/mcom/1996-65-216/S0025-5718-96-00762-4/S0025-5718-96-00762-4.pdf

The original LPW paper is "Some results on pseudosquares", Math. Comp. 65 (1996). The Sorenson paper that turned it into an efficient sieve is on SpringerLink here:
http://www.springerlink.com/content/914n525q4801q7q1/
(1-page preview; full text at some colleges; also printed as a chapter in Algorithmic Number Theory)

 

[kenewbie]

Maybe I am misreading what some of the more prominent people in this thread are saying, but a function such that

f(n) = p_n

would surely be a feat which guarantees a spot in mathematical history?

The trouble with the approaches that already exist seem to be that either they don't generate all, or when they generate all, they also generate a lot of garbage (like negative values that have to be discarded and such).

I as a complete nub in the field of math I feel like making a prediction (while I am still sufficiently naive to do so):

Any breakthrough in a sequentially generating prime formula will rely on a breakthrough in factoring, which in turn will rely on refinement of modular arithmetic.

so there.

k

 

[CRGreathouse]

Maybe I am misreading what some of the more prominent people in this thread are saying, but a function such that

f(n) = p_n

would surely be a feat which guarantees a spot in mathematical history?

No. It wouldn't even guarantee that you could publish a paper on it -- though if it's creative, a journal like American Mathematical Monthly or Recreational Mathematics might take it.

 

[kenewbie]

No. It wouldn't even guarantee that you could publish a paper on it -- though if it's creative, a journal like American Mathematical Monthly or Recreational Mathematics might take it.

Wow! But there is no such function found to date is there? And I thought the Riemann zeros were all about modifying gauss' ln-based prime prediction to be 100% accurate? I realize that it's applications has moved beyond that now though.

And "we found a new biggest prime" stories get published all the time (at least in newspapers), which seems a lot more useless.

I get a sneeking suspicion that I have to unlearn everything thought to me by the pop-sci math books.

k

 

[CRGreathouse]

Wow! But there is no such function found to date is there?

First, the function is just that: f(n) = the nth prime number, if n is a positive integer, and undefined otherwise.

But there are probably a good half dozen or dozen closed form versions of that formula, based on things like Wilson's Theorem. None of them are particularly interesting.
http://mathworld.wolfram.com/PrimeFormulas.html

And I thought the Riemann zeros were all about modifying gauss' ln-based prime prediction to be 100% accurate?

That's not entirely untrue. But the value to Riemann's approximation formula (or Gauss', or the log one) have value not because they're the best we can do, but because they're easy to calculate.

Take
$$F(n)=\left\lfloor\cos^2\left(\pi((n-1)!+1)/n\right)\right\rfloor$$
and
$$P(n)=\sum_{k=2}^nF(n)$$

Now P(n) is the number of primes up to n. Computing P(500) takes about 2 seconds on my machine (and is actually inaccurate due to rounding issues, but I'll ignore that for the moment). Computing P(5000) would probably take an hour (since precision would need to be very high).

Computing Riemann's approximation R(n) to the number of primes up to n is much faster. In fact, Pari reports that it took 0 ms to compute $R(10^{100})\approx4.36197198714070315909950911\times10^{97},$ which is probably the same as the true count of the primes to all displayed decimal places.

I get a sneeking suspicion that I have to unlearn everything thought to me by the pop-sci math books.

You know, this topic comes up a lot. What pop-math books are saying things like this?

 

[Antuan]

If anyone could find a pattern in the following sequence, maybe we could find a pattern for prime numbers...

-8
-1
-7
2
-4
3
1
-3
2
-4
5
-1
6
4
-2
5
-1
2
0
-2
-6
-8
-2
-6
0
-6
-8
-8
0
-6
-2
-6
-2
-8
0
0
-2
-6
-8
1
-1
-5
-7
-1
-7
1
1
-5
-1
-7
1
-5
1
-1
-1
-4
2
0
-4
2
-4
-4
-6
0
-6
-4
0
-6
0
-6
-4
3
-5
-5
3
3
1
-5
1
-5
-3
3
1
-3
-5
-3
3
-5

This sequence is produced from a particular prime number function where no numbers greater than 6 or less than -8 are produced.

 

[CRGreathouse]

Is that a signed version of Sloane's http://www.research.att.com/~njas/sequences/A040164 ?

I warn you, that will be markedly less useful when the average gap between primes becomes much larger than 10.

 

[ramsey2879]

First, the function is just that: f(n) = the nth prime number, if n is a positive integer, and undefined otherwise.

But there are probably a good half dozen or dozen closed form versions of that formula, based on things like Wilson's Theorem. None of them are particularly interesting.
http://mathworld.wolfram.com/PrimeFormulas.html

Can you list any functions F(n) = the nth prime number that will gve an answer independently of the determination of all lower primes?

Also, can you give a function P(n) which gives a 1 or 0 depending upon whether n is prime or not that in effect does not depend upon the calculation or n! or of all primes less than the square root of 'n'?

If yes to either question, please cite relevant descriptive material.

 

[CRGreathouse]

Can you list any functions F(n) = the nth prime number that will gve an answer independently of the determination of all lower primes?

Also, can you give a function P(n) which gives a 1 or 0 depending upon whether n is prime or not that in effect does not depend upon the calculation or n! or of all primes less than the square root of 'n'?

I don't understand what you mean by "function", since functions don't rely on things like the determination of primes or the calculation of n!. f(n) = 2 * n! does not rely on the calculation of n!; it's just a map from 1 to 2, 2 to 4, 3 to 12, 4 to 48, etc.

Do you mean an algorithm? One algorithm for calculating 2 * n! would be n!*2; another would be prod(k=1,n,k)+prod(k=1,n,k); another would be prod_primes(p=2,n,f(p,n)), f(p,n) = 0 for n < p, f(p,n) = 2*floor(n/p)+f(p,floor(n/p)) for n >= p. The first two seem to use the factorial; the third doesn't seem to use it (but it uses a function which may seem related).

Do you mean a closed-form formula? In that case, what do you consider a closed-form formula? If you were as restrictive as "polynomial" there would be no such functions; for broader definitions, there may be. Further, it's not clear what it means for a closed-form formula to be independent of the determination of smaller primes: this is a restriction on an algorithm, not a formula. A formula is just a string of symbols along with rules for putting them together and calculating with them.

Do you mean something other than "function", "algorithm", and "closed-form formula"?

 

[dodo]

Some formulas are 'covert sieves'. For example.

$$f(n) = \prod_{k = 2}^{ \lfloor \sqrt n \rfloor } (n - k \lfloor {n \over k} \rfloor )$$​

produces a 0 if n is composite, and a non-zero if n is prime.

 

[rscosa]

Hi!

Can you list any functions F(n) = the nth prime number that will gve an answer independently of the determination of all lower primes?

Also, can you give a function P(n) which gives a 1 or 0 depending upon whether n is prime or not that in effect does not depend upon the calculation or n! or of all primes less than the square root of 'n'?

If yes to either question, please cite relevant descriptive material.

Something like:
$$L_n=L_{n-2}+L_{n-3}$$ with $$L_0=0, L_1=2, L_3=3$$
also called the Perrin sequence.