\(l(2n) ≤ l(n)\)

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 the optimal addition chains 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\cdot 30958077) = l(4\cdot 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 surely an optimal addition chain for a number would entail an 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.