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, we have a set of impossible building blocks that might help us here.
So, if we assume an addition chain for \(n\) starts 1 ... 11 ... 24 ... 47 and somehow it was done in an impossible 8 steps and the rest of the chain only uses the values 11, 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 30978119:

1, 2, ?, ?, ?, 11, ?, 24, 47, 71, 118, 236, 472, 944, 1888, 3776, 7552, 7563, 15126, 30252, 60504, 121008, 242016, 484032, 968064, 1936128, 3872256, 7744512, 15489024, 30978048, 30978119

Here we get to 30978119 in 30 steps (albeit with some question marks to pad out the start). We know though that \(l(30978119)=31\). We now try to convert this to a chain for \(2^{30978119} -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^{47}\cdot (2^{71}-1)\) \(2^{24} \cdot (2^{47}-1)+2^{24}-1\) 48 126
\(2^{118}-1,...,2^{118}\cdot (2^{118}-1)\) \(2^{47} \cdot (2^{71}-1)+2^{47}-1\) 119 245
\(2^{236}-1,...,2^{236}\cdot (2^{236}-1)\) \(2^{118} \cdot (2^{118}-1)+2^{118}-1\) 237 482
\(2^{472}-1,...,2^{472}\cdot (2^{472}-1)\) \(2^{236} \cdot (2^{236}-1)+2^{236}-1\) 473 955
\(2^{944}-1,...,2^{944}\cdot (2^{944}-1)\) \(2^{472} \cdot (2^{472}-1)+2^{472}-1\) 945 1900
\(2^{1888}-1,...,2^{1888}\cdot (2^{1888}-1)\) \(2^{944} \cdot (2^{944}-1)+2^{944}-1\) 1889 3789
\(2^{3776}-1,...,2^{3776}\cdot (2^{3776}-1)\) \(2^{1888} \cdot (2^{1888}-1)+2^{1888}-1\) 3777 7566
\(2^{7552}-1,...,2^{14}\cdot (2^{7552}-1)\) \(2^{3776} \cdot (2^{3776}-1)+2^{3776}-1\) 15 7581
\(8\cdot (2^{7563}-1),...,2^{7566}\cdot (2^{7563}-1)\) \(2^{14} (2^{7552}-1)+2^3 \cdot (2^{11}-1)\) 7564 15145
\(8\cdot (2^{15126}-1),...,2^{15129}\cdot (2^{15126}-1)\) \(2^{7566}\cdot (2^{7563}-1)+8\cdot  (2^{7563}-1)\) 15127 30272
\(8\cdot (2^{30252}-1),...,2^{30255}\cdot (2^{30252}-1)\) \(2^{15129} \cdot (2^{15126}-1)+8\cdot  (2^{15126}-1)\) 30253 60525
\(8\cdot (2^{60504}-1),...,2^{60507}\cdot (2^{60504}-1)\) \(2^{30255} \cdot (2^{30252}-1)+8 \cdot (2^{30252}-1)\) 60505 121030
\(8\cdot (2^{121008}-1),...,2^{121011}\cdot (2^{121008}-1)\) \(2^{60507} \cdot (2^{60504}-1)+8 \cdot (2^{60504}-1)\) 121009 242039
\(8\cdot (2^{242016}-1),...,2^{242019}\cdot (2^{242016}-1)\) \(2^{121011} \cdot  (2^{121008}-1)+8 \cdot(2^{121008}-1)\) 242017 484056
\(8\cdot (2^{484032}-1),...,2^{484035}\cdot (2^{484032}-1)\) \(2^{242019} \cdot (2^{242016}-1)+8 \cdot (2^{242016}-1)\) 484033 968089
\(8\cdot (2^{968064}-1),...,2^{968067}\cdot (2^{968064}-1)\) \(2^{484035} \cdot (2^{484032}-1)+8 \cdot(2^{484032}-1)\) 968065 1936154
\(8\cdot(2^{1936128}-1),...,2^{1936131}\cdot (2^{1936128}-1)\) \(2^{968067} \cdot(2^{968064}-1)+8 \cdot(2^{968064}-1)\) 1936129 3872283
\(8\cdot(2^{3872256}-1),...,2^{3872259}\cdot(2^{3872256}-1)\) \(2^{1936131} \cdot(2^{1936128}-1)+8 \cdot(2^{1936128}-1)\) 3872257 7744540
\(8\cdot(2^{7744512}-1),...,2^{7744515}\cdot(2^{7744512}-1)\) \(2^{3872259} \cdot(2^{3872256}-1)+8 \cdot(2^{3872256}-1)\) 7744513 15489053
\(8\cdot(2^{15489024}-1),...,2^{15489027}\cdot(2^{15489024}-1)\) \(2^{7744515} \cdot(2^{7744512}-1)+8 \cdot(2^{7744512}-1)\) 15489025 30978078
\(8\cdot(2^{30978048}-1),...,2^{71}\cdot(2^{30978048}-1)\) \(2^{15489027} \cdot(2^{15489024}-1)+8 \cdot(2^{15489024}-1)\) 69 30978147
\(2^{30978119}-1\) \(2^{71} \cdot(2^{30978048}-1)+2^{71}-1\) 1 30978148

So, we have \(l(2^{30978119}-1)\le 30978148<l(30978119)+30978119-1=30978149\).

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. Even if we only save the exact number of bits for each value in the addition chain, we need 54.5TB of memory to save it all.

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^47*(2^71-1),
2^118-1,...,2^118*(2^118-1),
2^236-1,...,2^236*(2^236-1),
2^472-1,...,2^472*(2^472-1),
2^944-1,...,2^944*(2^944-1),
2^1888-1,...,2^1888*(2^1888-1),
2^3776-1,...,2^3776*(2^3776-1),
2^7552-1,...,2^14*(2^7552-1),
8*(2^7563-1),...,2^7566*(2^7563-1),
8*(2^15126-1),...,2^15129*(2^15126-1),
8*(2^30252-1),...,2^30255*(2^30252-1),
8*(2^60504-1),...,2^60507*(2^60504-1),
8*(2^121008-1),...,2^121011*(2^121008-1),
8*(2^242016-1),...,2^242019*(2^242016-1),
8*(2^484032-1),...,2^484035*(2^484032-1),
8*(2^968064-1),...,2^968067*(2^968064-1),
8*(2^1936128-1),...,2^1936131*(2^1936128-1),
8*(2^3872256-1),...,2^3872259*(2^3872256-1),
8*(2^7744512-1),...,2^7744515*(2^7744512-1),
8*(2^15489024-1),...,2^15489027*(2^15489024-1),
8*(2^30978048-1),...,2^71*(2^30978048-1),
2^30978119-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