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}
[1].
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 achieved 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 ℓ(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 ℓ^{*}(n) [2].
All addition chains for a given number n which have minimal length are called shortest addition chains (for its last/largest number).
I highly recommand Knuth's survey in section 4.6.3, "Evaluation of Powers", of The Art of Computer Programming, Volume 2: Seminumerical Algorithmus (3. edition appeared 1997, 2nd. ed. 1981, 1st ed. 1968) [6].
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 ℓ(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 ℓ(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) = ℓ(n)λ(n)
 Doubling 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: ℓ(i)=r }
 d(r)
 the number of numbers which have a shortest addition chain of length r
d(r) =  L(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 arithmetric 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) = j: f_{r}(j) = max_{h} f_{r}(h) with f_{r}(i) = ∑_{k ∈ N} { j ∈ L(r): ij=k }/4^{k} = ∑_{j ∈ L(r)} 4^{ij}
The base 4 of the power in the preceeding formula can be replaced by every C >= 2, but if C < 2 a different value for p(r) could be achieved.
Moreover for all i and for all C > 1 holds f_{r}(i) < (C+1)/(C1) .
Furthermore p(r) equals the median of a maximal subset of L(r) which is convex, compact or connected, i.e. it is an interval.
For the values r <= 43 but r ∈ {8,12,17,37,41,...} this maximal interval is unique. Of cource in the case the number of elements of the interval is even, p(r) may be the uppermedian or the lowermedian.
 σ(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}
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  L(6) 
7  29  3  4  54.5  51.3  49+  43  21.3  26  L(7) 
8  47  3  5  94.6  88.5  84+  84  39.0  44  L(8) 
9  71  3  4  162.4  151.0  147+  116  70.5  78  L(9) 
10  127  4  7  283.1  262.8  248+  230  125.6  136  L(10) 
11  191  4  7  491.5  456.1  435+  455  220.8  246  L(11) 
12  379  4  7  869.8  809.4  781+  840  387.5  432  L(12) 
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.5  238406628.4  234114742=  284950635  87306215.8  140588339 
34  155691199  7  16  464437430.4  441801858.5  434295820+  397507456  160480246.5  261070184 
35  298695487  7  19  861008497.7  819556624.5  806226455+  680509066  295231414.7  485074788 
36  550040063  7  17  1597540092.7  1521468390.3  1497772642+  1511488768  543803958.6  901751654 
37  994660991  8  18  2966374165.4  2826488080.1  2781892623+  2662728064  1002951179.8  1677060520 
38  1886023151  8  19  5511624121.5  5253825354.5  5175290925=  6428295372  1852301542.4  3119775195 
39  3502562143  8  18  10246077258.4  9769781638.2  9633929370+  12856590540  3426060760.9  5804404206 
40  6490123999  8  21  19053169915.2  18171553433.7  17903170643=  25713180876  6344960374.9  10804952217 
41  11889505663  8  21  35442346436.6  33810106974.4  33316133124=  38569771212  11759089688.4  20125814259 
42  22899028607  8  21  65956820829.5  62937464797.8  62028411677=  72336015580  21797397230.2  37516452013 
43  41866170239  8  25  122812323492.8  117232789580.2  115622740174+  115963068688  40405080341.5  69977286336 
44  76086635263  8  25  228823269079.3  218514610966.6  215644577418=  203573817010  74910180542.4  130579657981 
45  142771387391  8  26  426582178033.3  407515529011.2  402185339149=   138964158415.7  243724383149 
46  257661019487  9  26       
47  498691112447  9  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,257661019487,....
Moreover here are the graphs of c(r) and d(r) together with an approximation function plotted.
The two graphs of the quotient of c(r) and d(r) with a 1st order asymptotic approximation function
and with a 2nd order approximation function.
Finally the distribution of the number of shortest addition chains with fixed small step number and fixed λ(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
 ℓ(i) with i <= 50 or v(i) <=4 , and d(r) with r <=6
calculated March 1957 by W. Hansen [3]
 ℓ(i) with i <= 2^{10} and d(r) with r <=11
reported December 1963 by D. E. Knuth
 ℓ(i) with i < 2000 and d(r) with r <= 12
reported October 1968 by D. E. Knuth
 ℓ(i) with i < 18269 and d(r) with r <= 15 and c(r) with r <= 18
reported May 1969 by D. E. Knuth [6]
 ℓ(i) with i < 120000 and c(r) with r <= 22
computed until August 1988 by Achim
 ℓ(i) with i < 2^{17} and d(r) with r <= 20
computed April 1991 by Achim
 ℓ(i) with i < 2^{18} and d(21) and c(23)
computed until October 1991 by Achim
 ℓ(i) with i <= 500000 and c(24)
computed until November 1995 by D. Bleichensbacher
 ℓ(i) with i <= 720000 including c(25)
computed until end of March 1997 by Achim.
 ℓ(i) with i <= 2^{22} including c(28) and d(r) with r <= 25
computed until August 1997 by Achim.
 ℓ(i) with i <= 2^{22} and d(25) and d(26)
computed until August 2004 by Neill Clift
 ℓ(i) with i <= 2^{23} and d(27) and c(29) and c(30)
computed until September 2004 by Neill Clift
 ℓ(i) with i <= 2^{24}
computed until December 2004 by Neill Clift
 c(31)
computed December 2005 by Neill Clift
 ℓ(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
 ℓ(2^{29}1) = 29 + ℓ(29)  1
proved in December 2007 by Neill Clift
 ℓ(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
 ℓ(i) with i <= 2^{27} and ℓ(i) with i <= 2^{28} and ℓ(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
 ℓ(2^{n}1) = n + ℓ(n)  1, with n ∈ {31,33,...,46,48,49,50,51,52,54,56,60}
proved in May 2008 by Neill Clift

the first and smallest n such that ℓ(n) > ℓ(2n)
discovered on 30th May 2008 by Neill Clift
 c(36), d(34) and d(35)
computed June 2008 by Neill Clift
 c(37) and ℓ(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
 ℓ(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
 ℓ(i) with i <= 2^{32}
computed until October 2008 by Neill Clift
 ℓ(2^{n}1) = n + ℓ(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
 ℓ(2^{n}1) = n + ℓ(n)  1 with n ∈ {53,55}
proved in November 2008 by Neill Clift
 (2^{n}1) = n + ℓ(n)  1 with n ∈ {57}
proved in December 2008 by Neill Clift
 ℓ(2^{n}1) = n + ℓ(n)  1 with n ∈ {58,59}
proved in January 2009 by Neill Clift
 ℓ(2^{n}1) = n + ℓ(n)  1 with n ∈ {61}
proved in February 2009 by Neill Clift
 ℓ(2^{n}1) = n + ℓ(n)  1 with n ∈ {62,63}
proved until May 2009 by Neill Clift
 c(40)
computed in September 2009 by Neill Clift
 ℓ(i) with i <= 2^{33}
computed until October 2009 by Neill Clift
 c(41)
computed in November 2009 by Neill Clift
 ℓ(i) with i <= 2^{34}
computed until December 2009 by Neill Clift
 c(42)
computed in May 2016 by Neill Clift
 ℓ(2^{n}1) = n + ℓ(n)  1 with n ∈ {65,66,68,72,80,96}
proved in May 2016 by Neill Clift
 ℓ(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
 ℓ(i) with i <= 2^{36}
computed until October 2016 by Neill Clift
 ℓ(2^{n}1) = n + ℓ(n)  1, if ℓ(n) <= 8
computed in July 2018 by Neill Clift
 d(41)
computed in July 2019 by Neill Clift
 c(44)
computed in July 2019 by Neill Clift
 ℓ(i) with i <= 2^{37}
computed until July 2019 by Neill Clift
 ℓ(2^{n}1) = n + ℓ(n)  1, with n <= 134 and ℓ(n)=9
computed in July 2019 by Neill Clift
 ℓ(2^{n}1) = n + ℓ(n)  1, if ℓ(n) <= 9
computed in September 2019 by Neill Clift
 s(n) = ℓ(n)  λ(n) >= log_{2}(v(n)), if s(n) <= 5
computed in September 2019 by Neill Clift
 c(45)
computed in November 2019 by Neill Clift
 c(46)
computed in February 2020 by Neill Clift
 d(42)
computed in March 2020 by Neill Clift
 ℓ(i) with i <= 2^{38}
computed until March 2020 by Neill Clift
 d(43)
computed in March 2020 by Neill Clift
 d(44)
computed in April 2020 by Neill Clift
 c(47)
computed in January 2021 by Neill Clift
 ℓ(i) with i <= 2^{39}
computed until September 2022 by Neill Clift
 d(45)
computed in September 2022 by Neill Clift
 s(n) = ℓ(n)  λ(n) >= log_{2}(v(n)), if s(n) = 6
computed until November 2023 by Neill Clift
In July 2004 the data calculated 1997 by Flammenkamp was completely and independently checked.
Hereby Neill Clift uncovered four ℓ(n)errors, which he attributed to a typo
in Flammenkamp's program effecting only nvalues > 2500000.
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 ℓ(n)λ(n)ceil(log_{2}(v(n))) into 2 bits each which the exception of ℓ(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 ℓ(n), λ(n), s(n) and v(n) for each given input n which data is in the datafile.
You can also download all ℓ(n) with n <= 2^{33} as bziped2 binary data of 820 MB size.
Here datafile indicates the downloaded and then uncompressed data file.
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 ℓ(n) with n <= 2^{expo} as bziped2 binary data. Choose expo depending on your disk storage capabilities of your computer system from the following table:
To display the ℓ(n)values you must also download ddt4ln.c, compile it and run it as ddt4ln datafile [O?] [first n [total number [linelength] ] ].
Here datafile indicates the downloaded and then uncompressed data file.
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 ddt4l.The parameter O4 produces a format very similar to this of the above old helperprogram l.
In the case you need fast (and also random) access to ℓ(n) values it is
very announing to have to calculate v(n) and λ(n) for each n. Thus here is a Csourcecode to generate from add3?.4ln a new file containing either a table of s(n) values each represented by a halfbyte
(bits 03 of a byte hold the value for odd n and bits 47 of a byte hold it for even n)
or a table of ℓ(n) values each represented by 1 byte. Of cource the new file will be of doubled size in the first case and of 4times the size in the last case.
Look up in the database of the first 2^{31} many ℓ(n) values
The effort to compute these values up to n=2^{20} is here visible.
The number of cases checked to get ℓ(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 ℓ(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 ℓ(n)λ(n)ceil(log_{2}(v(n))) equals 0,1,2,3,4,... are 1, 29, 3691, 919627, 2135101487, ... .
A remark for the simple upper bound λ(n)v(n)+1 of ℓ(n): The smallest n such that ℓ(n)λ(n)+1=v(n) equals 1,2,3,4,5,... are 1, 3, 7, 29, 465, 24745, 12591273, 51544066569, ... .
For every n with ℓ(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, ℓ(n) and number of shortest addition chains for this n.
Neill Clift extended this data and put it into a file of almost 250 MB size. Thus you can download the number of shortest addition chains with ℓ(n) <=28 as a gziped ASCIIfile of 74 MB.
Conjectures
 ℓ(2^{n}1) <= n + ℓ(n)  1
 The outstanding ScholzBrauerConjecture of 1937. If ℓ(n) is achievable by a star chain then it holds. Therefore only values of n need to be considered with ℓ(n) < ℓ^{*}(n). But the smallest of these numbers is 12509.
In August 2005 Clift reported to have confirmed the ScholzBrauer inequality for all n < 5784689. ^{+}
 ℓ(2^{n}1) = n + ℓ(n)  1
 This narrow related equation is proved to hold at least for all n with ℓ(n) <= 9 ^{*}.
 ℓ(n) >= λ(n)+log_{2}(v(n))
 This famous lower bound was formulated first a bit differently by Stolarsky 1969 (p. 680, Lemma 10) [5] and
nearly proved 1974 by Schönhage who showed that ℓ(n) >= log_{2}(n)+log_{2}(v(n))2.123164629... holds for each n [7].
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}
and in September 2019 he confirmed it for all n with ℓ(n)  λ(n) <= 5.
Finally until November 2023 Neill Clift extended the validity of the conjecture for all n with v(n) <= 128.
 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 ℓ(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!
In 2002 E. Lehmann noted in his Ph.D. thesis, p 35: "Nevertheless, an exact solution to the addition chain problem remains strangely elusive. The Mary method runs in time polylog(n) and gives a 1 + o(1) approximation. However, even if exponentially more time is allowed, poly(n), no exact algorithm is known."
 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 the smallest NonHansen number 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 ℓ(n) <= 8.
He extended this equality in July 2019 to those n <= 134 with ℓ(n) = 9 and finally in September 2019 to all n with ℓ(n) = 9.
Unsorted 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.
Moreover, here is a link to the world's leading expert website to find shortest addition chains quickly and thus calculating these values ℓ(n) really fast covering all the "smaller" natural numbers n  state of the art: March 2020.
References
 Arnold Scholz
"Aufgabe 253",
Jahresbericht der deutschen MathematikerVereinigung V. 47, 2. Abteil.
1937 pp 4142.
 Alfred T. Brauer
"On addition chains",
Bulletin of the American Mathematical Society V. 45(10)
1939 pp 736739.
 Walter Hansen
"Zum ScholzBrauerschen Problem",
Journal für die reine und angewandte Mathematik, V. 202
1959 pp 129136.
 Pál Erdös
"Remarks on number theory. III: On addition chains",
Acta Arith. V. 6(1)
1960 pp 7781.
 Kenneth B. Stolarsky
"A lower bound for the ScholzBrauer problem",
Canadian Journal of Mathematics, V. 21
1969 pp 675683.
 Donald E. Knuth
The Art of Computer Programming V. 2
Seminumerical Algorithms, 1st edition,
AddisonWesly 1969 pp 398422.
 Arnold Schönhage
"A Lower Bound for the Length of Addition Chains",
Theoretical Computer Science, V. 1(1)
1975 pp 112.
Bibliography with more than 230 entries.
Achim Flammenkamp
Last update: 20231121 14:59:17 UTC+2