Collatzův problém

Předmětem tohoto cvičení je matematický problém, který je znám pod mnoha různými názvy – kromě názvu "Collatzův problém" se můžete setkat též s označením "3n+1 problém", "Ulamův problém", "Syrakuský problém" a spoustou dalších jmen. Problém se týká následujícího postupu:

Vezmi přirozené číslo, pokud je sudé, vyděl jej dvěma, pokud je liché, vynásob jej třemi a přičti jedničku. Tento postup opakuj, dokud nedostaneš číslo jedna.

Pokud začneme v čísle `7`, dostaneme následující posloupnost: `22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1` (viz ukázka). Ačkoliv je definice postupu jednoduchá, výsledné chování je velmi zajímavé. Již na příkladu začínajícím v čísle `7` je vidět, že chování vypadá docela "chaoticky". A když začneme číslem `27`, potřebujeme dokonce `111` kroků, než se dostaneme na číslo `1` a jako jeden z mezivýsledků dostaneme číslo `9232`.

Když máme takto definovaný postup, nabízí se následující otázka. "Platí, že ať začneme v libovolném přirozeném čísle, skončí posloupnost v jedničce?" Na tuto otázku zatím nikdo nezná s jistotou odpověď. Experimentálně bylo ověřeno, že i pro velmi vysoká čísla se výpočet nakonec dostane do jedničky, takže většina lidí věří, že hypotéza platí. Nicméně matematický důkaz zatím nemáme a problém je stále otevřený.

Ukázka

Číslo: 7
Posloupnost: | 22 | 11 | 34 | 17 | 52 | 26 | 13 | 40 | 20 | 10 | 5 | 16 | 8 | 4 | 2 | 1 |
Počet: 16

Cvičení

Posloupnost: Pro zadané číslo `n` vypiš posloupnost čísel.
Počet kroků: Pro čísla od `1` do `n` vypiš, kolik kroků je potřeba, než se dostaneš do jedničky.
Maximální hodnota: Nezobrazuj počet kroků, ale maximální hodnotu, na kterou v průběhu výpočtu narazí (např. pro začátek v čísle `7` je touto maximální hodnotou `52`).
Nejvíce kroků: Pro které číslo od `1` do `100000` potřebujeme nejvíce kroků, než dospějeme do jedničky?
Maximální číslo: Jaké je maximální číslo, které se v příslušné posloupnosti objeví?
Rekordmani: Rekordman je takové číslo `x`, pro které je počet potřebných kroků větší než pro jakékoliv `y < x`. Posloupnost rekordmanů začíná `1, 2, 3, 6, 7, 9, 18, 25, 27, 54`. Najdi všechny rekordmany do `100000`.
Modifikace vzorce: Vyzkoušej jiné funkce podobného typu a prozkoumej jejich chování. Co se například stane, když výraz `3n+1` nahradíme za `3n-1`? Pak už uvedená hypotéza neplatí – když začneme ve vhodném čísle, výpočet se zacyklí a nikdy se nedostane do jedničky. Najděte takové číslo.