Shortest Addition Chains

Introduction

Lower and Upper Bounds of ℓ(n)

Notation

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_i-1 + a_i-1

Star step

a_i = a_i-1 + a_j with j < i

Small step

λ(a_i) = λ(a_i-1)

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

Λ(n)

the number of shortest addition chains for n

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): |i-j|=k }|/4^k = ∑_{j ∈ L(r)} 4^-|i-j|
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)/(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
σ²(r) = 1/d(r) ∑_{i ∈ L(r)} i² - μ(r)²

Table of Characterizing Values

Generally Solved Small Step Cases

0-small-step case

Trivial

• For each n >= 0 there is exactly 1 0-small-step number in the half-open interval [2^n,2^(n+1)[ .
  

• list of all 0-small-step numbers:

  2^n

• shortest chains for 0-small-step numbers:
  

     0(     )  1 
     1( 0, D)  @(A)
  
  Here @(A)  means 2^A  with A a free nonnegative integer variable
  

1-small-step case

<= 1894 solved

• count of all 1-small-step numbers
• list of all 1-small-step numbers
• shortest chains for 1-small-step numbers

2-small-step case

<= 1957 solved

• count of all 2-small-step numbers
• list of all 2-small-step numbers
• shortest chains for 2-small-step numbers

3-small-step case

1991 solved

• count of all 3-small-step numbers
• list of all 3-small-step numbers
• shortest chains for 3-small-step numbers

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¹⁰ 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¹⁷ and d(r) with r <= 20
  computed April 1991 by Achim
• ℓ(i) with i < 2¹⁸ 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²² including c(28) and d(r) with r <= 25
  computed until August 1997 by Achim.
• ℓ(i) with i <= 2²² and d(25) and d(26)
  computed until August 2004 by Neill Clift
• ℓ(i) with i <= 2²³ and d(27) and c(29) and c(30)
  computed until September 2004 by Neill Clift
• ℓ(i) with i <= 2²⁴
  computed until December 2004 by Neill Clift
• c(31)
  computed December 2005 by Neill Clift
• ℓ(i) with i <= 2²⁵
  computed until April 2006 by Neill Clift
• d(29), d(30) and c(32)
  computed until June 2007 by Neill Clift
• ℓ(2²⁹-1) = 29 + ℓ(29) - 1
  proved in December 2007 by Neill Clift
• ℓ(i) with i <= 2²⁶
  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²⁷ and ℓ(i) with i <= 2²⁸ and ℓ(i) with i <= 2²⁹
  computed in May 2008 by Neill Clift
• d(33), c(34) and c(35)
  computed in May 2008 by Neill Clift
• ℓ(2ⁿ-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³⁰
  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³¹
  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³²
  computed until October 2008 by Neill Clift
• ℓ(2ⁿ-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ⁿ-1) = n + ℓ(n) - 1 with n ∈ {53,55}
  proved in November 2008 by Neill Clift
• (2ⁿ-1) = n + ℓ(n) - 1 with n ∈ {57}
  proved in December 2008 by Neill Clift
• ℓ(2ⁿ-1) = n + ℓ(n) - 1 with n ∈ {58,59}
  proved in January 2009 by Neill Clift
• ℓ(2ⁿ-1) = n + ℓ(n) - 1 with n ∈ {61}
  proved in February 2009 by Neill Clift
• ℓ(2ⁿ-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³³
  computed until October 2009 by Neill Clift
• c(41)
  computed in November 2009 by Neill Clift
• ℓ(i) with i <= 2³⁴
  computed until December 2009 by Neill Clift
• c(42)
  computed in May 2016 by Neill Clift
• ℓ(2ⁿ-1) = n + ℓ(n) - 1 with n ∈ {65,66,68,72,80,96}
  proved in May 2016 by Neill Clift
• ℓ(i) with i <= 2³⁵
  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³⁶
  computed until October 2016 by Neill Clift
• ℓ(2ⁿ-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³⁷
  computed until July 2019 by Neill Clift
• ℓ(2ⁿ-1) = n + ℓ(n) - 1, with n <= 134 and ℓ(n)=9
  computed in July 2019 by Neill Clift
• ℓ(2ⁿ-1) = n + ℓ(n) - 1, if ℓ(n) <= 9
  computed in September 2019 by Neill Clift
• s(n) = ℓ(n) - λ(n) >= log₂(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³⁸
  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³⁹
  computed until September 2022 by Neill Clift
• d(45)
  computed in September 2022 by Neill Clift
• s(n) = ℓ(n) - λ(n) >= log₂(v(n)), if s(n) = 6
  computed until November 2023 by Neill Clift

Data Access

Look up in the database of the first 2³¹ many ℓ(n) values

Generate a Shortest Addition Chain for any given number < 2²⁷

^# The smallest n such that ℓ(n)-λ(n)-ceil(log₂(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 Λ(n). Neill Clift extended this data and put it into a file of 450 MB size. Thus you can download the number of shortest addition chains with ℓ(n) <=29 as a gziped ASCII-file of 142 MB which presents these values for 26066657 numbers.

Conjectures

ℓ(2ⁿ-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. ⁺

ℓ(2ⁿ-1) = n + ℓ(n) - 1

This narrow related equation is proved to hold at least for all n with ℓ(n) <= 9  ^*.
On 1th July 2024 Neill Clift disproved that the conjecture holds for all n by constructing an addition chain for 2^30978119-1 of length 30978148, but ℓ(30978119)=31.

ℓ(n) >= λ(n)+log₂(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₂(n)+log₂(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⁶⁴ 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. This famous inequality may be rewriten equivalently as v(n) <= 2^s(n).

log₂(c(r)) ~ r - r/log₂r

That is the 1997 stated conjecture by Flammenkamp for the asymptotic growth of c(r) outdating the 1991 given assertation that log₂(c(r)) ~ r - 2log₂r.

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

K ⊆ {3,5,7,9,11} <==> ∀ k ∈ K: |{n : Λ(n) = k }| ∈ N

If and only if the number of shortest addition chains is one the five values 3,5,7,9 or 11, then there are finite many n such that for each of these n holds Λ(n) ∈ {3,5,7,9,11}. Specificaly, Λ(n)=3 <==> n ∈ {9,12}, Λ(n)=5 <==> n ∈ {7,27,48}, Λ(n)=7 <==> n ∈ {18,192}, Λ(n)=9 <==> n = 768 and Λ(n)=11 <==> n = 3072

Unsorted stuff

• An equivalent definition of addition chains based only on the set-theoretic 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

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.