Conjectura lui Scholz

În matematică , conjectura Scholz (numită și conjectura Scholz-Brauer sau, de asemenea, conjectura Brauer-Scholz ) este o conjectură formulată în 1937 care spune:

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

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

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

unde l (n) este lungimea celui mai scurt lanț de sume (lanț de adunare) care generează n. Conjectura a fost verificată pentru multe cazuri, dar, în general, rămâne o problemă deschisă.

De exemplu, condiția este verificată în cazul n = 5, de fapt l (5) = 3 (cel mai scurt lanț care generează 5 este 1 + 1 = 2, 2 + 2 = 4, 4 + 1 = 5) și l (31) = 7 (cel mai scurt lanț este 1 + 1 = 2, 2 + 1 = 3, 3 + 3 = 6, 6 + 6 = 12, 12 + 12 = 24, 24 + 6 = 30, 30 + 1 = 31) și avem

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

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

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

Raționamentul simplu despre natura lanțurilor de sume și reprezentarea binară a unui număr ne permite să arătăm cea mai slabă inegalitate:

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

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

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

linkuri externe

Achim Flammenkamp, cele mai scurte lanțuri de adăugare
Secvența A003313 a OEIS- Enciclopedia on-line a secvențelor întregi care indică lungimea celor mai scurte lanțuri de sume

Bibliografie

( DE ) Arnold Scholz, Aufgaben und Lösungen , în Jahresbericht der Deutschen Mathematiker-Vereinigung , vol. 47, 1937, pp. 41,42, ISSN 0012-0456 ( WC ACNP ) . Adus la 6 noiembrie 2012 .
( EN ) Alfred Brauer, Despre lanțurile adiționale , în Buletinul Societății Americane de Matematică , vol. 45, n. 10, AMS , 1939, pp. 736–739, DOI :10.1090 / S0002-9904-1939-07068-7 , ISSN 0002-9904 ( WC ACNP ) , MR 0000245 .

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică