c(r) and d(r)

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

 

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

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