Mistrzostwa Polski Szkół Średnich w Programowaniu Zespołowym 2024
Problem description
Rozpatrzmy ciąg liczbowy zaczynający się od liczby N. Kolejne wyrazy tego ciągu otrzymujemy za pomocą zaaplikowania prostej reguły. Jeśli poprzedni wyraz był parzysty to kolejny jest jego połową. Jeśli zaś był nieparzysty to kolejny jest jego trzykrotnością powiększoną o jeden.
Pytanie, na które nadal nie znamy odpowiedzi brzmi: czy dla dowolnego początkowego wyrazu ciągu (wartości N) zawsze po pewnej skończonej liczbie kroków uzyskamy liczbę 1?
Paul Erdos (węgierski matematyk) powiedział o tym problemie następujące zdanie: matematyka nie jest jeszcze gotowa na takie problemy.
Najprawdopodobniej zatem też nie jesteś gotowy(a) na takie problemy. Zadanie jest więc dużo łatwiejsze. Hipotezę sprawdzono dla bardzo wielu liczb i zawsze okazywała się prawdziwa. Zadanie to polega na doświadczalnym sprawdzeniu hipotezy. Który wyraz ciągu Collatza zaczynającego się od liczby N jest równy 1?
Napisz program, który: wczyta liczbę N, wyznaczy najmniejszy numer elementu ciągu Collatza zaczynającego się od N, który jest równy 1 i wypisze wynik na standardowe wyjście.
Wejście
W pierwszym (jedynym) wierszu wejścia znajduje się jedna liczba naturalna N — pierwszy wyraz ciągu Collatza.
Wyjście
W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba naturalna — najmniejszy indeks wyrazu ciągu Collatza, który jest równy 1.
Ograniczenia
0 ≤ N ≤ 109.
Przykład
| Input | Output | Explanation |
|
|
6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 |
| Input | Output | |
|
|