> For the complete documentation index, see [llms.txt](https://project-euler-ja.gitbook.io/project-euler-ja/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://project-euler-ja.gitbook.io/project-euler-ja/401-500/491-500/p494.md).

# 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)$$ と定義しよう。\
\&#xNAN;*f*(5) = 5, *f*(10) = 55, *f*(20) = 6771 が与えられている。

*f*(90) を求めよ。