Application of the algorithm known as "Sieve of Erastothenes (276-194BC)" yields two
indicators not described in the literature. Firstly, when a prime number is
recognized and its multiples are sieved out (eliminated from the ordering of mumbers)
, then the NEXT number in ordering is always a prime. Secondly, once a prime is
identified and its multiples sieved out, the "first to go" is the square of this very prime
. (See hyperlinks at Website: toteenmathpaj.htm . Or
initiated, in particular, at sievesetup.htm. For interactive display, see
http://www.faust.fr.bw.schule.de/mhb/erastosiv.htm.)
The secondly cited indicator is the
basis of another algorithm: In testing a number for factors, you need only
test for those primes less than the approximate square root of the candidate number. This
is known in the literature, but apparently not mentioned in conection with Erastothenes' Sieve.
Definition: Let the maximal prime by current state-of-t
he-art be labeled the sotaprime and denoted Dd where d
denotes a date [such as 11/12/02, for D11/12/02]. Obviously, Lemma: The
sotaprime is a cut in the ordering of numbers and primes, bifurcating these
into presotaprimes (less than sotaprime) and postsotaprimes (greater than sotaprime.)
Our result follows. Prime Number Algorithm: Presotaprimes allow
sieving of their multiples in the ordering above the sotaprime; the sotaprime allows sieving of
its multiples in the ordering above the sotaprime; then the first postsotaprime is a previously
unrecognized prime number. Proof: This follows from a special case of Euler's totient
function, f(), which requires defining
coprimality: Two numbers are coprime (relatively prime) iff
their only common factor is 1. Totient: Given prime
number p, the numerosity of numbers less than
and coprime to p is given as
f(p) = p(1 - 1/p) = p - 1. But these are all sieved out
between p and the prime preceding it in the presotaprimes;
and sieving applies also to the first postsotaprime, namely, p2
, as well as all multiples of p in the ordering
above p2; this leaves only a "new" prime as the current
first postsotaprime. (A simple computation suffices, preceeded by a one-step
preliminary computation, using, say, the Fast Fourier Transform, to compute the
square of the sotaprime. In the (main) computation, only two numbers need to be
computed, and only three simple types of computing are needed: first, recursion of all
integers beyond sotaprime up to sotaprime-square, for a test-sequence, which
can be sieved into a minipostsotaprime sequence; second, modularly setting to zero all
sotaprime multiples including the prime itself, a very short process. A list of all known
primes is ONLINE or can be arranged. Maximal known prime becomes sotaprime for program and
a loop creates number sequence above it up to some finite bound. By hyperlink, all primes stream
through a program loop nulling all non-postsotaprimes up to sostaprimesquare. Then print the
sotaprime and its successor, a new prime. (Can you think of a Corollary?) In the literature, the
E. sieve is a nonprime eliminator; by the p. n. algorithm, E. s. is a prime-pointer
: sotaprime 
newprime. See (below) primal run,
primal run distribution, primal run gap conjecture, primal run log conjecture. (The public
key encription algorithm labeled RSA encription uses prime factorization as the
trapdoor one-way function).
PRIMAL RUN
Upon any application of the Erastothenes sieve algorithm for p, the run of
consecutive primes, beginning with 2, up to the first composite
encountered. See primal run distribution, primal run gap conjecture, primal run log
conjecture, prime number algorithm.
PRIMAL RUN DISTRIBUTION
With any application of the Erastothenes sieve algorithm for p,
the run of consecutive primes, beginning with 2 , is up to
the square of the next prime just beyond p. This is an
extension of the pattern that, upon sieving the multiples of p, the
first number sieved is p2. Using the largest currently
known prime (the sotaprime, see prime number algorithm, a sotaprimalrun
can be computed. (An advantage might accrue from relating primal run to asymptiotic distribution
of primes and gap between primes: what is newly learned about one may suggest investigate in the
others.)
PRIMAL RUN LOG CONJECTURE
The primal run is connected to the logarithmic distribution of primes described
in the asymptotic prime number theorem).