From: Jim Choate <ravage@EINSTEIN.ssz.com>
Date: Wed, 25 Nov 1998 04:58:37 +0800
To: cypherpunks@EINSTEIN.ssz.com (Cypherpunks Distributed Remailer)
Subject: Re: A bit more on Goldbach's and Primes (fwd)
Message-ID: <199811242017.OAA26647@einstein.ssz.com>
MIME-Version: 1.0
Content-Type: text



Forwarded message:

> Subject: Re: A bit more on Goldbach's and Primes
> Date: Tue, 24 Nov 1998 13:18:13 -0600 (CST)
> From: ichudov@Algebra.Com (Igor Chudov @ home)

> According to the original conjecture, there are two prime numbers P1 and
> P2 such that N=p1+p2.
> 
> Rewriting this: N = 2 + (p1-1) + (p2-1).
> 
> That is, two plus two evens that are each one less than a prime.
> 
> That's eighth grade math.

No, shit. It's a pity nobody seem to have ever carried it through and
published it.

> > Process:
> > 
> > 1.	Pick an even number
> > 2.	Select largest prime that is smaller by at least 4.
> > 3.	Add 1.
> > 4.	The difference between 1 and 3 should be a p-1. Add one to the
> > 	difference and it must be in the list of primes. If it's not then
> 
> if it is not then it must have not been in the list of primes.

Exactly, I've a latter version that covers the various boundary conditions
and what they mean. 9 and 15 for example aren't prime so because that number
doesn't appear in the list of primes you know that this prime won't work as
a candidate and you go pick the next lower one.

If this is your only objection with this algorithm then I'm covered.

> > Observation:
> > 
> > This technique could be used to extrapolate potential unknown primes from
> > known primes since it produces a much smaller list of potential candidates 
> > than simply testing consecutive odds via a sieve. It also is not as porous
> > as Mersenne Prime tests.
> 
> Bullshit.
> 
> Your "technique" ASSUMES that you already know the "largest prime that
> is smaller by at least 4".

But you do. You have a list of known primes as I said originaly. Should have 
looked at the list of the first 1000 primes that was attached. If you don't
want an array you could always impliment a Seive of Eratosthanese for example
to generate them as required. This is an approach I'm looking at currently
with a Perl implimentation.

Hell, even if you start off with only 2 and 3 defined as prime you can
generate the others, though it doesn't appear to be sufficient to prove
primality. It does reduce the number of candidate odd numbers to examine for
primality.

Given [ 2, 3 ] and Goldbach's Extension:

6 = 2 + 2 + 2		p = 3, p = 3

8 = 2 + 2 + 4           p = 3, p = 5
 
We do a Seive of Eratosthanese and find 5 is prime so we now have:

[ 2, 3, 5 ]

10 = 2 + 4 + 4		p = 5, p = 5

12 = 2 + 4 + 6          p = 5, p = 7

So we check 7 and find it's prime and we now have:

[ 2, 3, 5, 7 ]

And so on.

The real advantage comes into play for very large primes since they get more
sparse implying that a strictly direct approach (eg applying a Seive to
every odd number) gets more and more non-primes to sift through. This
technique reduces that set considerably because it gives you a known list of
primes that you look through for existance.

> > 2+(largest_known_prime-1)+(next_smallest_unknown_prime-1)=big_even_number
> > 
> > So, we need a way of guestimating the magnitude of the next prime and pick
> > big_even_numbers that are appropriate.
> > 
> > Observation: For a given x the number of primes <x is limited by x/ln(x).
> >              So we could note the points where x/ln(x) increases by 1.
> > 
> 
> Your observation is incorrect.
> 
> Consider x = 8.  x/ln(x) =~ 3.84, but the number of primes < 8 (2,3,5,7) is
> 4, that is more than 8/ln(8).

I'd say round up the 3.84. This is modulo math so fractions like this are
impossible to deal with in this context because they aren't defined. The
normal process is that if a fraction is produced it rounds up to the next
larger integer (re the Camel & Banana problem).

It's not my observation. If you go and look on The Primes webpage or any
number theory book that covers limits on primes then you will find this
asymptote given as the most commenly used.

> I suggest checking observations more carefully.

I did, you should check your conclusions more carefuly before you jump into
something.



    ____________________________________________________________________
 
             Technology cannot make us other than what we are.

                                           James P. Hogan

       The Armadillo Group       ,::////;::-.          James Choate
       Austin, Tx               /:'///// ``::>/|/      ravage@ssz.com
       www.ssz.com            .',  ||||    `/( e\      512-451-7087
                           -====~~mm-'`-```-mm --'-
    --------------------------------------------------------------------