Here's a math question that may have been answered in the literature, but I haven't seen it anywhere. Maybe one of you professionals can help.
Let's suppose we have an algorithm (function?) that will take a positive integer x as input and output the xth prime. Say it takes some time to compute this prime, but unlike the sieve of Erastothenes it does it without looking at composites. In other words, the sieve has to strike out every multiple of 2,3,5... but this algorithm directly produces the xth prime without testing or dealing in any way (except intrinsically) with non-primes. We'll call this algorithm f(x), though it's doubtful that a single function would fit the description.
Now, let e(n) be a measure of the efficiency of any primality test for declaring a number of size n to be either prime or composite, given in hours.
Let E(n) be the time it takes to find a prime, given in hours.
For example, the USUAL test runs on odd numbers, checking for primality. The time it takes to prove one such number is either composite or prime is e(n), given size n. Then E(n) is e(n) TIMES the number of composites tested before finding a prime.
Now, f(x) as described above doesn't waste time checking composites.
Therefore, my question is, given a target range of size n, how fast would f(x) need to be in order to be as efficient as our fastest primality test now used, in terms of E(x), to find several consecutive primes in the target range?
Put another way, (SIMPLISTIC EXAMPLE) after finding 31, most tests would check 33 and 35 before finding 37 to be prime, while f(x) just goes straight to the next prime, 37, thus saving time. How slow could f(x) be to still be just as efficient? Thought this might be an interesting question.
Aaron

finding a prime p takes about (p!/2 + 1) operations per prime.

most tests would check 33 and 35 before finding 37 to be prime, while f(x) just goes straight to the next prime, 37, thus saving time. How slow could f(x) be to still be just as efficient? Thought this might be an interesting question.

Most algoritms would only test odd numbers, yes. I dont see how the function can jump to 37 directly, whitout knowing that it is a prime -a prime determined by another algorithm-

I don't have an example of a system that spits out the nth prime on command, but I have something close. As an example, 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 {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 85th prime when we input the number 85.

Here's a simplification (example) of what my question is about:

Let's pick a range, say all x between 10^60 and 10^61.
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, using the measure E?

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 of this type, how fast would it have to be, in terms of the size of the primes, to top known techniques? Thanks for the comments, and I hope this helps clarify a question that I think is worth studying.
Aaron

A bench mark test on your program and other top techniques would be sufficient to tell the advantage with a sample of few numbers, not so large that take hours. It looks like, finding the efficiency as you say is as tough as finding that the number(s) is prime or not.

15-2^3=7
15-2^2=11
15-2^1=13
15+2^1=17
15+2^2=19
15+2^3=23
15+2^4=31
15+2^5=47

29?

abs( 3^y * 5^z +/- 2^x ) = q1(x,y,z)

What values can x,y and z take? 0 to infinity?

3^(1000)*5^(1348578475)-2^(28388299900)=7

(okay these numbers do not really give 7, but if there a possibility that a certain prime number can only be found with EXTREMELY high values of x, y and z? If that is the case, then one has to try all combinations of x, y and z?)

Interesting side note:

I have heard that it is not worthwhile maintaining a list of known primes on disk, because it is faster to generate a new list than it is to read the list from disk!

aht,
As I said, to get ALL primes in a range, you must repartition.
29=abs(2^2*5+3^2) which is an expression of q3.
Incidently, very soon in the process, the addition becomes too large and only subtraction can be used (this happens when one side or the other of the +/- must contain enough factors to make it greater than the next prime squared). Even so, all primes (so far) can be found with subtraction alone.
29=abs(3^2*5-2^4), which is an expression of q1.
The size of the exponents needed seems to grow very, very slowly. Maybe if you don't use every partition, you might require very large exponents.

I believe, based only on the experience of having solved so many of these, that it will be possible to put upper bounds on the exponents that depend only on the size of the prime. Let me illustrate what seems to be a "natural phenomenon" when doing these computations.
abs(15+/-2^x)
13,11,7,1,17,49stop subtracting
17,19,23,31,47,79stop adding
Now increment exponent on 3:
abs(45+/-2^x)
and keep going, incrementing exponents on the 3 and 5 as needed.
At some point, you will increment an exponent on 3 or 5 to get the next larger size on the left, and you will get NO OUTPUTS less than 49, particularly with subtraction. I call this the beginning of a "desert", where no outputs are to be found.
At that point, you could stubbornly try higher exponents on the left, until you find a power of 2 on the right that produces more solutions within 49. It might be possible to find all primes in this fashion, BUT...
The interesting thing that I've discovered is that, so far, this isn't necessary. At the point you reach this desert, simply repartition the set and continue:
abs(10+/-3^x) and abs(6+/-5^x)
incrementing powers on the left as needed. So far, this has been sufficient to find all primes in the given range.
There are a staggering number of variables to consider when looking for large primes. The fact that I haven't found an exception (a skipped prime) so far is encouraging, particularly when you consider how unlikely it seems that I would get any sufficiently small solutions at all for some of the "larger" primes. The highest I've gone so far included partitioning and exponentiating primes from the set {2,3,5,7,11,13,17,19,23,29, and 31} and I found every prime from 37 to 37^2=1369, without going beyond the natural "desert" that I mentioned.
One way I've thought about proving no primes are skipped is the following:
29, 30, 31, 32, 33, 34, 35, ...... ,58, 59, 60, 61, 62
0, 1, 2, 3, 4, 5, 6, ........,29, 30, 31, 32, 33
subtract a bottom number from the corresponding top number to get 29. Now, to fit my abs( +/- ) scheme, every top/bottom pair must have a 2, a 3, and a 5 in it, along with no other primes. Now, 2 is in every pair. 3 is in two-thirds of the pairs, and 5 is in two-fifths of the pairs. So to find a pair that has 2,3, and 5 in it, we only need to look at 2/3 * 2/5 = 4/15 so out of 15 such pairs, four of them will have 2,3, and 5 as factors of one number or the other. It get's trickier when we try to eliminate higher primes from the pairs, but notice that five-sevenths of them will NOT have a seven as a factor, nine-elevenths will NOT have 11, eleven-thirteenths will NOT have 13, fifteen-seventeenths will NOT have 17, etc. So multiply all of these by the 4/15 that we found above. Where do we cut it off? I'm still working out the details, but it looks like if our fraction is greater than 1/n, and we've considered less than n pairs so far, we can say there exists a representation of the prime that fits the form given. Or something like that, like I said I'm still looking at it.
To all interested, I suggest working out all of the primes less than 121 this way, doing the process may answer questions more efficiently than I can, and if you still don't have "faith" in this process after trying it out, I'll be very, very surprised. To start out, look at f(x)=abs(105+/-2^x), it is a fascinating exponential expression, with reflection where it becomes negative, and every prime that it puts out occurs on integer values of x. Graphing some of these things in three dimensions is interesting, also, though adjustments are needed because the exponents are all positive, and the "plus" gets graphed separate from the "minus", etc. If you all have a spare minute, please try a couple, you'll be surprised at how easy it is to fill the whole range from 11 to 121. Remember, I did all primes to 1369 in my head, first checking odds by division to see if they were prime, and then finding a form that fits the procedure given.
You will also get a single output that isn't usually considered prime, the number 1. 1=3-2=10-9=15-14 etc. all come from the correct form. I believe it wouldn't be too hard to prove that you can always get the number 1. Also, I note the similarity with the theorem that says you can get every multiple of the gcd of two numbers by using linear combinations of them. I wonder if you can get all RELATIVELY PRIME multiples of the gcd of the left and right sides, i.e. all multiples of 1 that are relatively prime to the left and right, using linear combinations of the left and right with the coefficients restricted to factors already present in that side. Ex: Left->15, Right->2 now use a coefficient having only 1,3,5 as factors, to multiply by the left, and a coefficient having only 1,2 as factors to multiply by the right, then subtract the two results. Can we find all multiples of 1, relatively prime to 15 and 2, with this restricted linear combination? Good question, I think the answer is "yes", at least if we use the other two partitions in the same way.
Aaron

There is no algorithm for directly finding any prime. If you have one, you have solved one of the big enigmas of mathemetics. On the level of the quadrature of the circle. The Nobel prize is waiting.

Otherwise, finding primes by searching is simple and fast.

Hans

Alright, given. However, my algorithm does satisfy the one requirement that it finds primes without any undue checking of composite numbers. All else being the same, if a test finds primes without hours being wasted on numbers that are not prime, it will be more efficient. Say your favorite testing algorithm is testing a number that will prove to be prime, it may be a little faster than mine, BUT if you are testing one hundred numbers, of which only one is prime, mine will find several primes before yours finds that one. THAT'S what I call EFFICIENT. Anyone care to disagree with that?
Aaron

Did you mean directly find the nth prime given n, or directly find ANY prime? If you meant the second choice, then get the Fields medal ready (there isn't a Nobel prize for math).

In case you don't like the WAY I defined my generator, I'll redefine it here for you:

Let p(n) be the nth prime
Let p(n)# be p(n)*p(n-1)*p(n-2)*...*5*3*2
Let abs() be absolute value
Let +/- be "plus or minus", though the theory works with just minus

Let q(x1,x2,x3,...xn):positive integers --> positive integers given by
q(x1,x2,x3,...xn)= abs( A +/- B)
where A and B are given by:
p(n)# divides A*B
p(n+r) doesn't divide A*B for all r in the positive integers
gcd(A,B)=1
each xi is the positive integer exponent on each p(i)

Then if q(x1,x2,x3,...xn) < [p(n+1)]^2, then q(x1,x2,x3,...xn)is prime.

This is because contradiction of the distributive principle shows that q(x1,x2,x3,...xn) will not have any of p(1), p(2),... p(n) as factors, and the square root of q(x1,x2,x3,...xn) is less than p(n+1).

As I said before, to get all primes < [p(n+1)]^2, it's important to use ALL POSSIBLE disjoint partitions of {p(1),....,p(n)} into the two sets to be put into A and B.

This will produce primes without testing any composites, because the elimination of those composites is intrinsic to the definition of A and B, the gcd(A,B)=1, and the "less than" test. This indicates that this algorithm may still be in the running as the most efficient way to find primes, given that it doesn't waste time testing a large number of BIG composites. Prove me wrong, if you dare!

All else being the same, if a test finds primes without hours being wasted on numbers that are not prime, it will be more efficient.

This statement catches my attention. If it finds a prime, is that number proven to be a prime? Or does it just finds a number that may or may not be a prime which still needs to be proven prime by independant means.

So I guess my question is, does one still need to prove that the numbers your algorithm finds are indeed primes?

If you answer yes, than how can you be sure the numbers your algorithm gives are primes. Therefore you must answer no to this.

If no, then prove it please (if only textually. Intuition is also acceptable.)

aht,

These numbers will indeed be prime. First of all, check out my more rigorous definition, which got posted seconds before your last post.

Now, to the proof.

We have abs( A +/- B), where all the primes from 2 to p(n) are factors of either A or B, but not both, so A and B are relatively prime.

Let's drop the abs(), if we get a negative output just swap A and B.

Now, let p(i) be some prime between 2 and p(n), inclusive.

Assume p(i) is a factor of an output, q.

Then we have A-B=q, where p(i) is a factor of both q and (either A or B).
Without loss of generality, let p(i) be a factor of B. Rewrite A-B=q like this:
A=q+B. Since p(i) is a factor of both q and B, the distributive principle implies p(i) is also a factor of A. But A and B are relatively prime -><- contradiction.
Therefore, output q has no factors from the set of primes 2,3,...p(n) that we used to make up A and B.
Now, we are looking at outputs < [p(n+1)]^2, so the square root of q is less than p(n+1), but we've eliminated all primes less than p(n+1) as factors of q.
Therefore, like the sieve of Eratosthenes, q is prime.
The proof for p(i) in A, or for A+B=q, is very similar.
QED

However, my algorithm does satisfy the one requirement that it finds primes without any undue checking of composite numbers. All else being the same, if a test finds primes without hours being wasted on numbers that are not prime, it will be more efficient.

All else isn't the same though. Your algorithm will produce the same prime many times. This heuristic speed comparison won't get anywhere. You're going to have to come up with some actual runtime bounds for your algorithm (along with a proof that it gives all primes, but that's another story).


The method you've described to prove you get all primes (looking at the pairs (29,0), (30,1) etc) won't work. You're trying to guarantee that a pair will have all of 2, 3 and 5 as factors, which is fine and will be easy enough to do. However, this isn't sufficient for your algorithm. You want to find a pair that has ONLY 2, 3 and 5 as factors and neither number is 1. These won't occur in any kind of frequency like 4/15, they will become sparser and sparser as your list goes on, the acceptible pairs are (45,16), (54, 25), (125,96),... the next one, if one even exists, will be greater than (1000029,1000000), which is as far as I've checked (hasty inefficient program took 2 minutes to get this far, I should be able to drop this to 10 seconds with an intelligent algorithm). The point is, some kind of density estimate isn't going to work.

Shmoe,
You're probably right. As I've said, I need to look at it in more detail. What I'm thinking, though, is that the density at some point may still be greater than 1/p(x+1)^2 when you've included all primes <= p(x) in the product of the fractions, I think that might work, since we're looking for how many pairs contain p(1),....,p(a) and don't contain p(a+1),...p(x) for some a, and if we've eliminated p(2)...p(x), then the pairs also can't contain any composite less than [p(x+1)]^2.

I was able to check all pairs (29,0),...(29+10^30,10^30) quite quickly and found no more working pairs than the ones I listed above, so their density is quite sparse and I'm starting to believe there are only finitely many pairs that will work.

Something else interesting, I found no working pairs under this 10^30 cap that would give 253=11*23 using 2,3,5. Even if every prime is expressible using this exponent method, I have serious doubts that you could get every "coprime to 2*3*5 multiple" of these primes.

edit-Off topic-I looked at your original post of this, well over a year ago. While looking that up, I ran into another old post of yours (http://www.sciforums.com/showthread.php?t=29859). If you haven't found the answer to this, I'll resurrect that post and give details if you are still interested.

Shmoe,
Thank you, yes, I would be very interested in more details about this question.
Aaron

p.s. I'm not sure what you mean by the 253=11*23 comment. I assume you mean you took a prime and looked for a pair that gives this prime, but couldn't eliminate 11 and 23 as factors?

Oh, I get it! Okay, if it did work, it should have worked by then (I assume, which I shouldn't)
Aaron

edit: What about 5^3*2 + 3?

My mistake! I erroneously tossed out some pairs whose sum would be acceptible. You can also get 253=2*5+3^4. This also adds a couple pairs whose sum gives 29, (20,9) and (24,5) but no others with one entry below 10^30.

With this in mind, I tried getting 583=11*53 using 2, 3, and 5, and get no results. Same with 1079=13*83, and 1391=13*107. Unless I'm overlooking something again :bugeye: