Re: EFFICIENCY: PRIME TEST vs PRIME GENERATOR
From: Peter Webb (webbfamily-diespamdie_at_optusnet.com.au)
Date: 10/22/04
- Next message: Virgil: "Re: proof"
- Previous message: Virgil: "Re: Numbering of Octants"
- In reply to: synergy: "EFFICIENCY: PRIME TEST vs PRIME GENERATOR"
- Next in thread: Bob Silverman: "Re: EFFICIENCY: PRIME TEST vs PRIME GENERATOR"
- Messages sorted by: [ date ] [ thread ]
Date: Fri, 22 Oct 2004 18:17:47 +1000
"synergy" <ace2_004@yahoo.com> wrote in message
news:200410212346.i9LNkdw17252@proapp.mathforum.org...
> 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.
>
>
> The following was taken from a few entries I've made elsewhere.
> Anticipating that some of the same questions may come up, I have put some
> of my answers together all in one place, so it's kinda long. Thanks in
> advance for your patience.
>
>
> 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, so
> e(n)=E(n) for it.
> 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.
>
> 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 using all three functions, 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}, which you found in the last
> step, 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, though
> the answer may be pertenant to my algorithm to a large extent.
>
> 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. 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.
>
> 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.
>
> 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 o!
> f 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 a!
> nswer is "yes", at least if we use the other two partitions in the same
> way.
>
> Given, there is no perfect formula to find the xth prime by inputting x.
> 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.
>
> If you have gotten to this point, thanks for your patience, and for any
> comments you may add. Happy prime hunting!
> Aaron
>
The short, simple answer to your question is that if you choose x at random,
the probability of it being prime is 1/ln(x), and you must check of the
order of ln(x) numbers to find the next prime. So for numbers of the order
of 10^60 (the size you nominated), about each 145th number is prime, so you
may have to check 70 on average. Taking out those divisible by 2,3,7 and 7
probably reduces this to about 20 or so.
The efficiency of checks for primality for the remaining numbers varies
according to how big the numbers are, and how certain you need to be that
the number is prime. Many tests (and all the fast tests) indicate that a
number is likely or almost certain to be prime; they don't guarantee it. For
many applications, that may be sufficient.
If you haven't found it,
http://www.utm.edu/research/primes/
is an excellent reference.
- Next message: Virgil: "Re: proof"
- Previous message: Virgil: "Re: Numbering of Octants"
- In reply to: synergy: "EFFICIENCY: PRIME TEST vs PRIME GENERATOR"
- Next in thread: Bob Silverman: "Re: EFFICIENCY: PRIME TEST vs PRIME GENERATOR"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
