We often want to raise some value (not necessarily a real value) to an integer power (exponentiation). This is a pretty common operation in cryptography. The product rule of exponents tells us that \(x^a\times x^b=x^{a+b}\). So, let's try and see how we would calculate \(x^{29}\). I pick 29 as this number shows up many strange properties that make the subject worth studying.
\(x^{29}=x^{20}\times x^9\)
\(x^{20}=x^{11}\times x^9\)
\(x^{11}=x^9\times x^2\)
\(x^9=x^8\times x^1\)
\(x^8=x^4\times x^4\)
\(x^4=x^2\times x^2\)
\(x^2=x^1\times x^1=x\times x\)
Now we can dispense with all the \(x^a\) type terms and just record the \(a\) (exponent) values. 1 2 4 8 9 11 20 29. Under the assumption that all the multiplies have the same cost (often true but not true for example with integers as the bigger they get the more expensive they are to multiply) and that squaring \(x^a\times x^a\) is the same cost as a general multiply \(x^a\times x^b, a\ne b\) we want to keep the list of exponents small in number. It turns out that the way I calculated \(x^{29}\) above is an example of a shortest chain. You can't do better than 7 steps (8 exponent values). There are 132 different ways of getting to 29 in 7 steps if we ignore how each exponent value is constructed and just focus on the exponent value. The number of ways of getting to 29 explode as we increase the length. So, for example, in 8, 9, 10 and 11 steps we have 1781, 12619, 58875 and 205368 ways to get to 29 respectively.
We will put what we saw here into more exact mathematical language next. That will make it easier to describe just how strange this simple problem is. Things that seem obvious are in fact not true and we don't really know very much about the subject.
My primary interest is in trying to find ways that computers can find shortest chains more efficiently. I got interested in this topic trying to hack the VMS password hashing algorithm (Purdy Polynomial). I am a bit of a treasure hunter looking for numbers with strange properties. Few people actually study this area and so this website is here to find people who want to exchange ideas, talk about the area or write programs. Beware it's highly addictive trying to improve addition chain programs.
Send me mail Neill Clift if you're interested.
Start with a list of numbers containing initially 1. Perform a number of steps where we add two (not necessarily different) existing numbers together and add the new number to the list. If we eventually arrive at the number \(n\) we call this an addition chain (or more rarely an additive chain) for \(n\).
So, for example, we could create the following list 1,2,3,6,9,9,12,24,18 and call this an addition chain for \(n=18\). We will call the individual values in an addition chain elements and \(n\) the target.
We should note some things about this addition chain for 18.
We will assume from now on that addition chains are ordered and duplicate or values exceeding the target are removed.
Formally then an addition chain is:
\(1=a_{0}<a_{1}<\cdots<a_{r}=n,\,a_{i} =a_{j} +a_{k}\) with \(i>j\ge k\ge0\)
We say this addition chain has length \(r\). The chain with the shortest length we call the optimal chain. We denote its length by \(l(n)\). Many interesting questions arise when we consider optimal chains. Lots of stuff that might seem obvious is in fact wrong. For example, it seems reasonable to assume that each step in an addition chain uses the largest element created so far or that the best way to reach \(2n\) is by doubling the last element of a chain for \(n\). Both of these assumptions turn out to be false.
We define:
\(\lambda(n)=\left\lfloor log_{2}(n)\right\rfloor \)
\(v(n)=\begin{cases}
0 & n=0\\
v(\left\lfloor \frac{n}{2}\right\rfloor )+n\bmod2 & n>0
\end{cases}\) So, it's the number of 1s in the binary representation of n.
\(s(n) = l(n) - \lambda(n)\)
For step \(i\) of an addition chain we have two possibilities:
We can see from this that \(s(n)\) and \(\lambda(n)\) count the number of small and large steps respectively in an optimal addition chain for \(n\).
Additionally for step \(i\) we say that:
We define \(\Lambda(n)\) as the number of optimal addition chains for \(n\).
The smallest target requiring \(r\) steps in its optimal chain \(c(r) = \min \{n | l(n) = r\}\).
The number of targets requiring exactly \(r\) steps in their optimal chains \(d(r) = |\{n | l(n) = r\}|\).
We will often want to remove the ambiguity of how an addition chain element is constructed. We do this by tracking how each element is formed. I will use a hash notation to show this. For example, in this non-optimal addition chain for 4
1 2 3 4
I will use:
1 2 3 4#1,1 to show the element 4 is made from 2+2 or:
1 2 3 4#0,2 to show the element 4 is made from 1+3.
Here the hash is followed by two zero base indices into the addition chain.
In my opinion the most important conjecture on addition chains. It seems remarkable that \(v(n)\) appears to be bounded by the small step count of the chain:
\(v(n)\le2^{s(n)}\)
This conjecture is normally stated differently:
\(l(n)\ge\lambda(n)+\left\lceil log_{2}(v(n))\right\rceil \)
Cases \(s(n)=0,1\) can be determined with simple bounds. If \(s(n)=0\) then \(n=2^A\) and with \(s(n)=1\) then \(n=2^A+2^B\) is the best we can do bit count wise. Knuth outlines the case for \(s(n)=2\) yielding \(n=2^A+2^B+2^C\) or four cases were \(n=2^A+2^B+2^C+2^D\) (for example \(A-B=C-D\)).
The three-bit case was proved in [8] and the four-bit case by Knuth himself. Ed Thurber in his PhD thesis [9] proved the \(s(n)=3\) case. Achim Flammenkamp in his diploma thesis [10] wrote a computer program to enumerate all numbers reachable via 3 small steps and likewise found \(v(n)\le8\). I wrote a program to mimic the proof technique of Ed Thurber's thesis and verified the result but could not get it to work for the case \(s(n)=4\).
Using the derivative chains of Hansen transformed to graphs and making heavy use of symmetry to reduce problem size I was able to enumerate all numbers reachable with 4 and 5 small steps. I was also able to enumerate all the numbers reachable by 6 small steps restricted to those that might violate the conjecture.
So overall we know that \(v(n)\le2^{s(n)}\) for \(s(n)\le6\). So, for example, any number with \(v(n)\ge65\) must have \(s(n)\ge7\).
If this conjecture is true, it has some interesting consequences. Let's consider the number \(n = 223696213\) or in binary \(1101010101010101010101010101_2\). We have \(v(n) = 15\) so we expect \(s(n) \ge 4\).
We can easily see though that \(s(n) \ne 4\) since if \(s(n) = 4\) we could take an addition chain for \(n\) and extend it to form \(3n = 100111111111111111111111111111_2\):
1, 2, ..., 223696213, 447392426, 671088639
We have added only large steps but \(v(671088639) = 28\) so we expect \(5 \le s(3n) = s(n) = 4\) which is a contradiction. So, we must have \(s(n) \ge 5\).
Computer searches show \(s(671088639) = s(223696213) = 6\) achieved with the following chain:
1, 2, 3, 5, 10, 13, 23, 46, 92, 105, 210, 420, 840, 1680, 3360, 6720, 6825, 13650, 27300, 54600, 109200, 218400, 436800, 873600, 1747200, 3494400, 6988800, 13977600, 27955200, 55910400, 111820800, 223641600, 223696200, 223696213
I outline enumeration of small step chains here:
Find details here of the first known cases where \(l(2^n-1)<l(n)+n-1\). I found this case first Exact Equality but a few days later I put some effort into trying to find a smaller case:
The smallest case I have found so far is here but with way less verbiage: Exact Equality
Probably the most worked on conjecture in addition chains by far:
We do seem to be able to correct some gaps caused by non-Hansen chains. The first case I found was for the 7th non-Hansen 23097633. I then found the 19th and 20th non-Hansen 31942247 and 32364653 respectively could be constructed.
Using a different technique, I was able to close the gap for the first and second non-Hansen 5784689, 11568241.
Details here: Repair
These addition chains with an extra condition on each step are quite interesting. I calculated some values here:
After seeing a student paper using some graph properties on addition subtraction chains, I did a small calculation. See some results here:
Calculating Optimal Addition Chains
I run a bunch of machines to search for various things in the addition chain space. Currently I am using mostly EPYC 9654 processors.
2 X AsRock Rack 1U4L4E-GENOA/2T EPYC 9654
1 X Asus RS500A-E12-RS12U EPYC 9654
1 X MSI S2206-02 Dual EPYC 9654
1 X Dell 7525 Dual EPYC 7713 64 core machine
I have tried to build a list of all publications on addition chains. This is not simple because it can be difficult to draw the line between a paper on addition chains and one that uses them.
I do not include addition-subtraction chains but do include addition sequences and vector addition chains as recent work shows they are tied together.
I have tried to obtain all of these publications and only have a few missing. I would welcome any additional references or access to the stuff I do not have. The article in red I do not have a copy of.
I manage the following BibTex file with JabRef (JabRef.org):
[1] Brauer A (1939), "On addition chains", Bulletin of the American Mathematical Society. Vol. 45(10), pp. 736-739.
[2] Hansen W (1957), "Untersuchungen über die Scholz-Brauerschen Additionsketten und deren Verallgemeinerung". Thesis at: Göttingen.
[3] Hansen W (1959), "Zum Scholz-Brauerschen Problem.", Journal für die reine und angewandte Mathematik. Vol. 202, pp. 129-136.
[4] Knuth DE (1969), "The art of computer programming, 2: seminumerical algorithms, Addison Wesley", Reading, MA., §4.6.3, pp. 398-422.
[5] Knuth DE (1998), "The art of computer programming, 2: seminumerical algorithms, Addison Wesley", Reading, MA., §4.6.3, pp. 461-485.
[6] Thurber EG (1999), "Efficient Generation of Minimal Length Addition Chains", SIAM Journal on Computing. Vol. 28(4), pp. 1247-1263.
[7] Thurber EG and Clift NM, "Addition chains, vector chains, and efficient computation", Discrete Mathematics, Volume 344, Issue 2, 2021,
[8] Gioia A, Subbarao M and Sugunama M (1962), "The Scholz-Brauer problem in addition chains", Duke Math. J. Vol. 29, pp. 481-487.
[9] Thurber, E. "The Scholz-Brauer Problem on Addition Chains", University of Southern California, University of Southern California, 1971.
[10] Flammenkamp A (1991), "Drei Beiträge zur diskreten Mathematik: Additionsketten, No-Three-in-Line-Problem, Sociable Numbers". Thesis at: Diplomarbeit an der Fakultät für Mathematik, Universität Bielefeld.
Bleichenbacher D (1999), "Addition chains for large sets", Unpublished manuscript.