Shortest Addition Chains  for  1 <= n <= 1024.


The database has been compiled by David Wilson (davidwwilson(AT)comcast.net) and discussed on the seqfan mailing list, which is related to OEIS. I have added a little html to help browsing.


An addition chain for n is a finite increasing sequence of positive integers whose first element is 1, last element is n, and every element after the first is the sum of two previous elements in the chain. For example:

  (1 2 4 5 8 10 13)
is an addition chain for 13.

A shortest addition chain for n is an addition chain for n with the smallest possible number of elements.  For example,

  (1 2 3 6 12 13)

is a shortest addition chain for 13, since there is no addition chain for 13 with fewer than 6 elements.

A Brauer chain is an addition chain in which every member after the first is the sum of the immediately preceeding element and a previous element (possibly the same element).  For example,

  (1 2 3 6 7 13)
is a Brauer chain for 13.

A non-Brauer chain for n is an addition chain for n which is not a Brauer chain.  For example

  (1 2 4 5 8 13)
is a non-Brauer chain for 13.

The Database

The database can be downloaded as a single zip file ac.zip (size 5.5Mb) which contains the files acRead.txt (more or less this file), acIndx.txt (summary statistics) and the 1024 files named acNNNN.txt (with NNNN ranging from 0001 to 1024). Each acNNNN.txt file contains the actual chains for the given n=NNNN.  The format of these files is described below.

The single uncompressed acNNNN.txt files can  be browsed  following  these links:

001-032
033-064
065-096
097-128
129-160
161-192
193-224
225-256
257-288
289-320
321-352
353-384
384-416
417-448
449-480
481-512
513-544
545-576
577-608
609-640
641-672
673-704
705-736
737-768
769-800
800-832
833-864
865-896
897-928
929-960
961-992
993-1024

The file acIndx.txt includes summary statistics for the shortest addition chains for n.  It can be viewed also as a big table in this separate page. The lines are sorted on n, and have the format

    n siz act bct cct

where

    n   = last element of addition chain
    siz = number of elements in shortest addition chain for n
    act = number of non-Brauer shortest addition chains for n
    bct = number of Brauer shortest addition chains for n
    cct = act+bct = total number of shortest addition chains for n

The file ac****.txt, where **** is a zero-padded number n, records all shortest addition chains for n.  For example, ac0137.txt records all shortest addition chains for n = 137.  Each line describes one of the shortest addition chains for n.  Lines are sorted in lexicographic order on the chain elements.  The format of each line is

  a_1 = first element of chain
  a_2 = second element of chain
  a_3 = third element of chain
    ...
    a_siz = last element of chain
    type = a for non-Brauer chain, b for Brauer chain

Back to www.numbersaplenty.com