The Scholz conjecture, also called the Scholz-Brauer conjecture, is a conjecture on the length of certain addition chains. It was formulated by Arnold Scholz in 1937, and Alfred Brauer studied it soon afterward and proved a weaker bound; Neill Clift has announced an example showing that the bound of the conjecture is not always tight. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Statementl(2^n - 1) <= n - 1 + l(n), where l(n) is the length of the shortest addition chain producing n. 1 Proposed Year Progress Toward ResolutionClift (2011) showed by computer search that the conjecture is true for all n < 5784689, and that for all n <= 64 the inequality is actually an equality. The bound is not always exact: for n = 9307543 the inequality is strict. 1 Classification
Resolution Status Prize Status
Prize Status (category) Sources
1. Scholz Conjecture (Wikipedia)
Wikimedia FoundationLead section
after Arnold Scholz, who formulated it in 1937
Statement section
where l(n) is the length of the shortest addition chain producing n.
Partial results section
By using a combination of computer search techniques and mathematical characterizations of optimal addition chains, Clift (2011) showed that the conjecture is true for all n < 5784689.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.