3n+1 probléma
Tekintsük a következő algoritmust, mely egy adott $n$ számra a következő sorozatot adja:
$a_1=n$
$ a_{i+1} = \left\{\begin{array}{l l} \frac{a_{i}}{2} & \textrm{ha } a_i \equiv 0 \textrm{ mod }(2),\\ 3a_{i}+1 & \textrm{ha } a_i \equiv 1 \textrm{ mod }(2). \end{array}\right. $
$ a_{i+1} = \left\{\begin{array}{l l} \frac{a_{i}}{2} & \textrm{ha } a_i \equiv 0 \textrm{ mod }(2),\\ 3a_{i}+1 & \textrm{ha } a_i \equiv 1 \textrm{ mod }(2). \end{array}\right. $
Ha $a_i=1$, akkor vége a sorozatnak. Például $n=22$ esetén a sorozat:
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
A sejtés az, hogy a fenti algoritmus minden egész $n$-re (de legalábbis 1 és 1000000 között) véges sorozatot ad (utolsó eleme 1).
Feladat
Készíts programot (3N_1.PAS, 3N_1.C, ...), megy egy adott $n\in[i,j]$ számokra meghatározza az algoritmus által generált sorozatok maximális elemszámát.
Bemenet
A 3N_1.BE szöveges állomány sorai $i$ és $j$ számpárokat tartalmaz ($1\le i < j < 1000000$).
Kimenet
A 3N_1.KI szöveges állomány soraiban az $i$, $j$ és az $[i,j]$ intervallum elemeire generált sorozatok maximális elemszáma (szóközökkel elválasztva).
Példa
| 3N_1.BE | 3N_1.KI |
|
1 10 100 200 201 210 900 1000 |
1 10 20 100 200 125 201 210 89 900 1000 174 |