Conference rusure::math

    This routine is not correct.  It's results are not even close to
    being correct, I thought that you had mentioned this in the
    aforementioned conference?
    
    The big problem with it is its strange use of the variable PRIME
    when it should be using 'I' instead.  The program can be easily
    fixed by replacing
    			PRIME:=I+I+3;
    		with
    			PRIME:=I;
    					and starting the loops at I:=2
    instead of I:=1.  After this it is a pretty standard forward checking
    sieve of erastothones program, with out list reduction optimizations.
    
    -- Barry

Well, since you read LANGUAGES, then you know that if you look at the
values of the variable PRIME (and *not* the values of FLAGS[]), then the
program works correctly, except for deciding that 9 is a prime.  (Well, if
there are any other bugs in it, I don't know what they are).

Do you know of any other composite numbers that PRIME takes on the value
of, or any primes that the program misses?

I agree that changing the I+I+3 to I results in the traditional algorithm.
I had not noticed that.  However, the program in .0 is so weird, and yet
apparently so close to correct, that I'd like people to look at *it* a
little bit more.
				/AHM/THX

    You are right Alan, I was assuming that, for instance, because it
    said that it was "casting out" 11 that it had erred, and I failed
    to notice that in fact, 11 was later listed as a prime.
    
    But I have solved the mystery of this program.  It seems that FLAGS
    is only being used to flag the ODD integers!  This is what the I+I+3
    transformation is all about.  By a whole lot of unstated symmetry
    of factoring priciples, this routine works out correctly except
    for 3 mistakes:
    	1)	It does not identify 2 as a prime.  This could be easily
    	     corrected with a write staement in the beginning.
    	2)	It does not identify 3 as a prime.  This is because
    	     I:=1 is to high, PRIME:=5 in this case.  Starting I:=0
    	     will solve this problem.
    	3)	It incorrectly identifies 9 as a prime.  This is a direct
    	     consequence of (2), and will be solved at the same time.
    
    Of course it thought 9 was prime because 9 has no other factors
    except 3, and thus was unFLAGed.  Thereafter, all other numbers
    with on 3 as a factor would have been FLAGged a being factors of
    9.
    
    Programs like this are why God made documentation, and serve to
    emphasize why using a good structured language like pascal is no
    guarantee of a good program.
    
    -- Barry

Non-prime odd numbers are

	x * y, where x and y are odd, say

	x = 2 * m + 1
	y = 2 * n + 1

They are kicked out by

	i = m - 1
	prime = 2 * i + 3
	k = i + n * prime

because

	2 * k + 3 = 2 * i  +  2 * n * prime  +  3
		  = 2 * i  +  4 * n * i  + 6 * n  +  3
		  = (2 * n + 1)  *  (2 * i + 3)
		  = (2 * n + 1)  *  (2 * m + 1)
		  = x * y

(because when it's k's turn to try to be i, flags [k] is false.)

Note that the bugs mentioned in .3 are evident:

	2  isn't odd
	3  isn't treated as (2 * 0 + 3)
	9  needs (m = 1) and (i = 0)

John

Re .3:

Sorry about the misleading "Casting out".  That piece of inadvertant
misdirection was my doing, not the author's.


I'll have to go absorb .3 and .4 off-line, but thanks for the effort.
				/AHM/THX

This works: (from ERATOFOR.FOR)

	INTEGER COUNT,PRIME,primes(3000)
	LOGICAL*1 FLAGS(0:10000)
	LIMIT=10000
	WRITE (6,998)
998	FORMAT(' ERATO start in FORTRAN')
	CALL LIB$INIT_TIMER()
	DO 250 J=1,10
	COUNT=1
        primes(1)=2
	DO 140 I=0,LIMIT
140	FLAGS(I)=.TRUE.
	DO 240 I=0,LIMIT
	IF (.NOT.FLAGS(I)) GOTO 240
	PRIME=I+I+3
	K=I+PRIME
190	IF (K.GT.LIMIT) GOTO 230
	FLAGS(K)=.FALSE.
	K=K+PRIME
	GOTO 190
230	COUNT=COUNT+1
        primes(count)=prime
240	CONTINUE
250	CONTINUE
	CALL LIB$SHOW_TIMER()
	WRITE (6,999) COUNT
999	FORMAT(' ',I11,' primes')
        write(6,*) (primes(i),i=1,20)
	END

But what are the FLAGs doing if they do not flag prime numbers as in the
traditional Eratosthenes' sieve? They seem to be a curious lot.

= Giles =

	The flags do flag prime numbers:

		FLAGS(k) is true <==> 2 * k + 3 is prime


	John