Scholz conjecture
In mathematics, the Scholz conjecture sometimes called the Scholz–Brauer conjecture or the Brauer–Scholz conjecture (named after A. Scholz and Alfred T. Brauer), is a conjecture from 1937 stating that
- l(2n − 1) ≤ n − 1 + l(n) where l(n) is the length of the shortest addition chain producing n. N. Clift checked this by computer for n ≤ 46.
As an example, l(5) = 3 (since 1 + 1 = 2, 2 + 2 = 4, 4 + 1 = 5, and there is no shorter chain) and l(31) = 7 (since 1 + 1 = 2, 2 + 1 = 3, 3 + 3 = 6, 6 + 6 = 12, 12 + 12 = 24, 24 + 6 = 30, 30 + 1 = 31, and there is no shorter chain), so
- l(25−1) = 5 − 1 + l(5).
Brauer proved that
- l*(2n−1) ≤ n − 1 + l*(n)
where l* is the length of the shortest star chain (an addition chain where every element of the chain is the sum of its predecessor and some other element). For many values of n,and in particular for n ≤ 2500, they are equal: l(n) = l*(n). But Hansen showed that there are some values of n for which l(n) ≠ l*(n), such as n = 26106 + 23048 + 22032 + 22016 + 1 which has l*(n) = 6110, l(n) ≤ 6109.
[edit] References
- Scholz, Arnold (1937), "Aufgaben und Lösungen, 253", Jahresbericht der Deutschen Mathematiker-Vereinigung 47: 41–42, ISSN 0012-0456, http://resolver.sub.uni-goettingen.de/purl?GDZPPN002132214
- Brauer, Alfred (1939), "On addition chains", Bulletin of the American Mathematical Society 45 (10): 736–739, doi:10.1090/S0002-9904-1939-07068-7, ISSN 0002-9904, MR0000245
