Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Equation for Finding Primes?

  1. Jan 28, 2010 #1
    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. jcsd
  3. Jan 28, 2010 #2
    your thing doesn't work for 307. so thats a reason
  4. Jan 28, 2010 #3
    I'm not sure what the "thing" is, to begin with. [itex](n+1)^2+n[/itex] is divisible by 5 whenever n is of the form [itex]5k+1[/itex], namely for n=1,6,11,16,21,26,...
  5. Jan 28, 2010 #4
    when i said thing i meant equation...There is no integer value of n that solves 307
  6. Jan 28, 2010 #5
    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".)
  7. Jan 28, 2010 #6
    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).
  8. Jan 28, 2010 #7
    This other equation also produces all primes:
    See my point?
  9. Jan 28, 2010 #8
    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.
  10. Jan 28, 2010 #9

    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"
  11. Jan 28, 2010 #10


    User Avatar

    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
  12. Jan 28, 2010 #11
    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
  13. Jan 29, 2010 #12


    User Avatar
    Science Advisor
    Homework Helper

    If you pick a = 0, the equation becomes
    and it's clear that every prime is of this form. If you pick a = 1, the equation becomes
    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, [itex]p\equiv-1\pmod A[/itex] 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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook