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)\). In general, we can rewrite the Scholz-Brauer conjecture as \(s(2^n-1)\le l(n)\) and this is very helpful in understanding what's being assumed in the conjecture.
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\) and \(s(2^{47}-1)=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
Before building the table above I thought hand checking this addition chain was not realistic. I wrote code to parse the text description above. It validated that the lines \(s,...,e\) have \(e=2^d\cdot s\) and record \(d+1\) elements added to the chain. Lines of the form \(v\) without dots and \(s\) from above we validate are the sum of two prior values read from the text file. These lines contribute only one element to the chain. I used boost cpp_int to do all this.
Achim Flammenkamp kindly validated this and a prior chain and produced his own table with additional information here (for the old larger value): Counter Example Exact Scholz Brauer
This same reasoning is in the following paper that might be easier to read ExactScholzBrauer.pdf.
[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