# Equation for Finding Primes?

1. Jan 28, 2010

### 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.

Last edited: Jan 28, 2010
2. Jan 28, 2010

### dacruick

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

3. Jan 28, 2010

### 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,...

4. Jan 28, 2010

### dacruick

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

5. Jan 28, 2010

### 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".)

6. Jan 28, 2010

### 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).

7. Jan 28, 2010

### dodo

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

8. Jan 28, 2010

### 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.

9. Jan 28, 2010

### 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"

10. Jan 28, 2010

### Staff: Mentor

Ulam's spiral comes to mind.

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

Last edited by a moderator: May 4, 2017
11. Jan 28, 2010

### 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.

Last edited: Jan 28, 2010
12. Jan 29, 2010

### CRGreathouse

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.