Collatzeva domneva
nerešena domneva v matematiki From Wikipedia, the free encyclopedia
nerešena domneva v matematiki From Wikipedia, the free encyclopedia
Collatzeva domneva je v matematiki nerešena domneva. Prvi jo je leta 1937 postavil Lothar Collatz. Domneva je znana tudi kot domneva 3n + 1, Ulamova domneva (po Stanislawu Marcinu Ulamu), sirakuški problem, kot zaporedje zrn toče ali števila zrn toče, ter po knjigi Gödel, Escher, Bach tudi čudovita števila. Domneva sprašuje ali se določena vrsta številskega zaporedja vedno konča na isti način, ne glede na začetno število.
Erdős je o Collatzevi domnevi dejal: »Matematika še ni pripravljena za takšne probleme.« Ponudil je tudi 500 dolarjev za njeno rešitev.[1]
Za poljubno pozitivno celo število sta na voljo dve operaciji:
Za 3 je na primer rezultat 10, za 28 pa 14.
V zapisu modularne aritmetike se lahko za takšno operacijo podobno določi funkcijo s predpisom:
S pomočjo te funkcije se tvori rekurzivno zaporedje. Vzame se poljubno pozitivno celo število in v naslednjem koraku vzame za argument funkcije rezultat prejšnjega koraka:
Colattzova domneva se glasi: tako določeno zaporedje so bo končalo s številom 1, ne glede katero je izbrano prvo število.
n | Collatzevo zaporedje | št. korakov[2] |
---|---|---|
1 | 1 | 0 |
2 | 2, 1 | 1 |
3 | 3, 10, 5, 16, 8, 4, 2, 1 | 7 |
4 | 4, 2, 1 | 2 |
5 | 5, 16, 8, 4, 2, 1 | 5 |
6 | 6, 3, 10, 5, 16, 8, 4, 2, 1 | 8 |
7 | 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 | 16 |
8 | 8, 4, 2, 1 | 3 |
9 | 9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 | 19 |
10 | 10, 5, 16, 8, 4, 2, 1 | 6 |
11 | 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 | 14 |
18 | 18, 9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 | 20 |
25 | 25, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 | 23 |
27 | 27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1 | 111 |
Prva števila, ko je razvoj v Collatzevem problemu največji, so (OEIS A006877):
razlike pa so:
Določeno Collatzevo zaporedje je lahko izračunati kot kaže tudi algoritem, zapisan v psevdokodi:
funkcija collatz(n) dokler n > 1 prikaži n če n je lih priredi n vrednost 3*n + 1 drugače priredi n vrednost n / 2 prikaži n
Program se konča, ko zaporedje doseže 1, drugače bi v nedogled ponavljal cikel 4, 2, 1. Če je Collatzeva domneva pravilna, se bo program vedno ustavil, ne glede na začetno pozitivno celo število. (Glej Haltingov problem za povezavo med računalniškimi programi v končnem in nerešenimi matematičnimi problemi.)