Hipoteza Collatza

Dzisiaj kolejny z pozoru prosty problem matematyczny, który jeszcze nie znalazł rozwiązania. A prace nad Hipotezą Collatza trwają już ponad 70 lat.

Weźmy dowolną liczbę naturalną c₀. Jest to pierwszy wyraz ciągu określonego rekurencyjnie jako:

                c_n / 2 dla c_n parzystego
c_{n + 1} =
                3 * c_n + 1 dla c_n nieparzystego

Czyli dostaniemy następujące ciągi, w zależności od wyrazu początkowego:

1 → 4 → 2 → 1 → 4 → 2 → 1 → ...
2 → 1 → 4 → 1 → ...
3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 → ...
4 → 2 → 1 → ...
5 → 16 → 8 → 4 → 2 → 1 → ...
6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 → ...

Zazwyczaj jako ostatni wyraz ciągu przyjmuje się jedynkę, ponieważ potem wpada on w pętlę ;) Liczbę elementów poprzedzających jedynkę określa się czasem stopu dla danej wartości pierwszego wyrazu ciągu.

Co zatem tutaj tak ciekawego?

Weźmy ciąg Collatza dla liczby 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

Czas stopu dla liczby 27 to 111 elementów. Największy z nich ma wartość aż 9232. Hipoteza Collatza stwierdza, iż ciąg ten zawsze zakończy się na jedynce - dla każdej liczby naturalnej będącej początkiem ciągu. I właśnie to stwierdzenie przysparza problemów matematykom od ponad 70 lat ;)

Napiszmy prosty program w Pythonie który pokaże dla każdej liczby jej ciąg - od pierwszego elementu do jedynki. Wybrałem ten język, bo nie trzeba żadnej zabawy aby dostać obsługę liczb całkowitych dowolnej precyzji ;)

def collatz_tmp(n, ret):
  ret.append(n)
  if n == 1:
    return ret
  elif n % 2 == 0:
    return collatz_tmp(n >> 1, ret)
  else:
    return collatz_tmp(3*n + 1, ret)

def collatz(n):
  return collatz_tmp(n, [])

Zamiast zwykłego dzielenia wybrałem operację przesunięcia bitowego, ponieważ jako wyniku potrzebowałem liczby całkowitej ;)

Wyliczyłem czas stopu każdej liczby naturalnej od 1 do 40 000 i zapisałem w postaci obrazka 200 na 200 pikseli, gdzie czas stopu jest równy jasności piksela (od 0 do 255, czasy większe "przycinałem" do 255). Numeracja jest normalna - od prawej do lewej wierszami. Cóż, efekt nie powala, a liczyłem na kolejny w tym tygodniu ładny obrazek ;)

Jak widać niezwykle prosty ciąg, prosty algorytm, prosto sformułowany problem, a rozstrzygnięcia brak. Paul Erdős (matematyk węgierski, dzięki amfetaminie i spaniu 4-5 godzin na dobę napisał ponad 1500 artykułów dotyczących matematyki) powiedział o Hipotezie Collatza: "matematyka nie jest jeszcze gotowa na takie problemy".

Istnieje też alternatywne, bardziej życiowe sformułowanie tego problemu:

;)

Więcej: http://en.wikipedia.org/wiki/Collatz_conjecture