Ivo D�ntsch
Rechenzentrum &
Institut f�r semantische Informationsverarbeitung
Universit„t Osnabr�ck
40976 Osnabr�ck
Germany

Bitnet:   duentsch@dosuni1
Internet: duentsch@dosuni1.rz.uni-osnabrueck.de

Date: April 20, 1994


                                Aliquot


      Summary:

      Aliquot is a tool to compute aliquot chains with small starting
      numbers and keep a record of the results. It works on any PC with
      DOS 2.0 or greater.
      _________________________________________________________________

      Definitions:

      For a positive natural number n > 1, s(n) denotes the sum of its
      proper divisors. The sequence obtained by iterating s for some
      n is called an aliquot sequence or, sometimes, a chain.
      Various things can happen:

          1.  The sequence is constant from some point onwards;
              the constant term will be 1 or a perfect number.

          2.  The sequence becomes periodic with period > 1 by moving
              into a ring of amicable numbers.

          3.  It is an open problem whether an aliquot sequence can have
              infinitely many different terms.

      The target of an aliquot sequence is a member which is either
      a perfect number or a prime or the smallest member of an amicable
      ring.

      A record file consists of 32 bit long integers. Record n contains
      the target of n if it has been found, 0 if the sequence starting
      with n has not been resolved, -1 if n has not yet been looked at.
      The record file is, in a way, a skeleton for results to be written
      into. It is initialized with record 0 = number of records, record
      1 = last number processed, and all other entries set to -1.
      __________________________________________________________________

      Algorithm:

      The program uses Pollard-Brent factoring, the pseudorandom poly-
      nomial being x^2 + s, where s is the shift.
      __________________________________________________________________

      Options:

      [a]    Computes an aliquot chain; the result can be written to a
             text file. Press <esc> to quit during a long calculation.

      [c]    Given a record file, the option counts all occurrences of a
             target within a specified range.

      [e]    Extends the number of records of a record file.

      [f]    Finds a number and its target.

             (Enter 0 to find the largest possible number of records
             for this file, enter 1 to find the largest processed starting
             number.)

      [h]    A short help screen.

      [p]    Several parameters can be changed:

             The starting value and shift of the polynomial,

             The maximum number of shifts to do before aborting in
             option [r],

             The start of numbering (0 or 1) in option [a],

             When a partial chain is first saved in [c] and in which
             intervals; the filename will be the first 8 digits of the
             starting number.

      [q]    Quit the program.

      [r]    Create or fill in a record file systematically.

      [u]    Update a record file with a chain; the program needs a text
             file created with ALIQUOT, NUMBERS or a generic file of the
             following form:

                1. The first line contains the target.
                2. The following lines contain the numbers to which the
                   target is to be added.
                3. Blank lines or lines starting with # are ignored.

                Example: A file starting with the lines

                601
                840
                2040
                4440
                9240

                will cause the target 601 to be added to 840, 2040,
                4440, 9240.

      [s]    Counts the number of occurences of all targets in a specified
             range. Primes are not included, e.g. 7 is not included
             among all numbers with target 7. At present, the program
             can do the statistics for at most 10,000 different targets.
             This is sufficient for a range 1 - 300,000. The procedure
             can also output a list of primes in the chosen range which
             do not appear as targets.

      [t]    Finds all numbers with a given target in a specified range.
             The output can be written to a file.

      [x]    Extracts a specified range of a record file to text.


      __________________________________________________________________

      Limitations:

      The record file can only contain Turbo Pascals LongInts. Thus,
      targets greater than TP's maxint are not recorded.

      Input checking is hardly performed. Please report any errors.

      __________________________________________________________________

      Known bugs:

      Sometimes the program will try to write past the end of the chain
      file and terminate with an error message. I have not been able to
      find or systematically reproduce the error.

      __________________________________________________________________

      Included is a record file chain.rec with starters up to 300,000;
      the targets have been obtained by running the Pollard Rho
      algorithm on f(x) = x^2 + s with 1 <= s <= 5 and start value x_0 = 3.
      15% of the numbers have not yet been resolved. Please let me
      know if you find any new entries.

      __________________________________________________________________

      Contributions:

      J. Gerved (gerved@inet.uni-c.dk) has kindly supplied the chains
      with the starters 840,1248,1848,2580,2850,4488,4830,6792,7752,
      8262,8862,9540.

      The chains with starters 840 and 4488 were independently found by
      W. Creyaufm�ller.

      __________________________________________________________________


      Enjoy,

      Ivo.

      __________________________________________________________________

      Disclaimer:

        Extensive care has been taken to assure that the program runs
        properly; however, I disclaim all reliability to the user for
        any direct, indirect or consequential loss arising from the use
        of, or inability to use, this program.

        No warranty is given that the program will work under all
        circumstances, or that it does what it claims it does.

      __________________________________________________________________

      Licence:

      The program may be freely used for educational or research purposes.
      If you use its results in publications, I should appreciate if you
      included the following reference:

          Ivo D�ntsch, "Aliquot - a utility to compute aliquot chains",
          Universit„t Osnabr�ck (1992)

      __________________________________________________________________


      Changes:

      Jul 06, 1992:  Fixed a bug which in rare circumstances might cause
                     the computer to hang.

      Sep 14, 1992:  Added the utilities [s], included updated record file.

      Jan 04, 1993:  Included updated record file.

      Oct 06, 1993:  Included ability to read generic chain files.
                     Removed some minor inconsistencies.
                     Included updated record file.

      Jan 21, 1994:  Removed a memory problem in the [s] option.
                     Added negative list of primes to [s].
                     Added option [t].

      Apr 20, 1994:  Added chains to chain.rec supplied by J. Gerved and
                     W. Creyaufm�ller