PAP --- Prime Arithmetric Progressions
                 ( The Search for Long PAPs )

Paul Pritchard                       pap@bibliocity.com

   Original Author and Overall Project Coordinator for the

Anthony Thyssen     1991 - 1993      Anthony.Thyssen@gmail.com

  Modularization of project source files.
  Development of an IPC (Inter-Process Communications) Distributed Server
  Major Optimization and Bug Fixes of the Workers programs.
  Complete overhaul of administration of pap servers and workers.
  The current central coordinator of the search.

Andrew Moran        1989 - 1990      andrew@cs.chalmers.se

   Distributed development of Worker programs under an NFS file system
   Conversion to C. Some Optimization.


Project
-------
   We are using a distributed set of processes (Workers) to search the
numerical address space for PAPs -- Prime Arithmetic Progressions, or in
other words a sequence of prime numbers seperated by a constant amount
from each other. A n-PAP is a sequence of n such primes.

Example :-    6-PAP : First Term 7  Difference between terms 30
                         or     7  37  67  97  127  157

  The longest such sequence known is 21 primes in length and was first
found in a similar distributed process on the 30 or so workstations at
University of Queensland, late 1990. That particular run was not a
complete search of the search area as the goal at that time was to find
one such 21-PAP.

 length = 21,  first term = 142072321123    last term = 28537332814723
       common difference between terms = 1419763024680

  Since this discovery a new search was performed to find the 21-PAP that
has the smallest last term (see below). The search used approximately 20
workstations, 10 at the Griffith University, and 10 at the University of
Bergen, Norway!

 length = 21,  first term = 5749146449311   last term = 6269243827111
        common difference between terms = 26004868890

At the end of this search, a total of three 21-PAPs and 40 20-PAPs are
known.  However so far no PAP longer than 21 has been found.

The current (1991) search (the third since the project began) is to
locate any 22-PAP.  Success - March 1993!


Why Bother with PAPs
--------------------
   PAPs are of intellectual interest in mathematics.  They do not at this
time have a use, but if any use is to be found for this information it
would probably be in data encryption.

The search for PAPs provide a context for research in the areas of:

     Algorithms:
       Searching a near impossible domain of numbers in a reasonable
       time.  This search applies 5 different search techniques all at the
       same time. Some are new ideas. The programs check point scheme is
       particularly simple and effective.

     Distributed Computing:
       A fairly simple distributed example of using large numbers of
       workstations in parallel such that each workstation works
       completely independently on the results of the others. The number
       of machines does not matter nor whether machines are busy or down.
       Even the daemon servers are completely independent.

     Robustness:
       Check pointing and complete survival of the program from any
       machine crash. Without resorting to the requirement of root access
       to the machine (ie. all software runs completely in the user
       domain). That is to say that the program is completely user
       oriented with little or no machine dependence.

     Cray versus Workstations:
       The algorithm outperforms a Cray computer in the number of MIPs
       obtained, using only the wasted idle time of desktop workstations.

     Using Wasted Idle:
       Only the 'idle' time of the workstations is used. The program is
       small enough not to require much disk swapping and is given such a
       low priority (15) that it basically will not run when any other
       program is running. Only the normally wasted idle time of the
       machines is used. Idle time is a highly underestimated computing
       resource.


Method
------
   The Search for PAPs is performed by collection of worker programs each
running independently of each other. The 'Job' each worker performs is
collected from one of a number of IPC job servers.
   The location of these servers is gathered by a new worker on initial
startup by contacting a default server. This server's network address is
built in. After this worker's contact one of a number of server's known to
exist.
   The actual search code itself involves 6 search algorithms, one of
which is a new method of multiple searchs, all interwoven together.

  The PAPWorker programs are designed to :-
    + work completely independently of other worker programs
    + run one to a processor (ie. on a dual processor machine 2 workers
         would run)
    + use only the processor idle time (wasted cpu cyles)
         by running at a very low priority (15)
    + be fairly small to allow the swap-out of most of the code.
        (Currently memory size is 512Kbytes, but 200Kbytes in real memory)
    + check point the current job to two files every few search loops
       (approximately every 30 mins on a Sun SLC)

ASIDE:   Job  : a range of the search space to search (5000 numbers)
         Work : A group of Jobs.