Donald Knuth wrote a computer program to calculate addition chains in 1963. He reported the results in [1]. At the time it was considered pretty remarkable that addition chain for 191 and its double 382 were the same length.
In fact, it was supposedly proved that \(l(2n) = l(n)+1\) in [3] in answer to the question posed in [2]. When I looked at these papers, I didn't really see much of a mathematical argument that you could call a proof.
I think it's nice to look at the very few optimal chains for 382 and pair them up with similar chains for 191:
1 2 4 5 9 14 23 46 92 184 198 382
1 2 4 5 9 14 23 46 92 184 186 191
1 2 4 5 9 14 23 46 92 184 368 382
1 2 4 5 9 14 23 46 92 184 189 191
1 2 4 8 16 17 33 50 83 166 216 382
1 2 4 8 16 17 33 50 83 166 174 191
1 2 4 8 16 17 33 50 83 166 332 382
1 2 4 8 16 17 33 50 83 166 183 191
I didn't really expect the chains to be the same for so many elements.
I was searching for more extreme cases and in 2007 I found that \(l(30958077) = l(2*30958077) = l(4*30958077)\).
1 2 4 5 9 18 36 72 144 288 293 581 1162 1743 2036 3779 7558 15116 30232 60464 120928 241856 483712 967424 1934848 3869696 7739392 15478784 30957568 61915136 123830272 123832308
1 2 4 5 7 14 28 33 61 94 188 376 752 1504 3008 6016 12032 24064 48128 96256 96317 192573 288890 481463 962926 1925852 3851704 7703408 15406816 30813632 61627264 61916154
1 2 3 6 9 15 24 39 63 102 204 408 471 942 1884 3768 7536 15072 30144 30207 60288 120576 241152 482304 964608 1929216 3858432 7716864 15433728 15463935 30927870 30958077
In 2008 I managed to find an example of \(l(2n) < l(n)\) with \(l(750989406) < l(375494703)\).
1 2 4 5 6 11 17 28 56 73 101 202 404 477 954 1908 3816 7632 15264 30528 61056 122112 244224 488448 488925 977850 1955700 3911400 7822800 15645600 31291200 62582400 125164800 125164901 250329802 375494703
1 2 4 8 9 17 34 51 85 94 179 358 716 1432 2864 5728 11456 22912 45824 91648 183296 183347 366694 733388 1466776 2933552 5867104 11734208 23468416 46936832 93873664 187747328 375494656 750989312 750989406
Very quickly after I found the \(l(2n)<l(n)\) Ed Thurber came up with a rough rational for the phenomenon. If we look at the binary representation of the two numbers:
\(n=375494703=\underset{179}{\underline{10110011}}0000\underset{51}{\underline{110011}}00000\underset{47}{\underline{101111}_2}\)
\(n=750989406=\underset{179}{\underline{10110011}}0000\underset{51}{\underline{110011}}00000\underset{94}{\underline{1011110}_2}\)
In [4] Thurber called \(\{179,51,47\}\) and \(\{179,51,94\}\) critical numbers. The idea is that the length of an addition sequence \(l(\{179,51,47\})\) puts an upper limit of the length of an addition chain for \(375494703\). In [5] answer to question 41 Knuth suggests that if the critical numbers were wildly spaced apart then surly an optimal addition chain for a number would entail and optimal addition sequence for its critical numbers.
We find that \(l(\{197,51,47\})=12\) for example \(1, 2, 4, 8, 12, 13, 26, 39, 47, 51, 102, 153, 179\) but \(l(\{197,51,94\}=10\) with \(1, 2, 4, 8, 9, 17, 34, 51, 85, 94, 179\)
[1] Knuth D (1964), "Addition chains and the evaluation of n-th powers", Notices Am Math Soc. Vol. 11, pp. 230-231.
[2] Goulard A (1894), "Question 393", L'Intermédiaire des Mathématiciens. Vol. 1, pp. 234.
[3] de Jonquiéres E (1894), "Question 393 (A. Goulard)", L'Intermédiaire des Mathématiciens. Vol. 2, pp. 125-126.
[4] Thurber EG (1973), "On addition chains \(1(mn)\leq 1(n)-b\) and lower bounds for \(c(r)\)", Duke Mathematical Journal. Vol. 40(4), pp. 907-913. Duke University Press.
[5] Knuth DE (1998), "The art of computer programming, 2: seminumerical algorithms, Addison Wesley", Reading, MA., §4.6.3, pp. 461-485.