Is There an Equation for Finding All Prime Numbers?

[andrewey]

This isn't a homework problem, but something I was kicking around. Thus far it has worked for the first 20 primes I could calculate in my head. Does anyone know why this shouldn't work, or an example of it not working for the a specific prime number?

The idea is that all prime numbers can be written in the form of:
{(a+1)n} +a, where a is any number between zero and infinity, and n is also any value of your choice.

Thus examples are: 2n+1, 3n+2, 4n+3...

Love to hear feedback.

 

[dacruick]

your thing doesn't work for 307. so that's a reason

 

[dodo]

I'm not sure what the "thing" is, to begin with. (n+1)^2+n is divisible by 5 whenever n is of the form 5k+1, namely for n=1,6,11,16,21,26,...

 

[dacruick]

when i said thing i meant equation...There is no integer value of n that solves 307

 

[dodo]

Right. I mean I'm not sure of which equation are we talking about.

What you say is that "it" does not produce all primes (307 is missing - among others). What I say is that "it" produces lots of numbers which are not primes. (It remains to be seen if we all talk about the same "it".)

 

[andrewey]

That's true! However, if I add this additional equation (which just changes the positive to a negative), it seems to suit a whole lot more numbers!

(a-1)n +a Where both a and n are any number between 0 and infinity such as:
17n+18 (works for 307).

 

[dodo]

This other equation also produces all primes:
n
See my point?

 

[Norman.Galois]

andrewey, now you must determine which ones are primes from the list your equation gives you. Which is equally hard considering you don't even have all of them.

Dodo pointed that out.

 

[andrewey]

Dodo:

What I was doing wasn't to solve for the prime numbers, but get a way to rewriting them. So I could rewrite seven as 2n+1 using 3 for n (in all my tests I only used prime numbers as n values). Although you get other non-prime numbers if you do it "forward", I thought it was interesting most prime numbers can be rewritten in this form "backwards"

 

[Borek]

Ulam's spiral comes to mind.

http://www.stud.mathematik.uni-stuttgart.de/~kohlsn/images/ulam.gif

 

[dodo]

Hmm, I see, andrewey. But 2n+1 is not prime for n=7, even if 7 is prime.

Edit: sorry, not the counterexample you want. This one goes "backwards": 19 is prime, but is not of the form 2n+1 with n prime, since n=9.

However, I think there is a good intuition working at the bottom of what you're doing. For example, all primes (from 7 onward) are either of the form 6n+1 or 6n+5. But never of the form 6n+0, or 6n+2, or 6n+3, or 6n+4. The key element here is that 6,1 are coprimes, as well as 6,5. In your experiments, you always use formulas like 2n+1, 3n+2, 4n+3, ... where the coefficients are two consecutive numbers; and any two consecutive numbers are coprimes.

 

[CRGreathouse]

The idea is that all prime numbers can be written in the form of:
{(a+1)n} +a, where a is any number between zero and infinity, and n is also any value of your choice.

Thus examples are: 2n+1, 3n+2, 4n+3...

Love to hear feedback.

If you pick a = 0, the equation becomes
n
and it's clear that every prime is of this form. If you pick a = 1, the equation becomes
2n+1
and clearly every odd prime is of this form. So I see no reason to think that this is significant.

Let A = a + 1. Then your form is A(n + 1) - 1. So the essential claim is that a given prime is equivalent to -1 mod A for some A. If you want to make this other-than-trivial, you'd want to put more meaningful restrictions on what values A can take. In particular, you seem to want to say
"For any prime p, p\equiv-1\pmod A for some large A."
and just need a way to formalize "large".

Of course you could always pick A = p + 1, which corresponds to your original equation with n = 0. So the equation is trivial for A very small (2) and very large (p + 1). You might then wonder if in all cases A can be chosen to be between the two in size. You might enjoy finding this result, so I won't give it to you. Hint: Look at the factorization of p + 1.