Method for generating prime numbers - Computers, Math, Science, and Technology

WP Members: > 75,000

New Today: 13
New Yesterday: 34

Method for generating prime numbers

Previous 1, 2, 3, 4, 5, 6, 7, 8 Next

Wrong Planet Autism Forum Index -> Computers, Math, Science, and Technology

NakaCristo
Tufted Titmouse

Joined: Jan 24, 2012
Age: 26
Posts: 49
Location: Santander, Spain

Posted: Tue Feb 21, 2012 3:54 am Post subject:

Ancalagon wrote:

NakaCristo wrote:

With a Sieve of Eratosthenes approach we would get a block of n numbers (hence spatial complexity O(n), but that is another matter)
and then apply sieves.
The sieve by p requires looking O(n/p) ~ O(n) (as we use primes p<=sqrt(n)<<n).
We have a sieve for each prime p<=sqrt(n), this is pi(sqrt(n)) \in O(n^(1/2)/log n)
Again we have O(n^(3/2)/log n).

This isn't wrong, since O() is an upper limit, but according to a couple of papers I've found, the Sieve of Eratosthenes runs in O(n) or O(n log log n). (I think the difference is a matter of an optimization being made or not.)

The Sieve of Atkin runs in O(n/log log n). So both of them are a bit faster than using AKS on every number less than n, but the small amount of difference surprised me.

Declension wrote:

If you did have a proof, what would the theorem be?

If we had the best single prime checker (call its running time s) and the best sieve prime checker (call its running time m), then for creating a list of all primes < n, m=O(s). In other words, they might be asymptotically the same, or s might be asymptotically slower.

I have done in Maple the following implementation of the Sieve, for the same size that I got with my previous approach in 1 minute:

Quote:

s:=time();
N:=13254203;
S:=floor(sqrt(N));
L:=Array([seq(true,i=1..N)]):
for p from 2 to S do:
if(L[p])then
#Sieve by p
for n from 2*p to N by p do
L[n]:=false;
od;
fi;
od;
e:=time();
print("Tiem elapsed",e-s);

And I got "Tiem elapsed", 47.338.

So at least for small numbers the sieve is actually faster as you said.
Seems I had something wrong in my reasoning, the O(n/p) ~ O(n) is be a little brute. They can be added correctly using Prime_harmonic_series

heavenlyabyss
Phoenix
Phoenix

Joined: Sep 10, 2011
Posts: 530

Posted: Tue Feb 21, 2012 4:17 am Post subject:

As a person with a background in computer programming, I am definitely interested in formulas for speeding up calculation in prime calculation. However, I guess I am more drawn to pure math. Efficient algorithms and recursive algorithms are very important and practical, but they are not quite what I am looking for. What do you think of this quote? n a 1975 lecture, D. Zagier commented "There are two facts about the distribution of prime numbers of which I hope to convince you so overwhelmingly that they will be permanently engraved in your hearts. The first is that, despite their simple definition and role as the building blocks of the natural numbers, the prime numbers grow like weeds among the natural numbers, seeming to obey no other law than that of chance, and nobody can predict where the next one will sprout. The second fact is even more astonishing, for it states just the opposite: that the prime numbers exhibit stunning regularity, that there are laws governing their behavior, and that they obey these laws with almost military precision" (Havil 2003, p. 171). Confirms my suspicions. I would love to see a proof that there is no formula for generating primes that does not rely on recursion. I most likely would not understand it but I would still be interested in seeing it if anyone know of one. I'm not a high level mathematician but I am fascinated by this stuff. Anyone have further insight?

Declension
Phoenix
Phoenix

Joined: Jan 21, 2012
Posts: 1686

Posted: Tue Feb 21, 2012 4:22 am Post subject:

Ancalagon wrote:

I'm still confused about how to make sense out of your terminology "single prime checker" and "sieve prime checker".

If a "single prime checker" does this:

Quote:

(1.) Input N, Output whether N is prime

And a "sieve prime checker" does this:

Quote:

(2.) Input N, Output all primes from 1 to N

Then you are claiming that running a single prime checker on every number from 1 to M will never be faster than running a sieve prime checker on M? Well of course not! The sieve prime checker is more specialised. Or is there some sense of the word "sieve" that means that it can apply to some algorithms of type (2.) and not others?

Declension
Phoenix
Phoenix

Joined: Jan 21, 2012
Posts: 1686

Posted: Tue Feb 21, 2012 4:24 am Post subject:

heavenlyabyss wrote:

I would love to see a proof that there is no formula for generating primes that does not rely on recursion.

There is a method for generating all primes from 1 to N that does not rely on recursion. It's just the obvious one. Go through each number from 1 to N, and for each number, check whether any number lower than it goes into it.

heavenlyabyss
Phoenix
Phoenix

Joined: Sep 10, 2011
Posts: 530

Posted: Tue Feb 21, 2012 4:32 am Post subject:

Declension wrote:

heavenlyabyss wrote:

I would love to see a proof that there is no formula for generating primes that does not rely on recursion.

Okay, well, I consider that an algorithm.

I guess I was not clear with my wording.

Recursion was the wrong word to use.

I was referring to something more along these lines of Euler's equation, namely n^2 + n + 41, which gives all the primes form n= 0 to 39.

An interesting formula, but clearly artifical since it fails for n>=40. I guess I would like to see a proof that no finite equation is satisfactory. Intuitively, this actually seems to be pretty obvious, but proving it would be difficult I would think.

Declension
Phoenix
Phoenix

Joined: Jan 21, 2012
Posts: 1686

Posted: Tue Feb 21, 2012 4:36 am Post subject:

heavenlyabyss wrote:

I was referring to something more along these lines of Euler's equation, namely n^2 + n + 41, which gives all the primes form n= 0 to 39.

Ah okay, so you are speculating that there is no "nice" equation involving a variable n such that the equation is true if and only if n is prime?

It is difficult to prove things like that, because the word "nice" isn't actually such a simple concept. I guess it means "able to be written as a finite amount of multiplication, addition, exponentation, infinite sums, infinite products, etc. etc."

EDIT: look here, some results on this sort of thing are known:
http://en.wikipedia.org/wiki/Formula_for_primes

Last edited by Declension on Tue Feb 21, 2012 4:42 am; edited 1 time in total

heavenlyabyss
Phoenix
Phoenix

Joined: Sep 10, 2011
Posts: 530

Posted: Tue Feb 21, 2012 4:43 am Post subject:

Declension wrote:

heavenlyabyss wrote:

I was referring to something more along these lines of Euler's equation, namely n^2 + n + 41, which gives all the primes form n= 0 to 39.

Ah okay, so you are speculating that there is no "nice" formula that takes any number n and gives you the nth prime number? That seems true.

But it is difficult to prove things like that, because the word "nice" isn't actually such a simple concept. I guess it means "able to be written as a finite amount of multiplication, addition, exponentation, infinite sums, infinite products, etc. etc."

I mean, I can give you a formula for it. It is:

Quote:

phi(n)

where phi(n) is the nth prime number. Wink

But this formula isn't "nice".

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.

Declension
Phoenix
Phoenix

Joined: Jan 21, 2012
Posts: 1686

Posted: Tue Feb 21, 2012 4:49 am Post subject:

heavenlyabyss wrote:

Legendre has proven that there is no rational algebraic function that gives all primes.

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

Quote:

n = (k + 2)(1 −
[wz + h + j − q]2 −
[(gk + 2g + k + 1)(h + j) + h − z]2 −
[16(k + 1)3(k + 2)(n + 1)2 + 1 − f2]2 −
[2n + p + q + z − e]2 −
[e3(e + 2)(a + 1)2 + 1 − o2]2 −
[(a2 − 1)y2 + 1 − x2]2 −
[16r2y4(a2 − 1) + 1 − u2]2 −
[n + l + v − y]2 −
[(a2 − 1)l2 + 1 − m2]2 −
[ai + k + 1 − l − i]2 −
[((a + u2(u2 − a))2 − 1)(n + 4dy)2 + 1 − (x + cu)2]2 −
[p + l(a − n − 1) + b(2an + 2a − n2 − 2n − 2) − m]2 −
[q + y(a − p − 1) + s(2ap + 2a − p2 − 2p − 2) − x]2 −
[z + pl(a − p) + t(2ap − p2 − 1) − pm]2)

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 Tue Feb 21, 2012 5:04 am; edited 1 time in total

heavenlyabyss
Phoenix
Phoenix

Joined: Sep 10, 2011
Posts: 530

Posted: Tue Feb 21, 2012 5:02 am Post subject:

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?

Declension
Phoenix
Phoenix

Joined: Jan 21, 2012
Posts: 1686

Posted: Tue Feb 21, 2012 5:08 am Post subject:

heavenlyabyss wrote:

It doesn't generate primes, it is just a convoluted test for primes?

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 Tue Feb 21, 2012 5:15 am; edited 1 time in total

heavenlyabyss
Phoenix
Phoenix

Joined: Sep 10, 2011
Posts: 530

Posted: Tue Feb 21, 2012 5:14 am Post subject:

Declension wrote:

heavenlyabyss wrote:

It doesn't generate primes, it is just a convoluted test for primes?

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 simpler concepts. It removes some of the magic of being a prime.

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.

Ancalagon
Computer Geek
Phoenix

Joined: Dec 26, 2007
Posts: 2411

Posted: Tue Feb 21, 2012 12:03 pm Post subject:

Declension wrote:

I'm still confused about how to make sense out of your terminology "single prime checker" and "sieve prime checker".

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.

heavenlyabyss wrote:

The second fact is even more astonishing, for it states just the
opposite: that the prime numbers exhibit stunning regularity, that
there are laws governing their behavior, and that they obey these
laws with almost military precision" (Havil 2003, p. 171).

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.
_________________
"A dead thing can go with the stream, but only a living thing can go against it." --G. K. Chesterton

Declension
Phoenix
Phoenix

Joined: Jan 21, 2012
Posts: 1686

Posted: Tue Feb 21, 2012 7:29 pm Post subject:

Ancalagon wrote:

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:

Quote:

(1.) Input N, Output whether N is prime

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:

Quote:

(2.) Input N, Output all primes from 1 to N

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?

Quote:

(3.) Input N, Input primes from 1 to N, output primes from 1 to N

Obviously not, because that's trivial.

Or does a sieve prime checker do this?

Quote:

(4.) Input N, Input primes from 1 to floor(sqrt(N)), Output primes fom 1 to N

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?

Ancalagon
Computer Geek
Phoenix

Joined: Dec 26, 2007
Posts: 2411

Posted: Tue Feb 21, 2012 10:57 pm Post subject:

Declension wrote:

How can you codify "doesn't make use of other 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.

Quote:

And what does a sieve prime checker do? It doesn't do this:

Quote:

(2.) Input N, Output all primes from 1 to N

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.

Quote:

What are the inputs for a sieve prime checker?

Just n.
_________________
"A dead thing can go with the stream, but only a living thing can go against it." --G. K. Chesterton

heavenlyabyss
Phoenix
Phoenix

Joined: Sep 10, 2011
Posts: 530

Posted: Wed Feb 22, 2012 5:05 am Post subject:

Declension wrote:

heavenlyabyss wrote:

It doesn't generate primes, it is just a convoluted test for primes?

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

Wrong Planet Autism Forum Index -> Computers, Math, Science, and Technology

Previous 1, 2, 3, 4, 5, 6, 7, 8 Next

Forums ©

Read more Articles on Wrong Planet

Wrong Planet is a Registered Trademark.
Copyright 2004-2013, Wrong Planet, LLC and Alex Plank. Alex does public speaking for Autism.

Advertise on Wrong Planet

Wrong Planet News Wrong Planet Forums