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 ≥ 2^r+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 n_s=min{n | s(n) = s} must be one of the c(r) values. Hence c(l(n_s))=n_s. 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