Shortest Addition Chains
Introduction
A finite sequence of positive integers a_{0}, a_{1}, ..., a_{r} is called an addition chain iff for
each element a_{i}, but the first a_{0} which equals 1, there exist elements in the sequence with smaller indices j and k such that a_{i} = a_{j} + a_{k}.
Preciser this is called an addition chain of length r for its last number a_{r}. It can be interpreted like calculating n = a_{r}
starting from 1 by addition of only previous calculated numbers.
Let us restrict the definition a bit more: addition chains should be strictly
monotonic increasing.
This can be achived by reordering and dropping multiple numbers. As a consequence a_{1}=2 and a_{2}=3 or 4 always (as long as r > 1).
Now ask for the minimal length of an addition chain for a given number n and call this value l(n). If we demand that j or k equals i1 for all positive indices i  each a_{i} in the chain requires the previous a_{i1}, we call such a chain a starchain and denote its minimal length by l^{*}(n).
I highly recommand Knuth's survey in section 4.6.3 of The Art of Computer Programming, Volume 2: Seminumerical Algorithmus (3. edition appeared 1997).
To illustrate shortest addition chains for each n < 149
one may track the path from the root 1 to the corresponding node n in the following tree:
Such a tree can't be extended gapless to larger n because in the triple 43, 77, 149
any two numbers exclude the third for a shortest addition chain representation in a common tree.
Lower and Upper Bounds of l(n)
Write n in its binary representation and denote by v(n) the
number of ones in this representation and by λ(n) the binary logarithm of n rounded to the next integer down in the case it is not already integer (floorfunction).
Then it is obvious through construction of an addition chain according by the russian multiplication, that l(n) <=
λ(n) + v(n)  1. An open conjecture states a lower limit of λ(n) + log_{2}(v(n)).
Notation
Notice: The definitions of v(n) and λ(n) are given in the previous paragraph.
 s(n)
 the number of small steps of n defined as the difference of the length of its shortest addition chain and the binary logarithm (rounded down).
s(n) = l(n)λ(n)
 Double step
 a_{i} = a_{i1} + a_{i1}
 Star step
 a_{i} = a_{i1} + a_{j} with j < i
 Small step
 λ(a_{i}) = λ(a_{i1})
 Standard step
 a_{i} = a_{j} + a_{k} with i > j > k
 L(r)
 the set of numbers which have a shortest addition chain of length r
L(r) = { i: l(i)=r }
 c(r)
 the smallest number which has a shortest addition chain of length r
c(r) = min L(r)
 2^{r}
 the largest number which has an addition chain of length r
2^r = max L(r) holds trivally
 m(r)
 the median of numbers which have a shortest addition chain of length r
m(r) = med L(r)
 μ(r)
 the arithemtic average of numbers which have a shortest addition chain of length r
μ(r) = 1/d(r) ∑_{i ∈ L(r)} i
 g(r)
 the geometric average of numbers which have a shortest addition chain of length r
g(r) = exp( 1/d(r) ∑_{i ∈ L(r)} ln i )
 p(r)
 the "most probable" number which has a shortest addition chain of length r
p(r) = i: f_{r}(i) = max_{h} f_{r}(h) with f_{r}(i) = ∑_{k ∈ N} { j ∈ L(r): ij=k }/4^{k}
 σ(r)
 the standard deviation of the numbers which have a shortest addition chain of length r
σ^{2}(r) = 1/d(r) ∑_{i ∈ L(r)} i^{2}  μ(r)^{2}
 d(r)
 the number of numbers which have a shortest addition chain of length r
d(r) =  L(r) 
Table of Characterizing Values
r  c(r)  s(c(r))  v(c(r))  μ(r)  g(r)  m(r)  p(r)  σ(r)  d(r)  L(r) 

0  1  0  1  1.0  1.0  1=  1  0  1  {1} 
1  2  0  1  2.0  2.0  2=  2  0  1  {2} 
2  3  1  2  3.5  3.5  3+  3+  0.5  2  {3,4} 
3  5  1  2  6.3  6.2  6=  6  1.2  3  {5,6,8} 
4  7  2  3  10.8  10.4  10=  10  3.1  5  {7,9,10,12,16} 
5  11  2  3  18.2  17.3  17=  14  6.1  9  {11,13,14,15,17,18,20,24,32} 
6  19  2  3  31.7  30.1  28=  26  11.4  15  {19,21,22,23,25,26,27,28,30,33,34,36,40,48,64} 
7  29  3  4  54.5  51.3  49+  43  21.2  26 
8  47  3  5  94.6  88.5  84+  84  39.0  44 
9  71  3  4  162.4  151.0  147+  116  70.5  78 
10  127  4  7  283.1  262.8  248+  230  125.6  136 
11  191  4  7  491.5  456.1  435+  455  220.8  246 
12  379  4  7  869.8  809.4  781+  840  387.5  432 
13  607  4  7  1535.4  1429.4  1372+  1136  682.3  772 
14  1087  4  7  2725.8  2540.0  2461+  2028  1201.5  1382 
15  1903  5  9  4855.4  4527.9  4379=  4047  2122.4  2481 
16  3583  5  11  8672.1  8097.2  7813+  6832  3748.3  4490 
17  6271  5  9  15571.7  14570.0  14101+  12048  6611.3  8170 
18  11231  5  11  28094.6  26343.0  25641+  24096  11694.2  14866 
19  18287  5  10  50861.7  47784.4  46466+  48156  20748.0  27128 
20  34303  5  11  92379.2  86937.2  84764+  89120  36960.6  49544 
21  65131  6  12  168192.7  158468.7  154745=  146480  66224.1  90371 
22  110591  6  15  306531.6  289025.3  282128+  290858  119165.8  165432 
23  196591  6  16  559476.7  527913.7  514285=  520240  215048.9  303475 
24  357887  6  15  1023051.3  966288.1  942710=  1155126  388500.7  558275 
25  685951  6  15  1874869.1  1772876.3  1732716+  2310196  702737.4  1028508 
26  1176431  6  14  3443135.0  3259501.8  3191985+  2801503  1273563.8  1896704 
27  2211837  6  16  6333417.2  6001516.0  5881151=  5612462  2313684.8  3501029 
28  4169527  7  17  11667084.1  11064752.4  10848521+  9412704  4214352.7  6465774 
29  7624319  7  15  21516285.2  20418193.4  20044424+  16905070  7697737.3  11947258 
30  14143037  7  16  39714338.9  37704137.9  37013874=  41615456  14098404.4  22087489 
31  25450463  7  15  73345796.7  69658962.3  68327129+  83230816  25868797.8  40886910 
32  46444543  7  18  135563778.8  128804664.5  126581547+  132022368  47516034.6  75763102 
33  89209343  7  18  250780403.3  238406628.4  234114742=  284950635  87306216.3  140588339 
34  155691199  7  16  464437430.0  441801858.5  434295820+  397507456  160480247.6  261070184 
35  298695487  7  19  861008497.3  819556624.5  806226456+  680509066  295231415.9  485074788 
36  550040063  7  17  1597540092.5  1521468390.1  1497772469+  1511488768  543803959.0  901751654 
37  994660991  8  18       1677060520 
38  1886023151  8  19       3119775195 
39  3502562143  8  18       5804404206 
40  6490123999  8  21       10804952217 
41  11889505663  8  21       
42  22899028607  8  21       
43  41866170239  8  25       
In the median column the sign = means the value is unique and the character + indicates it lies between the
given index and the next index with this rvalue because d(r) is even.
With bold font in the previous c(r)column the sequence of smallest numbers n_{i} is highlighted which need at least i= s(c(r)) small steps in their addition chain:
1,3,7,29,127,1903,65131,4169527,994660991,....
Moreover here are the graphs of c(r) and d(r) together with an approximation function plotted.
And the quotient of c(r) and d(r) with the asymptotic approximation function.
Finally the distribution of the number of shortest addition chains with fixed small step number depending on the range of λ(n).
Generally Solved Small Step Cases
 0smallstep case
 Trivial
For each n >= 0 there is exactly 1 0smallstep number in the halfopen interval [2^n,2^(n+1)[ .
 list of all 0smallstep numbers:
2^n
 shortest chains for 0smallstep numbers:
0( ) 1
1( 0, D) @(A)
Here @(A) means 2^A with A a free nonnegative integer variable
 1smallstep case
 <= 1894 solved
 2smallstep case
 <= 1957 solved
 3smallstep case
 1991 solved
History: What was calculated When and by Whom
 l(i) with i <= 50 or v(i) <=4 , and d(r) with r <=6
calculated March 1957 by W. Hansen
 l(i) with i <= 2^{10} and d(r) with r <=11
reported December 1963 by D. E. Knuth
 l(i) with i < 2000 and d(r) with r <= 12
reported October 1968 by D. E. Knuth
 l(i) with i < 11232 and d(r) with r <= 15
calculated until May 1973 by D. E. Knuth
 l(i) with i < 120000 and c(r) with r <= 22
computed until August 1988 by Achim
 l(i) with i < 2^{17} and d(r) with r <= 20
computed April 1991 by Achim
 l(i) with i < 2^{18} and d(21) and c(23)
computed until October 1991 by Achim
 l(i) with i <= 500000 and c(24)
computed until November 1995 by D. Bleichensbacher
 l(i) with i <= 720000 including c(25)
computed until end of March 1997 by Achim.
 l(i) with i <= 2^{22} including c(28) and d(r) with r <= 25
computed until August 1997 by Achim.
 l(i) with i <= 2^{22} and d(25) and d(26)
computed until August 2004 by Neill Clift
 l(i) with i <= 2^{23} and d(27) and c(29) and c(30)
computed until September 2004 by Neill Clift
 l(i) with i <= 2^{24}
computed until December 2004 by Neill Clift
 c(31)
computed December 2005 by Neill Clift
 l(i) with i <= 2^{25}
computed until April 2006 by Neill Clift
 d(29), d(30) and c(32)
computed until June 2007 by Neill Clift
 l(2^{29}1) = 29 + l(29)  1
proved in December 2007 by Neill Clift
 l(i) with i <= 2^{26}
computed until May 2008 by Neill Clift
 d(31), d(32) and c(33)
computed until May 2008 by Neill Clift
 l(i) with i <= 2^{27} and l(i) with i <= 2^{28} and l(i) with i <= 2^{29}
computed in May 2008 by Neill Clift
 d(33), c(34) and c(35)
computed in May 2008 by Neill Clift
 l(2^{n}1) = n + l(n)  1, with n ∈ {31,33,...,46,48,49,50,51,52,54,56,60}
proved in May 2008 by Neill Clift
 c(36), d(34) and d(35)
computed June 2008 by Neill Clift
 c(37) and l(i) with i <= 2^{30}
computed until July 2008 by Neill Clift
 d(36)
computed in July 2008 by Neill Clift
 c(38)
computed in July 2008 by Neill Clift
 l(i) with i <= 2^{31}
computed until August 2008 by Neill Clift
 d(37)
computed in August 2008 by Neill Clift
 c(39)
computed in September 2008 by Neill Clift
 l(i) with i <= 2^{32}
computed until October 2008 by Neill Clift
 l(2^{n}1) = n + l(n)  1 with n ∈ {64,47}
proved in October 2008 by Neill Clift
 d(36), d(37) and d(38)
computed in November 2008 by Neill Clift
 l(2^{n}1) = n + l(n)  1 with n ∈ {53,55}
proved in November 2008 by Neill Clift
 l(2^{n}1) = n + l(n)  1 with n ∈ {57}
proved in December 2008 by Neill Clift
 l(2^{n}1) = n + l(n)  1 with n ∈ {58,59}
proved in January 2009 by Neill Clift
 l(2^{n}1) = n + l(n)  1 with n ∈ {61}
proved in February 2009 by Neill Clift
 l(2^{n}1) = n + l(n)  1 with n ∈ {62,63}
proved until May 2009 by Neill Clift
 c(40)
computed in September 2009 by Neill Clift
 l(i) with i <= 2^{33}
computed until October 2009 by Neill Clift
 c(41)
computed in November 2009 by Neill Clift
 l(i) with i <= 2^{34}
computed until December 2009 by Neill Clift
 c(42)
computed in May 2016 by Neill Clift
 l(2^{n}1) = n + l(n)  1 with n ∈ {65,66,68,72,80,96}
proved in May 2016 by Neill Clift
 l(i) with i <= 2^{35}
computed until May 2016 by Neill Clift
 d(39)
computed in May 2016 by Neill Clift
 d(40)
computed in May 2016 by Neill Clift
 c(43)
computed in September 2016 by Neill Clift
 l(i) with i <= 2^{36}
computed until October 2016 by Neill Clift

l(2^{n}1) = n + l(n)  1, if l(n) <= 8
computed in July 2018 by Neill Clift
In July 2004 the data calculated 1997 by Flammenkamp was completely and independently checked.
Hereby Neill Clift uncovered four l(n)errors, which he attributed to a typo
in Flammenkamp's program effecting only nvalues > 2500000.
On 30th May 2008, Neill Clift discovered the first and smallest n such that l(n) > l(2n).
Data Access
Thanks to Neill Clift's computations
you can download the lengths of all shortest additions chains for n up to n=2^{31}
as bziped2 binary data of 210 MB size. The uncompressed values are coded as l(n)λ(n)ceil(log_{2}(v(n))) into 2 bits each which the exception of l(2135101487) ^{#}.
To decipher this you can download ddt.c compile it and run it as ddt inputfile linelength.
You will get all values starting from 1 and broken into lines each
containing linelength values onto your stdout from the base36 alphabet (0,1,2,..,9,a,b,c,..,z) or as a 1 or 2 digit decimal value.
A second helper l.c outputs l(n), λ(n), s(n) and v(n) for each given input n which data is in the datafile.
Now you can download all l(n) with n <= 2^{33} as bziped2 binary data of 820 MB size.
To display these you must also download ddt4l.c, compile it and run it as ddt4l datafile [first n [total number [linelength] ] ].
You will get all or total numbermany values starting from 1 or first n and broken into lines each
containing linelength values onto your stdout from the base42 alphabet (0,1,2,..,9,a,b,c,..,z,A,B,C,..,F).
Now you can download all l(n) with n <= 2^{35} as bziped2 binary data of 3197 MB size.
To display these you must also download ddt4ln.c, compile it and run it as ddt4ln datafile [O?] [first n [total number [linelength] ] ].
You will get all or total numbermany values starting from 1 or first n and broken into lines (or pages) each
containing linelength values onto your stdout.
This ? after the O controls the output format and must take values ∈ {0,1,2,3,4}.
The default is 0 and means no output, but data integrity check only. Thus in generally you will need this outputoption.
The options O1 and O2 are the old formats known from ddt and ddtl4.The parameter O4 produces a format very similar to this of the above old helperprogram l.
Now you can download all l(n) with n <= 2^{36} as bziped2 binary data of 6397 MB size.
To display these you must also use ddt4ln.c like in the case of the 2^{35}many values.
Look up in the database of the first 2^{31} many l(n) values
The effort to compute these values up to n=2^{20} is here visible.
The number of cases checked to get l(n) is plotted in red against λ(n) for each number 2^{8} <= n < 2^{20}.
In blue the number of cases are marked to compute n=c(r) and finally in
dark green the average number of cases is drawn which is needed to calculate l(n)
for all numbers from 1 up to n (the last gives a good estimate of the average run time of the algorithm).
Generate a Shortest Addition Chain for any given number < 2^{27}
^{#} The smallest n such that l(n)λ(n)ceil(log_{2}(v(n))) equals 0,1,2,3,4,... are 1, 29, 3691, 919627, 2135101487, ... .
For every n with l(n) <=22
the number of shortest addition chains as a gziped ASCIIfile of 1.8 MB size, as a sorted by n list which consists of
three columns.
In each row of this list are given the values for the corresponding n, l(n) and number of shortest addition chains for this n.
Conjectures
 l(2^{n}1) <= n + l(n)  1
 The outstanding ScholzBrauerConjecture of 1937. If l(n) is achievable by a star chain then it holds. Therefore only values of n need to be considered with l(n) < l^{*}(n). But the smallest of these numbers is 12509.
In August 2005 Clift reported to have confirmed the ScholzBrauer inequality for all n < 5784689. ^{+}
 l(2^{n}1) = n + l(n)  1
 This narrow related equation is proved to hold at least for all n with l(n) <= 8 ^{*}.
 l(n) >= λ(n)+log_{2}(v(n))
 This famous lower bound was formulated first a bit differently by Stolarsky 1969 (p. 680, Lemma 10) and
nearly proved 1974 by Schönhage who showed that l(n) >= log_{2}(n)+log_{2}(v(n))2.123164629... holds for each n.
Thurber showed 1973 that it holds for all n with v(n) <= 16.
In October 2008 Clift confirmed the conjecture for all n <= 2^{64}.
 log_{2}(c(r)) ~ r  r/log_{2}r
 That is the 1997 stated conjecture by Flammenkamp for the asymptotic growth of c(r)
outdating the 1991 given assertation that log_{2}(c(r)) ~ r  2log_{2}r.
 Computing l(n) for given n is NPhard.
 Downey, Leony and Sethi didn't prove anything about this statement in their
1981 SIAM article. They proved a similar one, if a set of numbers is given!
Many people (and even experts) overlooked this important difference!
 d(r) <= d(r+1) <= 2d(r)
 Already 1981 D. Knuth stated "there is no evident way to prove that d(r) is an increasing function in r".
^{+}This number 5784689 = 2^{22}+97*2^{14}+65*2^{4}+97 is also the smallest NonHansen number (also identified by Neill Clift in 2005 as such).
^{*}In August 2005 Neill Clift reported to have proved equality without any further assumption for all n <= 28 and n = 30. Furthermore in December 2007 he showed equality without any further assumption even for n = 29. Moreover until May 2009 he proved it for all n <= 64 and in May 2016 for n ∈ {65,66,68,72,80,96}.
Lastly in July 2018 he proved the equality with a new groundbreaking algorithm to hold for all n with l(n) <= 8.
Unsorted new stuff
 An equivalent definition of addition chains based only on the settheoretic definition of natural numbers: additive complexity
 K. Stolarsky uses infinite addition chains in his 1969 appeared paper. Here are some basic remarks about minimal infinite addition chains.
 Is there a hiden connection between finite topologic spaces and addition chains? Look here.
References
 # H. Dellac
"Question 49",
L'Intermédiaire des Mathématiciens, V. 1
1894 p. 20.
 # E. de Jonquiéres
"Question 49 (H. Dellac)",
L'Intermédiaire des Mathématiciens V. 1
1894 20, pp 162164.
 # A. Goulard
"Question 393",
L'Intermédiaire des Mathématiciens V. 1
1894 p. 234.
 # E. de Jonquiéres
"Question 393 (A. Goulard)",
L'Intermédiaire des Mathématiciens V. 2
1895 pp 125126.
 # B. Datta and A.N. Singh
History of Hindu Mathematics V. 1
Bombay 1935, p. 76.
 # A. Scholz
"Aufgabe 253",
Jahresbericht der deutschen MathematikerVereingung V. 47, 2. Abteil.
1937 pp 4142.
 # A.T. Brauer
"On addition chains",
Bulletin of the American Mathematical Society V. 45
1939 pp 736739.
 # W.R. Utz
"A note on the ScholzBrauer problem in addition chains",
Proceedings of the American Mathematical Society, V. 4(3)
1953 pp 462463.
 # S.M. Hendley
"The theory and construction of addition chains",
Masters Thesis, University of South Carolina, 1954.
 # W. Hansen
"Untersuchungen über die ScholzBrauerschen Additionsketten und deren Verallgemeinerung",
Göttingen, Wiss. Prüfungsamt, Schriftl. Hausarbeit zum Staatsexamen 1957.
 # W. Hansen
"Zum ScholzBrauerschen Problem",
Journal für reine und angewandte Mathematik, V. 202
1959 pp 129136.
 # P.E. Valskii
"On the Lower Bounds of Multiplications in Evaluation of Powers",
Problems of Cybernetics, V. 2
1959 pp 7374.
 # P. Erdös
"Remarks on number theory. III: On addition chains",
Acta Arith. V. 6(1)
1960 pp 7781.
 # P.E. Valskii,
"The Smallest Number of Multiplications Necessary to Raise a Number to a Given Power",
Problems of Cybernetics V. 2
1961 pp 395397.
 # A.A. Gioia, M.V. Subbarao and M. Sugunamma
"The ScholzBrauer Problem in Addition Chains",
Duke Mathematical Journal, V. 29
1962 pp 481487.
 # R.E. Bellman
"Advanced problem 5125",
Amer. Math. Monthly, V. 70
1963 p. 765.
 # D.E. Knuth
"Addition chains and the evaluation of nth powers",
Notices of the American Mathematical Society, V. 11
1964 pp 230231.
 # E.G. Strauss
"Solution to Problem 5125",
Am. Math. Monthly, V. 71
1964 pp. 806808.
 # C.T. Whyburn
"A Note on Addition Chains",
Proceedings of the Am. Math. Society V. 16(5)
1965 p. 1134.
 # A.M. Il'in
"On Additive Number Chains",
Problemy Kibernet, V. 13
1965 pp 245248.
 # C.A. Demetriou
"Concerning minimal addition chains",
Thesis (Master Science),
University of Mississippi, 1967.
 # E. Wattel, G.A. Jensen
"Efficient calculation of powers in a semigroup",
Stichting Mathematisch Centrum. Zuivere Wiskunde,
Report ZW1968001 Mathematical Centre Amsterdam, V. 1 pp 118.
 # D.E. Knuth
The Art of Computer Programming V. 2
Seminumerical Algorithms, 1. edition,
AddisonWesly 1969 pp 449450.
 # D.E. Knuth
"Calculations on Addition chains",
Stanford University, California 1969.
 # K. B. Stolarsky
"A lower bound for the ScholzBrauer problem",
Canadian Journal of Mathematics, V. 21
1969 pp 675683.
 # H. Kato
"On Addition Chains",
Ph. D. Thesis,
University of Southern California, 1970.
 # E.G. Thurber
"The ScholzBrauer Problem for Addition Chains",
Ph.D. Thesis,
University of Southern California, 1971.
 # E. G. Thurber
"The ScholzBrauer Problem on Addition Chains",
Notices of the American Mathematical Society,
Abstract 71TA274, V. 18
1971 p. 1100.
 # R.P. Giese
"A Sequence of Counterexamples of Knuth's Modification of Utz's Conjecture",
Notices of the American Mathematical Society, Abstract 72TA257, V. 19
1972 p. A688.
 # A. Cottrell
"A Lower Bound for the ScholzBrauer Problem",
Notices of the American Mathematical Society, V. 20(5)
1973 p. A476.
 # E.G. Thurber
"The ScholzBrauer Problem on AdditionChains",
Pacific Journal of Mathematics, V. 49(1)
1973 p. 229242.
 # E.G. Thurber
"On addition chains l(mn) <= l(n)b And lower bounds for c(r)",
Duke Mathematical Journal, V. 40(4)
1973 p. 907913.
 # E. G. Thurber
"The ScholzBrauer Problem on Addition Chains",
Notices of the American Mathematical Society,
Abstract 73TA112, V. 20
1973 p. A318.
 # A. Cottrell
"A Lower Bound for the ScholzBrauer Problem",
Ph.D. Thesis,
University of California, Berkeley, 1974.
 # R.P. Giese
"Selected Topics in Addition Chains",
Ph.D. Thesis,
University of Houston, 1974.
 # K. R. Hebb
"Some Problems on Addition Chains",
Master Thesis,
University of Alberta, 1974.
 # K. R. Hebb
"Some results on addition chains",
Notices of the American Mathematical Society, V. 21(2)
1974 p. A294.
 # T.H. Southard
"Addition chains for the first n squares",
Report CNA84, Center for Numerical Analysis, University of Texas at Austin,
May 1974.
 # T.H. Southard
"Addition chains for the first n triangular numbers",
Report CNA85, Center for Numerical Analysis, University of Texas at Austin,
May 1974.
 # E. Vegh
"A Note on Addition Chains",
J. Comb. Theory, Ser. A, V. 19(1)
1975 pp 117118.
 # E. Vegh
"Addition Chains",
Notices of the American Mathematical Society, V. 22(1)
1975 pp A2A3.
 # A. Schönhage
"A Lower Bound for the Length of Addition Chains",
Theoretical Computer Science, V. 1(1)
1975 p. 112.
 # A.A. Gioia, M.V. Subbarao
"The ScholzBrauer Problem in Addition Chains",
Notices of the American Mathematical Society V. 22
1975 p. A63A64.
 # A.S. Saidan
The Arithmetic of alUqlîdisî
,
Dordrecht 1975 pp 341342
 # N. Pippenger
"On the Evaluation of Powers and Related Problems",
Proceedings, 19th Anual IEEE Symposium on the foundations of computer science,
Houston TX. 1976 pp 258263.
 # E.G. Thurber
"Addition chains and solutions of l(2n)=l(n) and l(2^n1)=n+l(n)1",
Discrete Mathematics, V. 16(3)
1976 pp 279289.
 # A.CC. Yao
"On the Evaluation of Powers",
SIAM J. Comput. V. 5(1)
1976 pp 100103.
 # E.G. Belaga
"The additive complexity of a natural number",
Soviet Mathematics Doklady V. 17(1)
1976 pp 59.
 # J. van Leeuwen
"An extension of {Hansen's} theorem for star chains",
J. Reine Angew. Math., V. 295
1977 pp 203207.
 # D.P. McCarthy
"The optimal algorithm to evaluate x^n using elementary multiplication methods",
Mathematics of Computation V. 31(137)
1977 pp 251256.
 # Rolf Sonntag
"Theorie der Additionsketten",
Diplomarbeit Technische Universität Hannover, 1978.
 # A.A. Gioia, M.V. Subbarao and M. Sugunamma
"The ScholzBrauer Problem in Addition Chains II",
Proc. Eighth Manitoba Conference on Numerical Math. and Computing, XXII V. 22
1978 pp 251274.
 # R.L. Graham and A.C.C. Yao and F.F. Yao
"Addition chains with multiplicative cost",
Discrete Mathematics, V. 23
1978 pp 115119
 # D. Dobkin, R. Lipton
"Additive chain methods for the evaluation of specific polynomials",
Proceedings of a Conference on Theoretical Computer Science (Univ.Waterloo, Waterloo, Ont., 1977),
Comput. Sci. Dept., Univ.Waterloo, Waterloo, Ont., V 148
1978 pp 146148.
 # N. Pippenger
"On the Evaluation of Powers and Monomials",
SIAM J. Computing, V. 9
1980 pp 230250.
 # D.E. Knuth
The Art of Computer Programming V. 2
Seminumerical Algorithms, 2. edition
AddisonWesly 1981 pp 441466.
 # D. Dobkin and R.J. Lipton
"Addition chain methods for the evaluation of specific polynomials",
SIAM Journal on Computing V. 9(1)
1980 pp 121125.
 # N. Pippenger
"On the evaluation of powers and monomials",
SIAM Journal on Computing V. 9(2)
1980 pp 230250.
 # P. Downey, B. Leony and R. Sethi
"Computing Sequences with Addition Chains",
SIAM Journal of Computing, V. 10(3)
1981 pp 638646.
 # J. Olivos
"On Vectorial Addition Chains",
Journal of Algorithms, V. 2(1)
1981 pp 1321.
 # D.E. Knuth, C.H. Papadimitriou
"Duality in addition chains",
Bulletin of the European Association for Theoretical Computer Science, V. 13
1981 pp 24.
 # I. Semba
"Systematic Method for Determining the Number of Multiplications Required to Compute x^m, where m is a Positive Integer",
Journal of Information Processing V. 6(1)
1983 pp 3133.
 # Y.H. Tsai
"A study on some addition chain problems",
Master Thesis, National TsingHua University, Hsinchu, Taiwan (6), 1985.
 # Y. H. Chin and Y. H. Tsai
"Algorithms for Finding the Shortest Addition Chain¨,
Proceedings of National Computer Symposium
Kaoshiung, Taiwan, December 2022, 1985 pp 13981414.
 # H. Volger
"Some Results on Addition/Subtraction Chains",
Inf. Process. Lett. V. 20(3)
1985 pp. 155160.
 # D.P. McCarthy
"Effect of improved multiplication efficiency on exponentiation algorithms derived from addition chains",
Mathematics of Computation, V. 46(174)
1986 pp 603608.
 # T. Lickteig and H. Volger
"Some Results on the Complexity of Powers",
Computation Theory and Logic , Editor Egon Börger
SpringerVerlag, 1987 pp 249255.
 # Y. H. Tsai, Y. H. Chin
"A study of some addition chain problems",
International Journal of Computer Mathematics, V. 22(2)
1987 pp 117134.
 # W. Orb
"Additionsketten",
Diploma Thesis, Mainz, University, 1987.
 # M. V. Subbarao
"Addition Chains  Some Results and Problems",
Number Theory and Applications, Editor R. A. Mollin,
NATO Advanced Science Institutes Series: Series C, V. 265
Kluwer Academic Publisher Group 1989 pp 555574.
 # F. Bergeron, J. Olivos
"Vectorial addition chains using Euclid's algorithm",
Research Report, Dept. Math., UQAM 105 (1989).
 # F. Bergeron, J. Berstel, S. Brlek, and C. Duboc
"Addition chains using continued fractions",
Journal Algorithms V. 10(3)
Sep. 1989 pp 403412.
 # F. Bergeron, J. Berstel, S. Brlek
"A unifying Approach to the generation of Addition Chains",
Proceedings of the XV LatinoAmerican Conference on Informatics,
1989 pp 1014.
 # J. Bos, M. Coster
"Addition Chain Heuristics",
Advances in Cryptolog, CRYPTO' 89
SpringerVerlag 1989 pp 400407.
 # M. Elias and F. Neri
"A Note on Addition Chains and Some Related Conjectures",
Sequences, Editor R. M. Capocelli,
SpringerVerlag 1990 pp 166181.
 # Y. Yacobi
"Exponentiating faster with addition chains",
Advances in Cryptology
EUROCRYPT '90, SpringerVerlag 1990 pp 222229.
 # F. Morain, J. Olivos
"Speeding up the computations on an elliptic curve using additionsubtraction chains",
ITA V. 24(6)
1990 pp 531544.
 # M.J. Coster
"Some algorithms on Addition Chains and their Complexity",
Tech. Report CSR9024,
Centrum voor Wiskunde en Informatica, Amsterdam, 1990 pp 169.
 # A. Flammenkamp
"Drei Beiträge zur diskreten Mathematik: Additionsketten, NoThreeinLineProblem, Sociable Numbers",
Diplomarbeit an der Fakultät für Mathematik, Universität Bielefeld 1991.
 # H. Zantema
"Minimizing Sums of Addition Chains",
Journal of Algorithms", V. 12(2)
1991 pp 281307.
 # S. Brlek, P. Castéran, R. Strandh
"On Addition Schemes",
TAPSOFT, V. 2
1991 pp 379393.
 # S. Brlek, P. Castéran, R. Strandh
"Chaînes d'addition et structures de contrôle",
Journées JFLA91 (2829 Janvier 1991, GresseenVercors, France) Bigre 72
1991 pp 5463.
 # Y.H. Chin, Y.H. Tsai
"On Addition Chains",
International Journal Computer Math, V. 45(34)
1992 pp 145160.
 # Y. H. Tsai and Y. H. Chin
"A Study of Addition Chain¨,
Proceedings of the National Science Council  Part A: Physical Science and Engineering,
V 16(6)
1992 pp. 506514.
 # J.N.E. Bos
"Practical Privacy",
PhD thesis, Eindhoven, University of Technology,
1992, ISBN 9061964059.
 # E.F. Brickell, D.M. Gordon, K.S. McCurley, D.B. Wilson
"Fast Exponentiation with Precomputation (Extended Abstract)",
EUROCRYPT 1992 pp 200207.
 # O.K. Gupta
"On Evaluation of Powers",
Journal of Information & Optimization Sciences, V. 13(2)
1992 pp 331336.
 # S. Brlek, R. Mallette
"Sur le calcul des chaînes d'additions optimales",
dans J. Labelle et J.G. Penaud, éditeurs,
Atelier de combinatoire francoquébecois (67 Mai 1991, Bordeaux, France)
Publ. du LACIM 10, 1992 ISBN 2892761018 pp 7185.
 # J. Sauerbrey and A. Dietel
"Resource requirements for the application of addition chains in modulo exponentiation",
Workshop on the Theory and Application of of Cryptographic Techniques
1992 pp 174182.
 # E. G. Thurber
"Addition chains  an eratic sequence",
Discrete Mathematics, V. 122
1993 pp 287305.
 # W. Aiello and M. V. Subbarao
"A conjecture in addition chains related to Scholz's conjecture",
Mathematics of Computation, V. 61(203)
1993 pp 1723.
 # M.J. Coster
"An algorithm on addition chains with restricted memory",
Research memorandum 603
Tilburg University, Department of Economics, 1993.
 # A.G. Dempster, M.D. Macleod
"Constant integer multiplication using minimum adders",
IEE Proceedings  Circuits, Devices & Systems, V. 141(5)
1994 pp 407413.
 # F. Bergeron, J. Berstel and S. Brlek
"Efficient Computation of Addition Chains",
Journal de Theorie des Nombres de Bordeaux, V. 6(1)
1994 pp 2138.
 # Y.J. Chen, C.C Chang, and W.P. Yang
"Some Properties of Vectorial Addition Chains",
International Journal of Computer Mathematics, V. 54(34)br>
1994 pp 185196.
 # Y.J. Chen
"Some Properties on Vectorial Addition Chains¨,
Ph.D. dissertation, Institute of Computer Science and Information Engineering, National Chiao Tung University,
Hsinchu, Taiwan, R.O.C., December 1994
 # P.J.N de Rooij
"Efficient exponentiation using precomputation and vector addition chains",
Workshop on the Theory and Application of of Cryptographic Techniques
EuroCrypt '94, 1994 pp 389399.
 # S.B. Gashkov and V.V. Kochergin
"On addition chains of vectors, gate circuits and the complexity of computations of powers",
Syberian Advances in Mathematics V. 4(4)
1994 pp 116.
 # V.V. Kochergin
"On the computation of powers sets",
Discrete Mathematics and Applications V. 4(2)
1994 pp 119128.
 # O. Kochergin
"The Evaluation of Powers",
Math. Problems of Cybernetics, V. 26
1995 pp 7682.
 # Y.J. Chen, C.C Chang, and W.P. Yang
"The Shortest Weighted Length Addition Chains",
Journal of Information Science and Engineering, V. 11(2)
1995 pp 295305.
 # S. Brlek, P. Castéran, L. Habsieger, R. Mallette
"Online evaluation of powers using Euclid's algorithm",
RAIRO, Inform. Theor. Appl. V. 29(5)
1995 pp 431450.
 # I.E. Bocharova, B.D. Kudryashov
"Fast exponentiation in cryptography",
Proceeding of AAECC11,
Lecture Notes in Computer Science, V. 948
Springer Verlag, 1995 pp 146157.
 # V. Dimitrov and T. Cooklev
"Two algorithms for modular exponentiation using nonstandard arithmetics",
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences V. 78(1)
The Institute of Electronics, Information and Communication Engineers
1995 pp 8287.
 # C. Ko`c
"Analysis of sliding window techniques for exponentiation",
Computers & Mathematics with Applications V. 30(10)
1995 pp 1724.
 # Y. Wu
"Strength reduction of multiplications by integer constants",
ACM SIGPLAN Notices V. 30(2)
1995 pp 4248.
 # C.Y. Chen, C.C. Chang, and W.P. Yang
"Hybrid Method for Modular Exponentiation with Precomputation",
Electronics Letters, V. 32(6)
1996 pp 540541.
 # D.C. Lou, and C.C. Chang
"Fast Exponentiation Method Obtained by Folding the Exponent in Half",
Electronics Letters, V. 32(11)
1996 pp 984985.
 # D. Bleichenbacher
"Efficiency and Security of Cryptosystems based on Number Theory",
Dissertation to Swiss Federal Institute of Technology Zürich, ETH Zürich 1996.
 # V.V. Kochergin
"On the complexity of computation of monomials and tuples of powers",
Siberian Advances in Math V. 6(1)
1996 pp 7186.
 # D. Bleichenbacher and A. Flammenkamp
"An Efficient Algorithm for Computing Shortest Addition Chains",
submitted 1997 to SIAM Journal of Discrete Mathematics
The same paper as gziped Postscript included all figures.
 # N. Kunihiro and H. Yamamoto
"Optimal addition chain classified by Hamming weight",
IEICE Technical Report, ISEC9674, 1997.
 # Bahig, H.M.,
"On the algorithms of computational number theory and their applications",
Master Thesis, Dept. of Math., Faculty of Science, Ain Shams University, Cairo, Egypt 1998.
 # G.D. Cohen, A. Lobstein, D. Naccache, G. Zémor
"How to Improve an Exponentiation BlackBox",
EUROCRYPT 1998 pp 211220.
 # D.M. Gordon
"A survey of fast exponentiation methods",
Journal of algorithms V. 27(1)
1998 pp 129146.
 # D.E> Knuth
"The Art of Computer Programming", V. 2
Seminumerical Algorithms, 3. edition,
Addision Wesley, Reading, MA 1998 pp 461485.
 # N. Kunihiro and H. Yamamoto
"Windows and Extended Window Methods for Addition Chain and AdditionSubtraction Chain",
IEICE Trans. on Fundamentals of Electronics, Comm. , V. 81(1) E83A
1998 pp 7281.
 # C.D. Walter
"Exponentiation Using Division Chains",
IEEE Trans. on Computers V. 47(7)
1998 pp 757765.
 # D. Lou, C. Chang
"An adaptive exponentiation method",
Journal Systems Software V 42(1)
1998 pp 5969.
 # Y. Yacobi
"Fast Exponentiation Using Data Compression",
SIAM J. Comput. V. 28(2)
1998 pp 700703.
 # A. Flammenkamp
"Integers with a Small Number of Minimal Addition Chains",
Discrete Mathematics V. 205(1)
1999 pp 221227.
 # E. G. Thurber
"Efficient Generation of Minimal Length Addition Chains",
SIAM Journal of Computing, V. 28(4)
1999 pp 12471263.
 # J. Abrahams
"Addition Chains as Test Trees and a Sequential Variant as the Huffman Problem",
DIMACS Technical Report 9915, February 1999.
 # D. Bleichenbacher
"Addition chains for large sets",
Unpublished manuscript 1999.
 # J. von Zur Gathen, M. Nöcker
"Computing special powers in finite fields",
In Proceedings of the 1999 international Symposium on Symbolic and Algebraic Computation
(Vancouver, British Columbia, Canada, July 28  31, 1999). S. Dooley, Ed. ISSAC.
ACM Press,New York, pp 8390.
 # H. Park, K. Park, Y. Cho
"Analysis of the variable length nonzero window method for exponentiation",
Computers & Mathematics with Applications V. 37(7)
1999 pp 2129.
 # N. Kunihiro and H. Yamamoto
"New Methods for Generating Short Addition Chains",
IEICE Transactions. Fundamentals, E83A, V. 83(1)
2000 pp 6067.
 # M.J. Coster
"The Brun algorithm for Addition Chains",
Unpublished manuscript 2000.
 # V.S. Dimitrov, G.A. Jullien, W.C. Miller
"Complexity and Fast Algorithms for Multiexponentiations",
IEEE Trans. on Computers V. 49(2)
2000, pp 141147.
 # X. Wang
"An algorithm for generating the shortest addition chains",
MiniMicro Systems Shenyang, V. 22(10)
2001 pp 12501253.
 # M. Otto
"Brauer AdditionSubtraction Chains",
Diplomarbeit, UniversitätGesamthochschule Paderborn, 2001.
 # H.M. Bahig, M.H. ElZahar, K. Nakamula
"Some Results for Some Conjectures in Addition Chains",
Combinatorics, Computability and Logic Proceedings of the 3rd international conference vol DMTCS '01
2001 pp 4754.
 # C. Clavier and M. Joye
"Universal Exponentiation Algorithm",
In Proceedings of the Third international Workshop on Cryptographic Hardware and Embedded Systems (May 14  16, 2001).
Lecture Notes In Computer Science, V. 2162
London, 2001 pp 300308.
 # H.M. Bahig, K. Nakamula
"Some Properties of Nonstar Steps in Addition Chains and New Cases Where the Scholz Conjecture Is True",
Journal. Algorithms V. 42(2)
2002 pp 304316.
 # N. Nedjah and L.M. Mourelle
"Minimal Addition Chain for Efficient Modular Exponentiation Using Genetic Algorithms",
IEA/AIE '02: Proceedings of the 15th international conference on Industrial and engineering applications of artificial intelligence and expert systems,
2002 pp 8898.
 # D.J. Bernstein
"Pippenger's Exponentiation Algorithm",
2002.
 # B. Möller
"Improved techniques for fast exponentiation",
International Conference on Information Security and Cryptology
2002 pp 298312.
 # H.M. Bahig, K. Nakamula
"Erratum to Some properties of nonstar steps in addition chains and new cases where the Scholz conjecture is true",
Journal Algorithms V. 47(1)
2003 pp 6061.
 # M. Stam
"Speeding up Subgroup Cryptosystems",
Ph.D. Technische Universiteit Eindhoven, 2003.
 # P. Tummeltshammer, J. C. Hoe, and M. Püschel
"Multiplexed Multiple Constant Multiplication",
In Proceedings of the 41st Annual Conference on Design Automation
(San Diego, CA, USA, June 07  11, 2004). DAC '04
ACM Press, New York, NY, pp 826829.
 # R. Parker, A. Plater
"Addition Chains with a Bounded Number of Registers",
Information Processing Letters, V. 90(5)
2004 pp 247252.
 # R.M. Avanzi
"A note on the signed sliding window integer recoding and a lefttoright analogue",
Selected Areas in Cryptography, Lecture Notes in Computer Science, ISSUE 3357,
2004 pp 130143.
 # R. Guy
"Unsolved problems in number theory",
V. 1
Springer Science & Business Media
2004 pp 169171.
 # N. Nedjah and L. de Macedo Mourelle
"Finding minimal addition chains using ant colony",
International Conference on Intelligent Data Engineering and Automated Learning
2004 pp 642647.
 # J. von Zur Gathen and M. Nöcher
"Computing special powers in finite fields",
Mathematics of computation V. 73(247)
2004 pp 14991523.
 # N.C. Cortés, F.RodríguezHenríquez, R.Morales and C.A.C. Coello
"Finding Optimal Addition Chains Using a Genetic Algorithm Approach",
in Yue Hao et al. (editors),
International Conference on Computational Intelligence and Security 2005 (CIS'05) Part I,
December 1519, 2005, Xi'an, China
SpringerVerlag, Lecture Notes in Computer Intelligence,
2005 pp 208215.
 # N. Nedjah and L. de Macedo Mourelle
"Efficient preprocessing for large windowbased modular exponentiation using ant colony",
International Conference on KnowledgeBased and Intelligent Information and Engineering Systems
2005 pp 640646.
 # C.S. Park and M.K. Lee and D.K. Kim
"New computation paradigm for modular exponentiation using a graph model",
International Symposium on Stochastic Algorithms
2005 pp 170179.
 # H.M. Bahig
"Improved Generation of Minimal Addition Chains",
Computing V. 78(2)
2006 pp 161172
 # H.M. Bahig
"On the Number of Minimal Addition Chains",
Proceedings of the 2006 International Conference on Scientific Computing, CSC 2006, Las Vegas, Nevada, USA, June 2629, 2006
CSREA Press 2006, ISBN 1601320078 pp 202208
 # H.M. Bahig, Hazem M. Bahig
"Speeding Up Evaluation of Powers and Monomials",
Proceedings of the 2006 International Conference on Foundations of Computer Science, Las Vegas, Nevada, USA, June 2629, 2006
CSREA Press 2006, ISBN 1601320159 pp 149153
 # Nadia1 Nedjah, Macedo Mourelle, Luiza
"Towards Minimal Addition Chains Using Ant Colony Optimisation",
Journal of Mathematical Modelling and Algorithms, V. 5(4)
2006 pp 525543
 # M.M. Johansen
"Exponentiation with Addition Chains",
undergraduate project paper, undated.
 # A. Mityagin, I. Mironov, Y.N. Kobliner
"Systems and methods for generating random addition chains",
U.S. Patent xxx.
 # Sander van der Kruijssen
"Addition Chains  efficient computing of powers"
Bachelor Thesis, Amsterdam, 2007
 # R. Goundar
" A Novel MultiExponentiation Method",
IAENG International Journal of Applied Mathematics, V. 37 (2)
,
2007 pp 8995
 # R. Goundar
"Addition Chains in Application to Elliptic Curve Cryptosystems",
PhD thesis, Kochi University, Japan, 2008
 # R.R. Goundar, K. Shiota, and M. Toyonaga
"SPA Resistant Scalar Multiplication using Golden Ratio Addition Chain
Method",
IAENG International Journal of Applied Mathematics, V. 38 (2)
2008, pp 8388
 # N.C. Cortés, F. RodríguezHenríquez and A. C.A.C. Coello
"An Artificial Immune System Heuristic for Generating Short Addition Chains",
IEEE Transactions on Evolutionary Computation, V. 12(1)
2008 pp 124
 # R. Goundar, K. Shiota, and M. Toyonaga,
"New Strategy for Doublingfree Short AdditionSubtraction Chain",
Applied Mathematics & Information Sciences  An International Journal, V. 2
2008, pp 123133
 # R. Goundar, K. Shiota, and M. Toyonaga,
"A Novel Method for Elliptic Curve MultiScalar Multiplication",
International Journal of Applied Mathematics and Computer Sciences, V. 4
2009, pp 15
 # N. M. Clift,
"Calculating optimal addition chains",
Computing V. 91
2011, pp 265284
legend:
# reviewed journal article
# thesis
# report, memorandum, paper
# conference proceedings
# monography
# unclassified or other
I like to thank Neill Clift, Kirkland, Washington, U.S.A., for far the most references in the preceeding bibliography list.
Achim Flammenkamp
Last update: 20180731 11:44:13 UTC+2