Method for generating prime numbers

Post Reply New Topic

Lol, very clever.

Seriously, though, I think I may have answered my own question. I was looking it up in the meanwhile, and apparently Legendre has proven that there is no rational algebraic function that gives all primes. This is a start, but then again, you have a point that "nice" is subjective, what about other methods?

Okay, I will stay out of this for the meanwhile. I have answered my main question.

On the Wikipedia page, there is a crazy result. Apparently n is prime if and only if n > 0 and



for some nonnegative integers a,...,z. That's pretty darn nice. (note: all of those "2"s are exponents)

This only uses multiplication, addition, and negation! You can't get any nicer than that.

I guess that the Legendre result doesn't apply here, because we have to specify "n > 0". In other words, this formula generates all primes, and also a bunch of nonpositive numbers. But all of the positive numbers that it generates are primes, and all of the primes are generated by it.

Last edited by Declension on 21 Feb 2012, 5:04 am, edited 1 time in total.

What the heck. That is crazy.

Very interesting.

Umm, I do not understand it all, but regardless, very interesting.

Even still, I hate to be a buzz kill, but this is a test, and not a formula, am I correct?

How can this test be used practically? It doesn't generate primes, it is just a convoluted test for primes? Am I missing something here? Is this test of practical use?

It could be used to generate a list of all the primes. Think of it like this. For any 26-tuple (a,...,z) of nonnegative integers, the formula either spits out a nonpositive number, or it spits out a prime.

It is possible to list all of the 26-tuples of nonnegative integers into a certain order. There are infinitely many of them, but you can deal with them "one at a time".

So, run through all of these 26-tuples, and for each one, check the formula. If it's positive, then it's a prime and add it to the list. If not, then move on.

In this way, you get an ever-growing list of primes such that any given prime will eventually end up on the list. Some primes might be listed more than once.

But if you just want an ever-growing list of primes such that any prime number will eventually end up on the list, there are simpler and faster ways to do it.

I doubt that this formula is useful, but it is very interesting to me, because it shows that the concept "being a prime" really can be broken down into much more "boring" concepts. It removes some of the mysterious cloak surrounding the idea of prime numbers.

Last edited by Declension on 21 Feb 2012, 5:15 am, edited 1 time in total.

Okay, I think I get what you are saying. I will have to think about this a little more if I want to make a meaningful post about, but I will think about it.

Thanks.

A single prime checker tells you whether a single number is prime without relying on a bunch of other primes. A sieve prime checker gives a list of all primes < n, and uses primes from a partial list to help generate the others. That isn't any sort of official terminology or anything, just what I'm using to distinguish between the 2.


There is a set of numbers called the "lucky numbers" that have some similar properties to the primes. You start in the same way as with the sieve of Eratosthenes, but the elimination process is slightly different. Instead of eliminating multiples, you eliminate based on the position in the remaining list. First, eliminate every 2nd number on the list, starting with 2. Then, since 3 is the next largest surviving number, eliminate every 3rd surviving number. Then, eliminate every 7th surviving number, because 7 survived, and so on.

It just doesn't seem like a rigorous concept to me. I can't make precise sense of it.

So a single prime checker does this:

But does it have to satisfy additional constraints before it counts as a "single prime checker"? How can you codify "doesn't make use of other primes"? I mean, obviously it can only "know about" a finite number of primes, because it is a finite algorithm and we are not giving it a list of primes as input.

And what does a sieve prime checker do? It doesn't do this:
because you say that the sieve prime checker already knows about a list of primes. Or are you saying that it finds a list of primes as part of its internal process? Well of course it does, because it outputs a list of primes!

So does a sieve prime checker do this?

Obviously not, because that's trivial.

Or does a sieve prime checker do this?


What are the inputs for a sieve prime checker? Is it just N, or is it N and a list of primes? Which list of primes?

The algorithm doesn't use other primes. If it doesn't have a list of primes hardcoded, doesn't generate a list of primes, and doesn't receive a list of primes, then it doesn't have any primes to work with, so it will not use them. If that doesn't answer your question, then I don't understand your question.


It does do that. It would have to generate at least some primes, because n can be arbitrarily large. It can call itself recursively to generate a smaller sublist of primes. Or it could do it in a loop, and ask itself, "do I have enough primes already to get all the way to n? If not, I'll generate some more and check again".

A sieve prime checker filters out composites using knowledge of primes. It uses some primes to get more primes.

If the sieve of Eratosthenes knows [2,3] is a complete list of primes < 4, then it can find out that [2,3,5,7,11,13] is a complete list of primes < 16, and it can use that to find out the list of primes < 256.


Just n.

Okay, I have done some my thinking on my own and have to come to appreciate how brilliant this set of equations really is.

Actually when I first saw that there were 26 variables exactly I was actually skeptical (one variable for each letter of the alphabet?) Lol, kind of funny, but apparently just a coincidence.

Yes, it is not efficient, but like you say, it does remove some of the magic from primes, which is exactly the kind of insight I was looking for. I haven't actually tested this with any numbers but it would be interesting to write a computer program that uses this concept to check and see if it actually works (I checked the sources, and it looks pretty accurate as far as I can tell).

I'd write it if someone can explain the nature of each function.

I have posted the Diophantine equations from two different sources. The second source expresses the formulas in a more compact way and may be easier to program. I have not checked its accuracy, of course but I am assuming it legit.

http://mathworld.wolfram.com/PrimeDioph ... tions.html

http://en.wikipedia.org/wiki/Formula_for_primes

I feel rather silly, I did not get what the different parts of the equation meant. It makes more sense now. Basically I have to do Gaussian elimination on the 14 equations and see if there are possible solutions?
I think there's a u^8 in in equation 11. x.x Not even going to bother.

Yes, it is a little complex. I'm sure you could program it but it wouldn't be the effort most likely unless you truly believe it will bring fruitful results. I am sure it has already been done by others.

As far as making the algorithm efficient I am not a good enough programmer to say how to do that. It was just an idea I was throwing out there.

I don't know if the equation gets more complex as k goes up. If it does there's little point trying to implement it when there are already working algorithms that solve it for a single input. I read that there's a set of equations with 52 variables and only x^4, but that's still out of scope for my math abilities. Now... if there was one with 208 variables and only x^1, that would be "easy". :3

For prime numbers (p), under 3 squared; p = 2a + 1 (where a = any whole number)
For prime numbers (r), under 5 squared; r = 3p +/- 2 or 4
For prime numbers (i), under 7 squared; i = 5r +/- 6 or 12 or 18 or 24
For prime numbers (m), under 11 squared; m = 7i +/- 30 or 60 or 90 or 120 or 150 or 180
For prime numbers (e), under 13 squared; e = 11m +/- 210 or 420 or 630 or 840 or 1050 or 1260 or 1470 or 1680 or 1890 or 2100

(A no. divisible by a, but not divisible by a group b +/- A no. divisible by group b, but not a = A no. not divisible by a or b.)

* Some rules give 1 but this is not prime.

Prime numbers under 3 squared (or 9, as I know it) are 2, 3, 5 and 7. This "rule" is thus correct, but largely through coincidence - it returns odd numbers, not primes, which is why it breaks down after this arbitrary point.

It also doesn't cover 2.



Primes up to 25 are 2, 3, 5, 7, 11, 13, 17, 19, 23. This formula is even more useless than the first one, as we're looking at four possible values for each value of p (3p+2, 3p+4, 3p-2, 3p-4). And you need to work out the values of p first.



I'm not even going to bother checking these. That last line has 20 possible permutations for every value of m and only holds up to 169! How many permutations are there for numbers up to 17 squared (289)? 32 per value of e?



I'm not sure what this is referring to. It doesn't seem to relate to the earlier formulae.

A more interesting observation is that every prime number aside from 2 and 3 (I agree that 1 is not prime) can be expressed as 6n+/-1. Not every value of 6n+1 or 6n-1 is prime, but every prime IS expressable this way. Proof:

Any number can be expressed as 6n+k, where k is in the range 0-5.
For k=0, this is trivial - the number is divisible by 6, so not prime.
For k=2 or 4, 6n+k is divisible by 2.
For k=3, 6n+k is divisible by 3.
So all primes must necessarily be either 6n+1 or 6n+5. We can express the second as 6n-1 (because 6n+5 is 6(n+1)-1, and n is an arbitrary value here).