Addition Chains

[Pfoertner, Hugo]

-----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
--------------------------

A table of the lengths of the shortest possible addition chains in
compressed form for n<2^24, together with a small program for de-coding can
be found at Achim Flammenkamp's web page:
http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html
http://www.uni-bielefeld.de/~achim/add24.bits.gz

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 starts:

Comparison of lengths of addition chains produced by various methods

Binary method (OEIS A056792)
l(n) = log_2(n) + (number of bits in binary representation of n) - 1

Factor method (OEIS A064097):
l(1) = 0; l(n) = l(n-1)+1 if n is prime else l(k*j)=l(k)+l(j),
beats power tree only in very rare cases (6 for n<10^5):
19879 39758 43277 60749 79516 86554 121498 136199 159032 173069 173108

Knuth's power tree method (OEIS A114622):
never worse than binary method, loses by 1 against shortest chain for n=
 77 154 233 293 308 319 359 367 377 382 423 457 466 551 553 559 571 573 586
616 617 619 623 638 699 713 717 718 734 754 764 813 841 846 849 869 879 905
 914  932 1007 1051 1063 1069 1102 1103 1106 1115 1118 1133 1137 1142 1146
1147 1157 1172 1175 1181 1207 1213 1231 1232 1234 1237 1238 1246 1255 1265
1269 1276 1335 1357 1369 1385 1387 1393 1398 1399 1402 1415 1417 1421 1426
1434 1436 1465 1468 1481 1486 1508 1528 1593 1609 1626 1641 1659 1671 1673
1681 1682 1692 1698 1711 1738 1758 1787 1801 1810 1828 1864 1867 1869 1883
1897 1901 1915 1999 2011 2014 2027 2029 2033 2039 2063


Shortest possible addition chains (OEIS A003313).


Author: Hugo Pfoertner http://www.pfoertner.org/
Date of last change: Feb 1 2006
----------------------------------------------------------- 

    n  l_binary
    |  |  l_factor
    |  |  |  l_power_tree
    |  |  |  |  l_shortest
    |  |  |  |  |
    2  1  1  1  1
    3  2  2  2  2
    4  2  2  2  2
    5  3  3  3  3
    6  3  3  3  3
    7  4  4  4  4
    8  3  3  3  3
    9  4  4  4  4
   10  4  4  4  4
   11  5  5  5  5
   12  4  4  4  4
   13  5  5  5  5
   14  5  5  5  5
   15  6  5  5  5
   16  4  4  4  4
   17  5  5  5  5
   18  5  5  5  5
   19  6  6  6  6
   20  5  5  5  5
   21  6  6  6  6
   22  6  6  6  6
   23  7  7  6  6
   24  5  5  5  5
....
------------------------------

After yesterday's discussion on A064097, which is nothing else but the
factor method (this should be mentioned in its title) I looked again into
Knuth's treatment of the subject:

Citation from Knuth TAOCP Vol. 2, 3rd ed, page 464:
<<
The first case for which the factor method beats the power tree method is
n=19879=103*193; such cases are quite rare. (For n<=100000 the power tree
method is better than the factor method 88803 times; it ties 11191 times;
and it loses ony 6 times.)
>>

Since Knuth omits the values for which this happens I've computed them:

Numbers n such that the factor method described in A064097 produces a
shorter addition chain than Knuth's power tree method:

19879 39758 43277 60749 79516 86554 121498 136199 159032 173069 173108
183929 242996 252941 272398 318064 346138 346216 362861 367757 367858
453281 456017 485992 505882 544796 561727 579193 603167 636128 637969
692276 692432 725722 735514 735709 735716 772193 906562 912034 931297
963649 971984 1011764 1051727

In all cases shown, the chain produced by the factor method is also the
shortest possible one.

The following are the first occurrences, where the factor method beats
the power tree, but does not produce the shortest possible addition chain. 

      n       l_fact(n) l_powtr(n) l_best(n) 
   4789709        27        28        26
   6241007        28        29        27
   6731315        28        29        27
   6984291        28        29        27
   7860817        28        29        27
   8051873        28        29        27
  12482014        29        30        28
  13462630        29        30        28
  13968582        29        30        28
  16103746        29        30        28
  23216141        29        30        28

I'll try to submit the corresponding sequences during the next days.

Hugo Pfoertner