Shortest Addition Chains

Introduction

A finite sequence of positive integers a0, a1, ..., ar is called an addition chain iff for each element ai, but the first a0 which equals 1, there exist elements in the sequence with smaller indices j and k such that ai = aj + ak [1].
Preciser this is called an addition chain of length r for its last number ar. It can be interpreted like calculating n = ar 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 a1=2 and a2=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 i-1 for all positive indices i -- each ai in the chain requires the previous ai-1, we call such a chain a star-chain 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:
Addition Chain 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 (floor-function). 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) + log2(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
ai = ai-1 + ai-1
Star step
ai = ai-1 + aj with j < i
Small step
λ(ai) = λ(ai-1)
Standard step
ai = aj + ak 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)
2r
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) = i: fr(i) = maxh fr(h) with fr(i) = ∑k ∈ N |{ j ∈ L(r): |i-j|=k }|/4k = ∑j ∈ L(r) 4-|i-j|
The base 4 of the power in the preceding 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 fr(i) < (C+1)/(C-1) . 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 upper-median or the lower-median.
σ(r)
the standard deviation of the numbers which have a shortest addition chain of length r
σ2(r) = 1/d(r) ∑i ∈ L(r) i2 - μ(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= 10 1{1}
1 2 0 1 2.0 2.0 2= 20 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= 61.2 3{5,6,8}
4 7 2 3 10.8 10.4 10= 103.1 5{7,9,10,12,16}
5 11 2 3 18.2 17.3 17= 146.1 9{11,13,14,15,17,18,20,24,32}
6 19 2 3 31.7 30.1 28= 2611.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.11772876.31732716+ 2310196 702737.4 1028508
26 1176431 6 14 3443135.03259501.83191985+ 2801503 1273563.8 1896704
27 2211837 6 16 6333417.26001516.05881151= 5612462 2313684.8 3501029
28 4169527 7 17 11667084.111064752.410848521+ 9412704 4214352.7 6465774
29 7624319 7 15 21516285.220418193.420044424+ 16905070 7697737.3 11947258
30 14143037 7 16 39714338.937704137.937013874= 41615456 14098404.4 22087489
31 25450463 7 15 73345796.769658962.368327129+ 83230816 25868797.8 40886910
32 46444543 7 18 135563778.8128804664.5126581547+ 132022368 47516034.6 75763102
33 89209343 7 18 250780403.5238406628.4234114742=28495063587306215.8140588339
34 155691199 7 16 464437430.4441801858.5434295820+397507456160480246.5261070184
35 298695487 7 19 861008497.7819556624.5806226455+680509066295231414.7485074788
36 550040063 7 17 1597540092.71521468390.31497772642+1511488768543803958.6901751654
37 994660991 8 18 2966374165.42826488080.12781892623+26627280641002951179.81677060520
38 1886023151 8 19 5511624121.55253825354.55175290925=64282953721852301542.43119775195
39 3502562143 8 18 10246077258.49769781638.29633929370+128565905403426060760.95804404206
40 6490123999 8 21 19053169915.218171553433.717903170643=257131808766344960374.910804952217
41 11889505663 8 21 35442346436.633810106974.433316133124=3856977121211759089688.420125814259
42 22899028607 8 21 65956820829.562937464797.862028411677=7233601558021797397230.237516452013
43 41866170239 8 25 122812323492.8117232789580.2115622740174+11596306868840405080341.569977286336
44 76086635263 8 25 215644577418=203573817010 130579657981
45 142771387391 8 26
46 257661019487 9 26

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 r-value because d(r) is even.
With bold font in the previous c(r)-column the sequence of smallest numbers ni is high-lighted 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

0-small-step case
Trivial
1-small-step case
<= 1894 solved
2-small-step case
<= 1957 solved
3-small-step case
1991 solved


History: What was calculated When and by Whom

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 n-values > 2500000.
On 30th May 2008, Neill Clift discovered the first and smallest n such that ℓ(n) > ℓ(2n).


Data Access

Thanks to Neill Clift's computations you can download the lengths of all shortest additions chains for n up to n=231 as bziped2 binary data of 210 MB size. The uncompressed values are coded as ℓ(n)-λ(n)-ceil(log2(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 base-36 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 <= 233 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 number-many values starting from 1 or first n and broken into lines each containing linelength values onto your stdout from the base-42 alphabet (0,1,2,..,9,a,b,c,..,z,A,B,C,..,F).
Now you can download all ℓ(n) with n <= 2expo as bziped2 binary data. Choose expo depending on your disk storage capabilities of your computer system from the following table:
max n binary data file compressed size uncompressed size online since
232 add32.4ln.bz2 417 MB 1073742360 bytes ?
233 add33.4ln.bz2 820 MB 2147484256 bytes ?
234 add34.4ln.bz2 1612 MB 4294967964 bytes ?
235 add35.4ln.bz2 3197 MB 8589935360 bytes May 2016
236 add36.4ln.bz2 6397 MB 17179869992 bytes Oct 2016
237 add37.4ln.bz2 12863 MB 34359739200 bytes Jul 2019
238 add38.4ln.bz2 25854 MB 68719477576 bytes Mar 2020
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 number-many 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 output-option. 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 helper-program l.
In the case you need fast (and also random) access to ℓ(n) values it is very announing to have to calculate v(n) an λ(n) for each n. Thus here is a C-source-code to generate from add3?.4ln a new file containing either a table of s(n) values each represented by a half-byte (bits 0-3 of a byte hold the value for odd n and bits 4-7 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 4-times the size in the last case.

Look up in the database of the first 231 many ℓ(n) values

starting from index the following values
Table Raw

The effort to compute these values up to n=220 is here visible. The number of cases checked to get ℓ(n) is plotted in red against λ(n) for each number 28 <= n < 220. 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 < 227

n= fast difficult

# The smallest n such that ℓ(n)-λ(n)-ceil(log2(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 ASCII-file 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.


Conjectures

ℓ(2n-1) <= n + ℓ(n) - 1
The outstanding Scholz-Brauer-Conjecture 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 Scholz-Brauer inequality for all n < 5784689. +
ℓ(2n-1) = n + ℓ(n) - 1
This narrow related equation is proved to hold at least for all n with ℓ(n) <= 9  *.
ℓ(n) >= λ(n)+log2(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) >= log2(n)+log2(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 <= 264 and in September 2019 he confirmed it for all n with ℓ(n) - λ(n) <= 5.
log2(c(r)) ~ r - r/log2r
That is the 1997 stated conjecture by Flammenkamp for the asymptotic growth of c(r) outdating the 1991 given assertation that log2(c(r)) ~ r - 2log2r.
Computing ℓ(n) for given n is NP-hard.
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 M-ary 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 = 222+97*214+65*24+97 is the smallest Non-Hansen 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 ground-breaking 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 new stuff

Moreover, here is a link to the world's leading expert web-site 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

  1. Arnold Scholz
    "Aufgabe 253",
    Jahresbericht der deutschen Mathematiker-Vereinigung V. 47, 2. Abteil.

    1937 pp 41-42.
  2. Alfred T. Brauer
    "On addition chains",
    Bulletin of the American Mathematical Society V. 45(10)

    1939 pp 736-739.
  3. Walter Hansen
    "Zum Scholz-Brauerschen Problem",
    Journal für die reine und angewandte Mathematik, V. 202

    1959 pp 129-136.
  4. Pál Erdös
    "Remarks on number theory. III: On addition chains",
    Acta Arith. V. 6(1)

    1960 pp 77-81.
  5. Kenneth B. Stolarsky
    "A lower bound for the Scholz-Brauer problem",
    Canadian Journal of Mathematics, V. 21

    1969 pp 675-683.
  6. Donald E. Knuth
    The Art of Computer Programming V. 2 Seminumerical Algorithms, 1st edition,
    Addison-Wesly 1969 pp 398-422.
  7. Arnold Schönhage
    "A Lower Bound for the Length of Addition Chains",
    Theoretical Computer Science, V. 1(1)

    1975 pp 1-12.
Bibliography with more than 230 entries.


Achim Flammenkamp
Last update: 2020-06-07 14:35:00 UTC+2