494：コラッツプレフィックスファミリー

コラッツ数列は次のように定義される： $a_{i+1} = \left \{ \begin{array}{cl}a_i / 2 & a_i が偶数のとき \\ 3a_i+1 & a_i が奇数のとき \end{array} \right .$

コラッツ予想では、いかなる正の整数から始めても、この数列は最終的に 1,4,2,1... という周期に入るとされている。 $a_1 = n$ から始まるコラッツ数列のうち、2のべき乗でない数からなる部分数列を、その数列の先頭の数を用いて $p(n)$ と表し、これを「数列プレフィックス」と定義する。 （この問題では $2^0 = 1$ は2のべき乗と見なす。）

例えば： $p(13) = \{13, 40, 20, 10, 5\}$ $p(8) = \{\}$ コラッツ予想に反する数が存在するならば、この部分数列は無限の長さを持つことになる。

長さ $m$ の全ての数列プレフィックスの集合を $S_m$ とする。$S_m$ 内の2つの数列 $\{a_1, a_2, \dots, a_m\}$ と $\{b_1, b_2, \dots, b_m\}$ が、$1 \leq i,j \leq m$ において $b_i < b_j$ かつそのときに限り $a_i < a_j$ であるならば、この数列は同じプレフィックスファミリーに属すると言うことにする。

例えば、集合 $S_4$ 内では、{6, 3, 10, 5} は {454, 227, 682, 341} と同じファミリーに属するが、{113, 340, 170, 85} はそうではない。 $S_m$ 内の異なるプレフィックスファミリーの個数を $f(m)$ と定義しよう。 f(5) = 5, f(10) = 55, f(20) = 6771 が与えられている。

f(90) を求めよ。