Is There an Equation for Finding All Prime Numbers?

  • Thread starter andrewey
  • Start date
  • Tags
    Primes
In summary, Dodo says that "it" does not produce all primes, while Andrey says that "it" produces lots of numbers which are not primes.
  • #1
andrewey
3
0
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:
Physics news on Phys.org
  • #2
your thing doesn't work for 307. so that's a reason
 
  • #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,...
 
  • #4
when i said thing i meant equation...There is no integer value of n that solves 307
 
  • #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".)
 
  • #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).
 
  • #7
This other equation also produces all primes:
n
See my point?
 
  • #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.
 
  • #9
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
Ulam's spiral comes to mind.

http://www.stud.mathematik.uni-stuttgart.de/~kohlsn/images/ulam.gif [Broken]
 
Last edited by a moderator:
  • #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:
  • #12
andrewey said:
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, [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.
 

1. What is the equation for finding primes?

The equation for finding primes is known as the Sieve of Eratosthenes. It is an algorithm that identifies all prime numbers up to a given limit.

2. How does the Sieve of Eratosthenes work?

The Sieve of Eratosthenes works by creating a list of numbers from 2 to a given limit, and then repeatedly crossing out all multiples of each prime number until only prime numbers are left.

3. What is the time complexity of the Sieve of Eratosthenes?

The time complexity of the Sieve of Eratosthenes is O(n log log n), making it one of the most efficient methods for finding prime numbers.

4. Can the Sieve of Eratosthenes be used for large numbers?

Yes, the Sieve of Eratosthenes can be used for large numbers. However, as the numbers get larger, the amount of memory and processing power required also increases.

5. Are there any other equations for finding primes?

Yes, there are multiple equations and algorithms for finding prime numbers, such as the Sieve of Atkin and the AKS primality test. However, the Sieve of Eratosthenes is one of the most commonly used and efficient methods.

Similar threads

  • Linear and Abstract Algebra
Replies
1
Views
789
  • Programming and Computer Science
Replies
22
Views
596
Replies
5
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
885
  • Precalculus Mathematics Homework Help
Replies
9
Views
1K
  • Precalculus Mathematics Homework Help
Replies
2
Views
838
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • General Math
Replies
7
Views
1K
  • General Math
Replies
23
Views
3K
  • Linear and Abstract Algebra
Replies
11
Views
2K
Back
Top