Addition Chains

[Hugo Pfoertner]

"Pfoertner, Hugo" schrieb:
> 
> -----Original Message-----
> From: franktaw at netscape.net [mailto:franktaw at netscape.net]
> Sent: Tuesday, January 31, 2006 17:46
> To: seqfan at ext.jussieu.fr
> Subject: Addition Chains
> 
> There should really be a link from the main addition chain sequences to
> somewhere on the net with a list of l(n) at least up to 1000 or so.
> Preferably with minimum Brauer chain, power tree, factor, and binary methods
> for comparison.  I did a quick search, and couldn't find anything like that.
> 
> First option, does anyone know of an existing web site with this kind of
> information?
> 
> Second option, can someone set one up?
> 
> Franklin T. Adams-Watters
> 16 W. Michigan Ave.
> Palatine, IL 60067
> 847-776-7645
---------------------
> But that's probably not what you had in mind. I created
> http://www.randomwalk.de/sequences/addchains.txt , but would prefer to have
> that stored somewhere near the OEIS, after including any improvements or
> comments.

The table can now be found at
http://www.research.att.com/~njas/sequences/a003313.txt
and is linked from http://www.research.att.com/~njas/sequences/A003313
and some other sequences.

Using a slightly modified version of the program achain-all from Donald
Knuth's
http://www-cs-faculty.stanford.edu/~knuth/programs.html
http://www-cs-faculty.stanford.edu/~knuth/programs/achain-all.w
plus Neill Clift's converted length data

the addchains.txt table has been amendend by one example of a shortest
addition chain for every n (usually more than 1 exist). I don't know
which of the tables would be more useful for inclusion into the OEIS.

The updated table starts

    n  l_binary
    |  |  l_factor
    |  |  |  l_power_tree
    |  |  |  |  l_shortest
    |  |  |  |  |      Example of a shortest chain
    |  |  |  |  |      omitting n and constant 2,1 at start
    2  1  1  1  1                   [ 2 1 ]
    3  2  2  2  2                   [ 3 2 1 ]
    4  2  2  2  2                   [ 4 2 1 ]
    5  3  3  3  3       4 short for [ 5 4 2 1 ]
    6  3  3  3  3       3           [ 6 3 2 1 ]
    7  4  4  4  4       6  3        [ 7 6 3 2 1 ]
    8  3  3  3  3       4
    9  4  4  4  4       6  3
   10  4  4  4  4       5  4
   11  5  5  5  5       8  4  3
   12  4  4  4  4       6  3
   13  5  5  5  5      10  5  3
   14  5  5  5  5       7  6  3
   15  6  5  5  5      10  5  4
   16  4  4  4  4       8  4
   17  5  5  5  5      16  8  4
   18  5  5  5  5       9  6  3
   19  6  6  6  6      14  7  5  4
   20  5  5  5  5      10  5  4
   21  6  6  6  6      14  7  6  3
   22  6  6  6  6      11  8  4  3
   23  7  7  6  6      18  9  5  4
   24  5  5  5  5      12  6  3
   25  6  6  6  6      20 10  5  4

......

 2045 19 14 14 14      1630  815  415  400 200 100  50  25  15  10  5  4
 2046 19 15 14 14      1023  682  341  260 130  81  49  48  32  16  8  4
 2047 20 16 15 15      1366  683  681  454 227 162  81  65  64  32 16 
8  4
 2048 11 11 11 11      1024  512  256  128  64  32  16   8   4
 2267 17 16 15 14      1810  905  457  448 224 112  56  28  14   9  5  4
 2391 17 16 15 14      2068 1034  517  323 194 129  65  64  32  16  8  4
 2413 17 16 15 14      2316 1158  579  386 193  97  96  48  24  12  6  3

.......

 4945 17 18 16 15      4624 2312 1156  578 321 257 256 128  64  32 16 
8  4
 4962 17 18 16 15      2481 2320 1160  580 290 161 129 128  64  32 16 
8  4
 4971 19 17 16 15      4648 2324 1162  581 323 258 129  65  64  32 16 
8  4

and can be found at

http://www.randomwalk.de/sequences/addchains.txt

It would also be possible to give the terms of the chains in ascending
order. Can I get some advice which is the preferred order?

Hugo Pfoertner