c(r) and d(r)

For mathematical definitions see the top-level Addition Chains.

c(r) must be a strictly increasing function (c(r+1) > c(r)). To see this, we will assume the smallest counter example is r+1 so that c(r+1) < c(r). We have c(0) < c(1) from the table below so we may assume r > 0.

If we now construct the found set f = {n | l(n) ≤ r}f is finite, since if a target m ≥ 2r+1 then l(m) ≥ r + 1. We now find the smallest unfound target u = min{n | l(n) > r}. We must have u - 1 ∈ f and hence l(u-1) ≤ r otherwise u is not the smallest unfound target.

We must have l(m-1) = r since if l(m-1) < r we would have l(m) ≤ l(m-1) + 1 < r + 1 implying m ∈ f which is a contradiction. Hence, we arrive at the contradiction that c(r) ≤ m - 1 < c(r+1).

Achim Flammenkamp proved that the target ns=min{n | s(n) = s} must be one of the c(r) values. Hence c(l(ns))=ns. See [1] the answer to question 27 in §4.6.3. The short proof contained a bracketing error.

 Smallest Target to have an Optimal Addition Chain of Length r
r c(r) s(c(r)) r c(r) s(c(r)) r c(r) s(c(r)) r c(r) s(c(r)) r c(r) s(c(r))
0 1 0 11 191 4 22 110591 6 33 89209343 7 44 76086635263 8
1 2 0 12 379 4 23 196591 6 34 155691199 7 45 142771387391 8
2 3 1 13 607 4 24 357887 6 35 298695487 7 46 257661019487 9
3 5 1 14 1087 4 25 685951 6 36 550040063 7 47 498691112447 9
4 7 2 15 1903 5 26 1176431 6 37 994660991 8
5 11 2 16 3583 5 27 2211837 6 38 1886023151 8
6 19 2 17 6271 5 28 4169527 7 39 3502562143 8
7 29 3 18 11231 5 29 7624319 7 40 6490123999 8
8 47 3 19 18287 5 30 14143037 7 41 11889505663 8
9 71 4 20 34303 5 31 25450463 7 42 22899028607 8
10 127 4 21 65131 6 32 46444543 7 43 41866170239 8

Knuth mentions that there is no clear way to prove d(r+1) ≥ d(r).

1903

How Many Targets have Optimal Addition Chains of Length r
r d(r) r d(r) r d(r) r d(r) r d(r)
0 1 11 246 22 165432 33 140588339 44 130579657981
1 1 12 432 23 303475 34 261070184 45 243724383149
2 2 13 772 24 558275 35 485074788
3 3 14 1382 25 1028508 36 901751654
4 5 15 2481 26 1896704 37 1677060520
5 9 16 4490 27 3501029 38 3119775195
6 15 17 8170 28 6465774 39 5804404206
7 26 18 14866 29 11947258 40 10804952217
8 44 19 27128 30 22087489 41 20125814259
9 78 20 49544 31 40886910 42 37516452013
10 136 21 90371 32 75763102 43 69977286336

Knuth [2] says that for c(r) values "The computation of l(n) seems to be hardest for this sequence of n's". This leads some authors to think that finding optimal chains for c(r) values is hard. In fact, this is not the case. If you know l(c(r)) then finding chains appears to be easy as they have very large numbers of chains. What is hard is proving that there is no chain shorter than l(c(r)). The following tables shows numbers h(r) that have the highest search times for proving l(n)=r based on the subproblem pop count suggested by Thurber. The program does not use graph reduction but instead prunes via the dual (vector addition chain at the end of a partial chain). It finds all chains (calculates NMC(n)).

r c(r) Pops(c(r)) h(r) Pops(h(r))
0 1 0 1 0
1 2 1 2 1
2 3 2 3,4 2
3 5 5 6 6
4 7 16 7 16
5 11 53 11 53
6 19 110 22 156
7 29 476 29 476
8 47 865 58 1422
9 71 5234 71 5234
10 127 11638 142 18229
11 191 54414 191 54414
12 379 70613 508 94759
13 607 306734 607 306734
14 1087 761161 1214 1155982
15 1903 2010962 2174 2844044
16 3583 3064627 3806 7517918
17 6271 11567039 7612 17392079
18 11231 30540731 12662 49508021
19 18287 196564529 18287 196564529

With additional pruning. For example, using the Knuth-Stolarsky conjecture by enumerating the dual chain possibilities and filtering out those that have too many bits etc. We also stop when we find the first addition chain for n so we are just calculating l(n) we can search further:

r c(r) Pops(c(r)) h(r) Pops(h(r))
0 1 0 1 0
1 2 1 2 1
2 3 2 3,4 2
3 5 3 5,6,8 3
4 7 4 7,9,10,12,16 4
5 11 5 11,13,14,15,17,18,20,24,32 5
6 19 6 19,21,22,23,25,26,27,28,... 6
7 29 9 29 9
8 47 8 58 13
9 71 15 116 17
10 127 18 142 27
11 191 61 191,382 61
12 379 69 474 78
13 607 171 753 186
14 1087 290 1214 451
15 1903 582 2298 910
16 3583 578 4218 2447
17 6271 1486 8436 4838
18 11231 3898 12261 8706
19 18287 17721 20437 22218
20 34303 27167 37630 56457
21 65131 67188 75260 115850
22 110591 107849 122253 269880

[1] Knuth DE (1998), "The art of computer programming, 2: seminumerical algorithms, Addison Wesley", Reading, MA. , pp. 461-485.

[2] Knuth DE (1998), "The art of computer programming, 2: seminumerical algorithms, Addison Wesley", Reading, MA. , pp. 477