Congettura Di Scholz

${\displaystyle l(2^{n}-1)\leq n-1+l(n),}$

dove l(n) è la lunghezza della più breve catena di somme (addition chain) che genera n. La congettura è stata verificata per moltissimi casi ma, in generale, rimane un problema aperto.

Per esempio, la condizione è verificata nel caso n = 5, infatti l(5)=3 (la catena più corta che genera 5 è 1+1=2, 2+2=4, 4+1=5) e l(31)=7 (la catena più corta è 1+1=2, 2+1=3, 3+3=6, 6+6=12, 12+12=24, 24+6=30, 30+1=31) e si ha

${\displaystyle l(2^{5}-1)=5-1+l(5).}$

Semplici ragionamenti sulla natura delle catene di somme e la rappresentazione binaria di un numero consentono di mostrare la disuguaglianza più debole:

${\displaystyle l(2^{n}-1)\leq 2n-2.}$

• (DE) Arnold Scholz, Aufgaben und Lösungen, in Jahresbericht der Deutschen Mathematiker-Vereinigung, vol. 47, 1937, pp. 41,42, ISSN 0012-0456 (WC · ACNP). URL consultato il 6 novembre 2012.
• (EN) Alfred Brauer, On addition chains, in Bulletin of the American Mathematical Society, vol. 45, n. 10, AMS, 1939, pp. 736–739, DOI:10.1090/S0002-9904-1939-07068-7, ISSN 0002-9904 (WC · ACNP), MR 0000245.

• Achim Flammenkamp, Shortest Addition Chains
• Sequenza A003313 della OEIS-On-Line Encyclopedia of Integer Sequences che indica la lunghezza delle più brevi catene di somme

  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica