Problem Collatza

Z Wikipedii

Problem Collatza (znany też jako problem 3x+1, problem Ulama) to nie rozstrzygnięty dotychczas (i nie wiadomo, czy w ogóle rozstrzygalny) problem o wyjątkowo prostym – jak wiele innych problemów teorii liczb – sformułowaniu. Nazwa pochodzi od nazwiska niemieckiego matematyka Lothara Collatza (1937). Zagadnienie to było również rozpatrywane przez polskiego matematyka Stanisława Ulama.

Spis treści

1 Definicja
2 Przykłady
3 Problem Collatza jako hipoteza
4 Uogólnienie problemu Collatza na liczby całkowite ujemne
5 Próba rozwiązania problemu
6 Zobacz też
7 Linki zewnętrzne

[edytuj] Definicja

Weźmy dowolną liczbę naturalną c₀ (większą od 0). Jeśli jest ona parzysta, to za c₁ przyjmijmy c₀/2, w przeciwnym wypadku niech c₁=3c₀ + 1. Następnie, z liczbą c₁ postępujemy podobnie jak z c₀ i kontynuujemy ten proces. Otrzymamy w ten sposób ciąg liczb naturalnych określony rekurencyjnie przez formułę

${c_{n+1}} = \left\{ \begin{matrix} \frac{1}{2}c_n & \mbox{gdy } c_n \mbox{ jest parzysta}\\ 3c_n + 1 & \mbox{gdy } c_n \mbox{ jest nieparzysta} \end{matrix} \right.$

Hipoteza Collatza stwierdza, że niezależnie od jakiej liczby $c 0$ wystartujemy, w końcu dojdziemy do liczby 1.

[edytuj] Przykłady

Zaczynając od n = 11 mamy,

11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

Zaczynając od n = 27 mamy,

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

dla n = 27 cały proces zajmuje aż 111 kroków z maksymalną wartością 9232.

[edytuj] Problem Collatza jako hipoteza

Wykazano prawdziwość hipotezy Collatza dla liczb c₀ aż do 3×2⁵³ (prawie 2.70216 × 10¹⁶). Granicę tę w lutym 2004r. przesunięto do 2⁵⁸ (ponad 2.8823 × 10¹⁷), jednak dla ogólnego przypadku problem nadal pozostaje nierozstrzygnięty.

Są dwa możliwe warianty rozwiązania negatywnego:

ciąg c wpada w cykl;
ciąg c jest rozbieżny do nieskończoności.

Paul Erdős wypowiedział o problemie Collatza słynne zdanie: "mathematics is not yet ready for such problems" - "matematyka nie jest jeszcze gotowa na takie problemy". Niewątpliwie świadczy to o złożoności ewentualnego rozwiązania, z drugiej strony kontrast pomiędzy ową złożonością a prostotą sformułowania jest intrygujący.