Collatzeva domneva

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]

Vsebina problema

Histogram števila korakov za števila od 1 do 100 milijonov. Število korakov je na osi x, frekvenca pa na osi y.

Števila od 1 do 9999 in njim pripadajoča števila korakov

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

• če je število sodo, se ga deli z 2,
• če je število liho, se ga pomnoži s 3 in prišteje 1.

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:

${\displaystyle 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 se tvori rekurzivno zaporedje. Vzame se poljubno pozitivno celo število in v naslednjem koraku vzame za argument funkcije rezultat prejšnjega koraka:

${\displaystyle 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.

Zgledi

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):

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

Program za računanje Collatzevih zaporedij

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

Vizualizacije

• 
  Usmerjeni graf kaže orbite majhnih števil pod Collatzovo preslikavo. Colattzova domneva je enakovredna izjavi, da vse povezave vodijo v 1.
• 
  Usmerjeni graf kaže orbite prvih 1000 števil.
• 
  Os x predstavlja začetno število, os y pa najvišje doseženo število med veriženjem do  1.

Sklici

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

Viri

• Jeffrey Clark Lagarias. The 3x + 1 problem: An annotated bibliography (1963--2000).
• Jeffrey Clark Lagarias. The 3x + 1 problem: An annotated bibliography, II (2001--).
• Jeffrey Clark Lagarias. The 3x + 1 problem and its generalizations, American Mathematical Monthly Volume 92, 1985, pp. 3 - 23.
• Jeffrey Clark Lagarias: Syracuse problem na Springer Online Encyclopaedia of Mathematics (angleško)
• Günther J. Wirsching. The Dynamical System Generated by the ${\displaystyle 3n+1}$ Function. Number 1681 in Lecture Notes in Mathematics. Springer-Verlag, 1998.
• An ongoing distributed computing project by Eric Roosendaal verifies the Collatz conjecture for larger and larger values.
• Another ongoing distributed computing project by Tomás Oliveira e Silva continues to verify the Collatz conjecture (with fewer statistics than Eric Roosendaal's page but with further progress made).
• Hailstone Patterns discusses different resonators along with using important numbers in the problem (like 6 and 3^5) to discover patterns.
• Review of progress, plus various programs
• Ohira, Reiko & Yamashita, Michinori A generalization of the Collatz problem Arhivirano 2008-04-06 na Wayback Machine.
• URATA, Toshio Some Holomorphic Functions connected with the Collatz Problem Arhivirano 2008-04-06 na Wayback Machine.
• Matti K. Sinisalo: On the minimal cycle lengths of the Collatz sequences, Preprint, June 2003, University of Oulu
• Paul Stadfeld: Blueprint for Failure: How to Construct a Counterexample to the Collatz Conjecture Arhivirano 2007-09-26 na Wayback Machine.

Zunanje povezave

• Weisstein, Eric Wolfgang. »Collatz Problem«. MathWorld.
• Collatzov problem Arhivirano 2007-07-14 na Wayback Machine. na PlanetMath (angleško)