277 : 修正コラッツ列

整数の修正コラッツ列は値$a_1$から始めて次のようにして得られる：

$a_n$が3で割り切れるならば、$\displaystyle a_{n+1} = \frac{n}{3}$ これを大きな下降ステップ "D" と表す。

$a_n$を3で割った余りが1ならば、$\displaystyle a_{n+1} = \frac{4a_n + 2}{3}$ これを大きな上昇ステップ "U" と表す。

$a_n$を3で割った余りが2ならば、$\displaystyle a_{n+1} = \frac{2a_n - 1}{3}$ これを小さな下降ステップ "d" と表す。

数列は$a_n = 1$となれば終了する。

任意の整数が与えられたとき、ステップの列を書き出すことができる。 例えば$a_1=231$なら、数列${a_{n}}={231,77,51,17,11,7,10,14,9,3,1}$はステップ "DdDddUUdDD" に対応する。

もちろん、同じ列 "DdDddUUdDD...." から始まる列は他にもある。 例えば$a_{1}=1004064$なら、ステップの列は DdDddUUdDDDdUDUUUdDdUUDDDUdDD である。 実際、1004064 は列 DdDddUUdDD から始まる最小の可能な$a_1 > 10^6$である。

列 "UDDDUdddDDUDDddDdDddDDUDDdUUDd" から始まる最小の$a_1 > 10^{15}$は何か？