Congettura di Scholz
Da Wikipedia, l'enciclopedia libera.
In matematica, la Congettura di Scholz (chiamata anche Congettura di Scholz-Brauer o anche Congettura di Brauer-Scholz) è una congettura formulata nel 1937 che dice:
- l(2n−1) ≤ n − 1 + l(n)
dove l(n) è la lunghezza della più breve delle catene di somme (addition chains) che generano n. È stata verificata per moltissimi casi ma, in generale, rimane un problema aperto.
Per esempio, l(5)=3 (1+1=2, 2+2=4, 4+1=5, e non esistono catene di somme più corte che generino 5) e l(31)=7 (1+1=2, 2+1=3, 3+3=6, 6+6=12, 12+12=24, 24+6=30, 30+1=31, idem), infatti:
- l(25−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:
- l(2n−1) ≤ 2n − 2
[modifica] Collegamenti esterni
[modifica] Bibliografia
- Scholz, A., "Jahresbericht" Deutsche Math. Vereingung 1937 pp. 41-42
- Brauer, A. T., "On addition chains" Bull. Amer. Math. Soc. 1939 pp. 637-739
Portale Matematica: accedi alle voci di Wikipedia che parlano di matematica
