The database has been compiled by
David Wilson
(davidwwilson(AT)comcast.net) and discussed on the seqfanmailing 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:
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