Collatzova domneva

Iz Wikipedije, proste enciklopedije

Skoči na: navigacija, iskanje
Usmerjeni graf kaže orbite majhnih števil pod Collatzovo preslikavo. Colattzova domneva je enakovredna izjavi, da vse povezave vodijo v 1

Collatzova 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.

Paul 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]

Vsebina

[uredi] Vsebina problema

Za poljubno pozitivno celo število sta na voljo dve operaciji:

  • če je število sodo, ga delimo z 2,
  • če je število liho, ga pomnožimo s 3 in prištejemo 1.

Za 3 je na primer rezultat 10, za 28 pa 14.

V zapisu modularne aritmetike lahko za takšno operacijo podobno določimo funkcijo s predpisom:

f(n) = \begin{cases} n/2 & \; ; \; n \equiv 0 \pmod{2}\\ 3n+1 & \; ; \; n\equiv 1 \pmod{2}\end{cases} \,\! .

S pomočjo te funkcije tvorimo rekurzivno zaporedje. Vzamemo poljubno pozitivno celo število in v naslednjem koraku vzamemo za argument funkcije rezultat prejšnjega koraka:

a_{i} = \begin{cases}n & \; ; \; i = 0 \\ f(a_{i-1}) & \; ; \; i > 0 \end{cases} \,\! .

Colattzova domneva se glasi: tako določeno zaporedje so bo končalo s številom 1, ne glede katero je izbrano prvo število.

[uredi] Zgledi

n Collatzovo 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 Collatzovem problemu največji, so:

2, 3, 6, 7, 9, 18, 25, 27, 54, 73, 97, 129, 171, 231, 313, 327, 649, 703, 871, 1161, 2223, 2463, 2919, 3711, 6171, 10971, 13255, 17647, 23529, 26623, 34239, 35655, 52527, 77031, ...,

razlike pa so:

1, 6, 1, 8, 3, 1, 3, 88, 1, 3, 3, 3, 3, 3, 3, 13, 1, 26, 8, 3, 1, 26, 8, 21, 24, 6, 8, 3, 3, 26, 3, 13, 16, 11, ...

[uredi] Program za računanje Collatzovih zaporedij

Določeno Collatzovo 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 sod
      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 Collatzova 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.)

[uredi] Opombe

  1. ^ Lagarias (1985).
  2. ^ (OEIS A006577)

[uredi] Viri

[uredi] Zunanje povezave


E na i pi  Ta matematični članek je škrbina. Pomagaj Wikipediji in ga razširi.
Vzpostavljeno iz »http://sl.wikipedia.org/wiki/Collatzova_domneva«