Exact Equality in the Scholz-Brauer Conjecture

For mathematical definitions see the top-level Addition Chains.

The Scholz-Brauer conjecture says that \(l(2^n-1)\le l(n)+n-1\). For all the explicitly calculated \(l(2^n-1)\) values we find equality \(l(2^n-1)=l(n)+n-1\). Knuth [1] asks in the last question (question 34 later moving to question 43 in later additions):

34. [M50] Is \(l(2^n-1)\le n-1+l(n)\) for all positive integers \(n\)? Does equality hold? Does \(l(n)=l^0(n)\)?

Equality seems to have been noted first by Kenneth Stolarsky [2], who at the time did what he called tedious hand calculations for \(n\le 8\).

We now know the first non-Hansen number (5784689) dispensed with part 3 of that question. Could we use some hackary to find an example of \(l(2^n-1)< l(n)+n-1\)?
Maybe we can find an addition chain for some smaller value of \(2^m-1, m<n\) that has some nice properties that might help us build a good addition chain for \(2^n-1\). To keep things simple, let us consider only the terms in an addition chain of \(2^m-1\) of the form \(2^d\cdot(2^r-1)\) and record the \(r\) values. We can call these 'interesting' values as they are good building blocks in chains. For example, if \(m=12\) we have the following chain:

1 2 4 6 7 14 21 42 63 126 252 504 1008 2016 4032 4095
1       2 3   3             6     6     6     6       6       6       6     12

We color the entries red that are interesting and are first with a particular \(r\) value. We list the \(r\) values below the entries above. The \(r\) values when duplicates are removed form an addition chain (1 2 3 6 12) but this is not always true. Note that \(s(2^{4096}-1)=l(12)\).

Could we find an addition chain for \(2^m-1\) that had \(r\) values that generate an impossible chain? By this we mean that \(l(\{r_1,...,r_q\})>s(2^m-1)\) were \(r_i,1\le i\le q\) are the \(r\) values. Searching all addition chains for small values of \(m\) we find the following chain for \(2^{47}-1\):

1, 2, 3, 6, 12, 24, 30, 60, 120, 240, 480, 483, 963, 1926, 3852, 7704, 8187, 8189, 16376, 32752, 65504, 131008, 262016, 524032, 1048064, 2096128, 4192256, 8384512, 16769024, 16777213, 16777215, 33554428, 67108856, 134217712, 268435424, 536870848, 1073741696, 2147483392, 4294966784, 8589933568, 17179867136, 34359734272, 68719468544, 137438937088, 274877874176, 549755748352, 1099511496704, 2199022993408, 4398045986816, 8796091973632, 17592183947264, 35184367894528, 70368735789056, 140737471578112, 140737488355327

It's corresponding \(r\) values are 1, 2, 4, 11, 23, 24, 47. Now \(l(47)=8\) but no optimal addition chains for 47 contains both the value 11 and 24. So \(l(\{1,2,4,11,23,24,47\})> 8\) and we have a set of impossible building blocks that might help us here. We have an alternate chain with \(l(\{1,2,8,11,23,24,47\})> 8\) but that doesn't seem to add anything beyond what the first does. In fact, we seem to get all we need by just using 11 and 23 or 24 or both.
So, if we assume an addition chain for \(n\) starts 1 ... 11 ... 23, 24, ... 47 and somehow it was done in an impossible 8 steps and the rest of the chain only uses the values 11, 23, 24, and 47 could we get to some \(n\) in a total of \(l(n)-1\) steps? The answer is yes for the many values including 9307543:

1, 2, ?, ?, 11 ?, 23, 24, 47, 71, 142, 284, 568, 1136, 2272, 4544, 9088, 18176, 36352, 36363, 72715, 145430, 290860, 581720, 1163440, 2326880, 4653760, 4653783, 9307543

Here we get to 9307543 in 28 steps (albeit with some question marks to pad out the start). We know though that \(l(9307543)=29\). We now try to convert this to a chain for \(2^{9307543} -1\) using the chain for \(2^{47}-1\) above at the start. Starting the chain this way, we remove the need to consider what those question marks represented above. We have to reorder some doubling steps as we don't have \(2^{11}-1\) in our chain but instead \(8\cdot (2^{11}-1)\). We do have both \(2^{24}-1\) and \(2^{47}-1\) as building blocks though.

Elements How First Element Formed Elements In Row Chain Length So Far
1 1 0
2 \(1+1\) 1 1
3 \(2+1\) 1 2
6,...,24 \(3+3\) 3 5
\(2\cdot (2^4-1),...,2^5\cdot (2^4-1)\) \(24+6\) 5 10
483 \(2^5\cdot  (2^4 - 1)+3\) 1 11
\(963,...,2^3\cdot 963\) \(483 + 2^5\cdot (2^4-1)\) 4 15
8187 \(2^3\cdot 963 + 483\) 1 16
8189 \(8187 + 2\) 1 17
\(2^3\cdot (2^{11}-1),...,2^{13}\cdot (2^{11}-1)\) \(8189 + 8187\) 11 28
16777213 \(2^{13}\cdot (2^{11}-1) + 8189\) 1 29
\(2^{24}-1\) \(16777213 + 2\) 1 30
\(2^2\cdot (2^{23}-1),...,2^{24}\cdot (2^{23}-1)\) \(2^{24}-1 + 16777213\) 23 53
\(2^{47}-1,...,2^{24}\cdot (2^{47}-1)\) \(2^{24} \cdot (2^{23}-1)+2^{24}-1\) 25 78
\(2^{71}-1,...,2^{71}\cdot (2^{71}-1)\) \(2^{24} \cdot (2^{47}-1)+2^{24}-1\) 72 150
\(2^{142}-1,...,2^{142}\cdot (2^{142}-1)\) \(2^{71} \cdot (2^{71}-1)+2^{71}-1\) 143 293
\(2^{284}-1,...,2^{284}\cdot (2^{284}-1)\) \(2^{142} \cdot (2^{142}-1)+2^{142}-1\) 285 578
\(2^{568}-1,...,2^{568}\cdot (2^{568}-1)\) \(2^{284} \cdot (2^{284}-1)+2^{284}-1\) 569 1147
\(2^{1136}-1,...,2^{1136}\cdot (2^{1136}-1)\) \(2^{568} \cdot (2^{568}-1)+2^{568}-1\) 1137 2284
\(2^{2272}-1,...,2^{2272}\cdot (2^{2272}-1)\) \(2^{1136} \cdot (2^{1136}-1)+2^{1136}-1\) 2273 4557
\(2^{4544}-1,...,2^{4544}\cdot (2^{4544}-1)\) \(2^{2272} \cdot (2^{2272}-1)+2^{2272}-1\) 4545 9102
\(2^{9088}-1,...,2^{9088}\cdot (2^{9088}-1)\) \(2^{4544} \cdot (2^{4544}-1)+2^{4544}-1\) 9089 18191
\( 2^{18176}-1,...,2^{18176}\cdot (2^{18176}-1)\) \(2^{9088} (2^{9088}-1)+ 2^{9088}-1\) 18177 36368
\(2^{36352}-1,...,2^{14}\cdot (2^{36352}-1)\) \(2^{18176}\cdot (2^{18176}-1)+2^{18176}-1\) 15 36383
\(2^3\cdot (2^{36363}-1),...,2^{36352}\cdot (2^{36363}-1)\) \(2^{14} \cdot (2^{36352}-1)+  2^3\cdot (2^{11}-1)\) 36350 72733
\(2^{72715}-1,...,2^{72715}\cdot (2^{72715}-1)\) \(2^{36352}\cdot (2^{36363}-1)+2^{36352}-1\) 72716 145449
\(2^{145430}-1,...,2^{145430}\cdot (2^{145430}-1)\) \(2^{72715} \cdot (2^{72715}-1)+2^{72715}-1\) 145431 290880
\(2^{290860}-1,...,2^{290860}\cdot (2^{290860}-1)\) \(2^{145430} \cdot  (2^{145430}-1)+ 2^{145430}-1\) 290861 581741
\(2^{581720}-1,...,2^{581720}\cdot (2^{581720}-1)\) \(2^{290860} \cdot (2^{290860}-1)+2^{290860}-1\) 581721 1163462
\(2^{1163440}-1,...,2^{1163440}\cdot (2^{1163440}-1)\) \(2^{581720} \cdot (2^{581720}-1)+2^{581720}-1\) 1163441 2326903
\(2^{2326880}-1,...,2^{2326880}\cdot (2^{2326880}-1)\) \(2^{1163440} \cdot(2^{1163440}-1)+2^{1163440}-1\) 2326881 4653784
\(2^{4653760}-1,...,2^{25}\cdot(2^{4653760}-1)\) \(2^{2326880} \cdot(2^{2326880}-1)+2^{2326880}-1\) 26 4653810
\(2^2\cdot(2^{4653783}-1),...,2^{4653760}\cdot(2^{4653783}-1)\) \(2^{25} \cdot(2^{4653760}-1)+2^2\cdot(2^{23}-1)\) 4653759 9307569
\(2^{9307543}-1\) \(2^{4653760} \cdot(2^{4653783}-1)+2^{4653760}-1\) 1 9307570

So, we have \(l(2^{9307543}-1)\le 9307570<l(9307543)+9307543-1=29+9307543-1=9307571\).

The following sequence may be easier to process if you want to check this via a computer program. In each group of doubling steps (shown with ,...,) only the first and last values can ever be used in the rest of the chain. So, you can avoid generating them otherwise the memory usage is too big.

1,
2,
3,
6,...,24,
2*(2^4-1),...,480,
483,
963,...,7704,
8187,
8189,
2^3*(2^11-1),...,2^13*(2^11-1),
16777213,
2^24-1,
2^2*(2^23-1),...,2^24*(2^23-1),
2^47-1,...,2^24*(2^47-1),
2^71-1,...,2^71*(2^71-1),
2^142-1,...,2^142*(2^142-1),
2^284-1,...,2^284*(2^284-1),
2^568-1,...,2^568*(2^568-1),
2^1136-1,...,2^1136*(2^1136-1),
2^2272-1,...,2^2272*(2^2272-1),
2^4544-1,...,2^4544*(2^4544-1),
2^9088-1,...,2^9088*(2^9088-1),
2^18176-1,...,2^18176*(2^18176-1),
2^36352-1,...,2^14*(2^36352-1),
8*(2^36363-1),...,2^36352*(2^36363-1),
2^72715-1,...,2^72715*(2^72715-1),
2^145430-1,...,2^145430*(2^145430-1),
2^290860-1,...,2^290860*(2^290860-1),
2^581720-1,...,2^581720*(2^581720-1),
2^1163440-1,...,2^1163440*(2^1163440-1),
2^2326880-1,...,2^2326880*(2^2326880-1),
2^4653760-1,...,2^25*(2^4653760-1),
4*(2^4653783-1),...,2^4653760*(2^4653783-1),
2^9307543-1

Achim Flammenkamp kindly validated the chain above and produced his own table with additional information here: Counter Example Exact Scholz Brauer

[1] Knuth DE (1969), "The art of computer programming, 2: seminumerical algorithms, Addison Wesley", Reading, MA., §4.6.3, pp. 422
[2] Stolarsky, Kenneth B. A lower bound for the Scholz-Brauer problem 1969 Canadian J. Math , Vol. 21 p. 675-683