Problemy obliczeniowe w informatyce są klasyfikowane, ze względu na złożoność obliczeniową (trudność dla komputera), jako należące do jednej z klas problemów. Do takich klas należą problemy wielomianowe (łatwe), NP-zupełne (trudne) czy nierozstrzygalne (niemożliwe do rozwiązania). To zadanie dotyka powierzchownie jednego z problemów, który mimo długich badań sprawia problemy z zaklasyfikowaniem do którejś z takich klas.
Rozważmy następujący algorytm:
1. wprowadź n
2. drukuj n
3. if n = 1 then STOP
4. if n jest nieparzyste then n:=3n+1
5. else n:=n/2
6. GOTO 2
gdzie instrukcja STOP kończy działanie programu, natomiast instrukcja GOTO powoduje bezwarunkowy skok do wiersza 2 programu. Jeśli podamy na wejściu liczbę 22, wydrukowana zostanie następująca sekwencja 16 liczb:
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
Hipoteza matematyczna (nie potwierdzona ani nie obalona do dzisiaj) mówi, że dla każdej liczby naturalnej taka procedura jest skończona. Zostało to sprawdzone dla wielu liczb, w szczególności wiadomo, że jest to prawda dla wszystkich liczb mieszczących się w zakresie podstawowych typów danych języka C.
Twoim zadanie jest napisać program, który wczyta dwie liczby naturalne N oraz M i wydrukuje maksymalną długość ciągu wygenerowanego przez tę procedurę, gdy na wejściu podawać będziemy liczby z znajdujące się pomiędzy N a M (z N i M włącznie).
Przykład
Wejście:
1 10
Wyjście:
20
Podpowiedź: Zaimplementuj odpowiednią funkcję wyznaczającą kolejną wartość w ciągu.