Clarification: Test VS Generator

[synergy]

Okay, a test is a function f: positive integers --> {0,1} such that it outputs a zero if the integer is composite and a one if the integer is prime.

A generator is a function f: positive integers --> prime numbers such if x is the input then the xth prime is the output. It doesn't require checking a bunch of composites.

How efficient would the second type of function have to be to be quicker than the first type, for a large range of primes of any size.

Amateur, this is about my theory, not yours. Doesn't even apply to yours.

Aaron

[synergy]

say you input 10000 and it gives you the 10000th prime, which requires some time to compute
then you input 10001 and it gives you 10001th prime
then you input 10002 and it gives you 10002th prime
then you input 10003 and it gives you 10003th prime
each of which requires some time to compute.

now this program is racing against a program that checks all odds after the 10001th prime to see if they are prime. after checking alot of composites, it finds the 10002th prime. then it checks more odds until it finds the 10003th prime.

My question is, how efficient must the first program be to surpass the second program in efficiency?

[synergy]

I'm not saying my method does exactly that, but it's close to working like that, and I'm sure that it's not efficient enough, yet, but I have plans to "tweak" the method.
Aaron

[synergy]

I guess that exactly the question I have is, how fast must it run to find ALL OF the primes in a range at the same rate that the second program finds them, given that the second program checks every odd between the nth prime and the n+1th prime, and the first program just computes the nth prime and the n+1th prime directly from input values n and n+1, not needing to test anything at all - particularly not even considering values between the two primes. No test, just input and output. Input 42, output the fourty-second prime. Maybe next you input 100 and output the one hundredth prime, it can skip around that way.

Put another way, given that you know 2,3,5...31, find primes through 53.
The second program tests 33,35,37,39,41,43,45,47,49,51, and 53 for primality. The first program inputs 12 and gets out the 12th prime, 37,
inputs 13 and gets out 41, inputs 14 and gets out 43, inputs 15 and gets out 47, inputs 16 and gets out 53, and is done. 5 inputs, 5 primes output.
The second program input 11 odd numbers to test for primality, and output 5 primes.
For higher ranges, the second program might have to test hundreds of consecutive odds to find 5 consecutive primes, while the first program will still only have 5 inputs to output the 5 primes.

[biwema]

Assuming you want to find the n'th prime:

No proof here, but I would prefer this strategy:

The function Pi(x) is more efficient than calculating all Primes up to a limit. According to http://numbers.computation.free.fr/C...ingPrimes.html Pi(x) has a Complexity of O(x^1/2).

Li(x) and R(x) are Approximations which should be better than an error of sqrt(x).

Say you want to find the 100000th prime

So my Recipe:

1. Calculate Li(x) or R(x) and try to approximate Li(x) = 100000 (with Newton?)

2. Calculate Pi(x) of that x you have found.

3. Sieve forward or back until you have found your prime.


In case you want to find all primes in some range, you can either sieve or test all for primalty.
Which approach is faster depends on the size of the range and Primes, the algorithm and the architecture of the computer.

In case you found the starting prime using the recipe above, you still have the sieved array (step 3) in your computer, where you just can pick your primes.

[xilman]

Originally Posted by biwema

Assuming you want to find the n'th prime:

No proof here, but I would prefer this strategy:

The function Pi(x) is more efficient than calculating all Primes up to a limit. According to http://numbers.computation.free.fr/C...ingPrimes.html Pi(x) has a Complexity of O(x^1/2).

Li(x) and R(x) are Approximations which should be better than an error of sqrt(x).

Say you want to find the 100000th prime

So my Recipe:

1. Calculate Li(x) or R(x) and try to approximate Li(x) = 100000 (with Newton?)

2. Calculate Pi(x) of that x you have found.

3. Sieve forward or back until you have found your prime.


In case you want to find all primes in some range, you can either sieve or test all for primalty.
Which approach is faster depends on the size of the range and Primes, the algorithm and the architecture of the computer.

In case you found the starting prime using the recipe above, you still have the sieved array (step 3) in your computer, where you just can pick your primes.

But sieving involves checking composites, unless I misunderstand your use of that term.

Binary search lets you avoid that particular problem. To find the i-th prime, find by some means two values of x such that pi(x1) <= i <= pi(x2). One such approach would be to start with x1 = 2, x2=3 and then repeatedly iterate x1=x2, x2=2*x2 until the inequality is satisfied. Then raise x1 or lower x2 as appropriate, always maintaining the inequality, until x1==x2.

Paul

[synergy]

Nice to see some of you are seeing what I'm getting at...
For anybody still not sure, I've simplified it somewhat:

Let's pick a range, say all x between 10^9 and 10^10.
Now, let e=the efficiency of standard programs in proving x is either prime or composite, in terms of the time it takes.
Let E=the time it takes to find (and prove the primality of) a prime number

Then E=e*(the number of integers you tested before finding the prime)

So, if you can prove a number is prime in 100 hours, and it takes my program 1000 hours to generate a prime, then e=100 for you and 1000 for me, yours is ten times more efficient than mine at PROVING PRIMALITY.

However, if you examined 100 integers before finding the prime, then it took you 10000 hours to find the prime, so E=10000 for you and still only 1000 for me, and mine is ten times more efficient than yours for FINDING A PRIME.

Now, I think my question is more clear, i.e. how efficient must a program of the second type be, in order to be as fast as the first type?

I welcome all coments, both positive and negative criticism, although really, how can you criticize a question, when I'm not making any claim? I've already stated my algorithm has a setback or two, such at duplicate prime outputs. I just want to know, in theory, if we had an "oracle" program, how fast would it have to be, in terms of the size of the primes, to top known techniques? Thanks for the comments, I'll study them.
Aaron

[synergy]

Here's a couple examples of my algorithm:
Let's look at the absolute value of 15 plus or minus 2^x, for outputs less than 7^2=49. No such output can have a factor of 2,3, or 5. This is one of a sequence of equations which gets all primes less than 49. I write this as abs( 15 +/- 2^x ) = q(x), where q(x)<49. Actually, if you want the entire theory in a nutshell, look at
abs( 3^y * 5^z +/- 2^x ) = q1(x,y,z) where q1(x,y,z)<49,
then look at q2(x,y,z)= abs( 2^x*3^y +/- 5^z ) and
q3(x,y,z) = abs( 2^x*5^z +/- 3^y), where qi<49. You can see that I've partitioned the set {2,3,5} into two disjoint sets, one on each side of the +/-. If you work this out, you will get every prime less than 49, depending on the integer exponents >0 that you input. When q1 gets "tired", move to q2, etc. For the next step in the algorithm, partition the set of primes {2,3,...43} into two disjoint subsets, one on each side of the +/-, with each prime independently exponentiated with positive integers, and the output will be prime when it is less than 47^2=2209. To get all primes in that range, repartition the sets as necessary. I haven't actually gotten that high so far, but I have found every single prime less than 37^2=1369 using this method.

Now, my question wasn't exactly about this algorithm, since the primes it finds come in no linear order and my algorithm does have repeated outputs i.e. it might produce 29 six times (though I expect the repeats to dwindle at high prime values). Also notice that, like the sieve, you can get a set "enriched" with primes simply by ignoring the less-than test, for example, 15 +/- 2^x will eliminate all composites with 2,3, or 5 as factors, even if we look at outputs higher than 49. My question was about an "ideal" program that produces the 49th prime when we input the number 49, and how fast such a program would need to be, since, like mine, it doesn't eliminate composites one at a time but rather it eliminates them all from the start, which might make it more efficient in terms of finding a prime even if it is slower at proving primality. I think this is a useful question, as it might provide an "upper-bound" of sorts on how fast we could find primes.
Aaron

[ET_]

It takes less than one twentieth of second to BUILD ALL primes in the range 10^9-10^10.

It takes (nearly) forever to prove for primality one number with one million digits.

There are deterministic (APR-CL and ECPP) and probabilistic (Miller-Rabin) algorithms that use a time that is proportional to the length of the prime to test.

I would not try to squash a mosquito with a cannonball, there are obviously more efficient instruments to do it. Conversely, you can't scare out an elephant with a toothpick.

It's a matter of scale.

If your algorithm has a resolution time that grows slower than (say) APR-CL, then I'd really be interested in it; however it should be tested on a range where its time is comparable to other known algorithms to be correctly valued.

What I am trying to say is that I would never test for primality each odd in the range you proposed, because there are far faster methods to check or even create them.

That said, I'm not deducing that your system won't work, I'm just asking for a fair comparison.

Luigi

[R.D. Silverman]

Originally Posted by synergy

Nice to see some of you are seeing what I'm getting at...
For anybody still not sure, I've simplified it somewhat:

Let's pick a range, say all x between 10^9 and 10^10.
Now, let e=the efficiency of standard programs in proving x is either prime or composite, in terms of the time it takes.
Let E=the time it takes to find (and prove the primality of) a prime number

Then E=e*(the number of integers you tested before finding the prime)

So, if you can prove a number is prime in 100 hours, and it takes my program 1000 hours to generate a prime, then e=100 for you and 1000 for me, yours is ten times more efficient than mine at PROVING PRIMALITY.

However, if you examined 100 integers before finding the prime, then it took you 10000 hours to find the prime, so E=10000 for you and still only 1000 for me, and mine is ten times more efficient than yours for FINDING A PRIME.

Now, I think my question is more clear, i.e. how efficient must a program of the second type be, in order to be as fast as the first type?

I welcome all coments, both positive and negative criticism, although really, how can you criticize a question, when I'm not making any claim? I've already stated my algorithm has a setback or two, such at duplicate prime outputs. I just want to know, in theory, if we had an "oracle" program, how fast would it have to be, in terms of the size of the primes, to top known techniques? Thanks for the comments, I'll study them.
Aaron

"So, if you can prove a number is prime in 100 hours, and it takes my program 1000 hours to generate a prime, then e=100 for you and 1000 for me, yours is ten times more efficient than mine at PROVING PRIMALITY."

This is meaningless gibberish. You are comparing TWO DIFFERENT THINGS.
One is an algorithm that GENERATES primes, another is one that TESTS
CANDIDATES FOR PRIMALITY.

They are two different things. Your "questions" are devoid of any
mathematical rigor. They are meaningless. Your use of your variable 'e'
is gibberish because you are assigning constants to things that should
be functions of the PROBLEM SIZE.

Asking in vague general terms for the "best algorithm" is meaningless
because different algorithms have different crossover points, and different
algorithms behave different on varying computer architectures. You also
have to consider differences in programming technique.

I have said this before and you have ignored the advice.

Go *LEARN* something about this subject. Learn about algorithm complexity.
Learn about different types of algorithms. Learn what a Turing machine is.
Learn that there are different models of computation. Learn some number
theory.

[synergy]

Thanks, Luigi, I'll look those things up when time permits. Admittedly, I have little experience at the computer side of this endeaver, I am more comfortable with the theoretical math, hence I'm "asking the experts" my questions. Please replace the range I gave with whatever makes the numbers work out better as you read it.

Bob,

I will learn more of these things when I have time.
I thought it was understood that both e and E were the VALUE OF functions OF the size of the primes in the range that I specified, since I said that e is the efficiency of proving x is prime and I specified that x was in the range given. For VALUE OF functions, substitute the word CONSTANT. I was very clear in how I stated this. Read it again.
I do know a good bit about number theory (obviously there is alot that I don't know also, including much about its application to modern prime testing algorithms). That's why I'm asking you guys that are on the front lines of this field. We're all on the same team, unless you would rather the set of mathematicians not be a connected set?

No, they aren't really different in that I am proving the primality of one number i.e. the prime that I generate. You are proving alot of numbers are composite and then that one number is prime. Please consider this. Just because I am generating a prime doesn't mean I am not proving its primality. I understand, by now, that most people searching for primes are only considering the efficiency of the test, not of the entire testing process that eventually culminates in finding a prime. My generator also can test all integers i.e. if it is not an output then it is composite, else it is prime. It is just a different way of looking at it, the sieve of Aristothenes works the same way, if it isn't crossed out it is output as a prime, if it is crossed out it is not output and is a composite - my method just crosses them out right from the start.
Consider how many composites you have looked at before finding a large prime. If you could eliminate that stage, is there really any way you could say that it wouldn't be more efficient at finding primes, in terms of hours?