Conference rusure::math

    678
    
    Eugene

        re .1
        
>>      678
        
        No.  First hint follows the formfeed:
        
        All elements of the sequence are prime.
        
        Dan

    ... something to do with spirals?

	No, not 17.  I know of no connection with spirals.

	Hint #2:



	No one has any idea whether the sequence contains all of
	the primes.

	Dan

	I believe that the next two values are:

5 and 6221671

	What is most interesting about this puzzle is that it's such
a famous algorithm, but yet it never occured to me to actually compute
what the real values are, before this.

        Correct!  Does anyone care to try for the next element
        after those two?  The final hint is:
        
        Although no two elements of the sequence are identical,
        there will always be a next element, and so the sequence
        is infinite.
        
        Dan

    1106.7
    
    Eugene

	(2*3)+1=7
	(2*3*7)+1=43
	(2*3*7*43)+1=1807	1807=13*139

	Proof of the existence of infinitely many primes.
				HRM

        Yes, .5 (Andrew) and .8 (HRM) got it.  Each element is
        the smallest integer greater than one (and therefore the
        smallest prime) that divides one more than the product of
        all of the previous elements.  I think it was Euclid who
        first showed in this way that there would always be
        another prime.
        
		2 3 7 43 13 53 5 6221671 38709183810571
        
        I wonder if anyone has ever investigated this sequence. 
        Do you think 11 ever shows up?  Do you think every prime
        eventually shows up?  How many times? :-)  The next two
        one-plus-products after 5 are both prime.
        
        Dan

re .8
>	Proof of the existence of infinitely many primes.
	
    ???
    
    Eugene

	re .10

>>	???

	Take all the primes so far, multiply them together, and add
	one.  It won't be divisible by any of the primes you started
	with.  So if not prime itself, any prime dividing it is a new
	one.  So you can generate infinitely many primes this way,
	one at a time.

	Dan

    re .8 .11
    
    Now I see, but I didn't see .8 multiplying all the prime though.
    
    Eugene

    
    I challenge the statement "so you can generate infinitely many primes
    this way".
    
    The proof in .11 shows existence of infinite primes, but unfortunately
    it does *not* say how to generate any of them !
    
    /Eric

>> .11	Take all the primes so far, multiply them together, and add
>>	one.  It won't be divisible by any of the primes you started
>>	with.  So if not prime itself, any prime dividing it is a new
>>	one.  So you can generate infinitely many primes this way,
>>	one at a time.

>> .13  The proof in .11 shows existence of infinite primes, but unfortunately
>>      it does *not* say how to generate any of them !
        
        Start with two.  At each step take as the next prime the
        smallest integer greater than one that divides one plus
        the product of the primes generated so far.  This will
        generate an infinite list of primes. .11 did not make
        explicit *which* prime divisor of one more than the product
        to use.
        
        Dan
        
        P = {2};
        forever {
            N = 1 + product_of_elements_of(P);
            for (k = 2 ; N % k != 0 ; k++);
            P = P union {k};
        }
        

    Just to make this a little bit clearer (or maybe less :-)...
    
    Dan describes how to generate an infinite number of primes
    *algorithimically*, of which there have been many known ways to do this
    for a very long time (at least since Erastothones(sp?)).
    
    It is *not* a way to functionally generate an infinite number of
    primes, which it has been proven (I think) that there MUST be a way,
    but no one has found it yet.
    
    So Dan was describing was not an inadvertent claim to having solved one
    of the oldest popular number theory problems. (Which I think is what
    .13 was objecting to in principle).
    
    --  Barry

	I disagree.  Both earlier replies specify a way to generate
	an infinite sequence of primes.  The first version is
	nondeterministic because it does not specify which prime
	factor to choose.  The second version is determistic, it
	specifies that the smallest nontrivial factor be used.

	Dan

    Perhaps I was not clear.
    
    An Algorthimic method is like this:
    
    	"Follow this procedure to generate primes ..."
    
    Whereas a Functional (or Expressive?) method is like this:
    
    	"The infinite series P(n) is always prime for any positive integer
    	'n'.  P(n) is an expressible mathmatical function, calulable
    	in O(1) time."
    
    We know lots of ways to do the first.  We do not know of any way to do
    the second, though it has been shown that there must exist some
    (mixed?) polynomial finction that can generate unique primes.

>    the second, though it has been shown that there must exist some
>    (mixed?) polynomial finction that can generate unique primes.
    
    Would you quote the theorem you're referring to here? I have a problem
    believing the obvious interpretation of the above.
    
      John

        Every recursively enumerable relation over the
        nonnegative integers can be expressed in the form:
        
          P(x1,...,xn) if and only if there exist y1,...,yk
          such that p(x1,...,xn,y1,...,yk) = q(x1,...,xn,y1,...,yk)
          where p and q are built up from the specified variables
          and 0 using plus, times, and the successor function.
          [i.e., p and q are terms in the first order theory of
          arithmetic]
        
        Replacing S(0) with 1, S(1) with 2, ..., and S(x) with x+1,
        etc., you can write p and q as polynomials with
        nonnegative integer coefficients.  So p-q is a polynomial
        with integral coefficients.  Call this polynomial f, and
        you get P(x1,...,xn) iff f(x1,...,xn,y1,...,yk) = 0 for
        some y1,...,yk.
        
        Now consider a polynomial g with integral coefficients
        such that x is prime iff g(x,y1,...,yk) = 0 for some
        y1,...,yk.  Then x - (x+1)(g(x,y1,...,yk)^2) will have
        its nonnegative values (for nonnegative integral
        x,y1,...,yk) be exactly the primes.
        
        The proof is constructive but the explicit polynomials
        generated aren't very useful for most practical purposes.
        
        Dan

RE: .18 (John)
    
    This is from memory, but I believe that it has been shown that there
    is a relatively simple function (transcendental, i.e., involving
    exp, log; but nevertheless simple) which, given "n" will return the
    n'th prime.
    
    The "trick" is that the function includes an irrational valued constant
    (call it P).  P is essentially an encoding of the sequence of primes,
    which the function simply decodes to provide the n'th prime.  In
    order to actually *use* the function you would have to first calculate
    that constant, and in order to do that you have to already know all the
    primes, so it is of no practical use at all.
    
    I may be misremembering but I believe that the same function -- with
    different constants -- can handle *any* increasing sequence of integers
    which doesn't grow too fast (no more than exponentially?)
    
    Anyway, once you have the form of the function in hand, the proof is
    pretty straightforward as I remember it.
    
    					Topher