---

Problem 494

---

Collatz prefix families

The Collatz sequence is defined as:

$$a_{i+1} = \frac{a_i}{2} \text{ if }a_i\text{ is even}$$ $$a_{i+1} = 3a_i+1\text{ if }a_i\text{ is odd}$$

The Collatz conjecture states that starting from any positive integer, the sequence eventually reaches the cycle 1,4,2,1….
We shall define the sequence prefix p(n) for the Collatz sequence starting with a₁ = n as the sub-sequence of all numbers not a power of 2 (2⁰=1 is considered a power of 2 for this problem). For example:
p(13) = {13, 40, 20, 10, 5}
p(8) = {}
Any number invalidating the conjecture would have an infinite length sequence prefix.

Let S_m be the set of all sequence prefixes of length m. Two sequences {a₁, a₂, …, a_m} and {b₁, b₂, …, b_m} in S_m are said to belong to the same prefix family if a_i < a_j if and only if b_i < b_j for all 1 ≤ i,j ≤ m.

For example, in S₄, {6, 3, 10, 5} is in the same family as {454, 227, 682, 341}, but not {113, 340, 170, 85}.
Let f(m) be the number of distinct prefix families in S_m.
You are given f(5) = 5, f(10) = 55, f(20) = 6771.

Find f(90).

---

考拉兹前缀族

考拉兹序列是指按如下方式定义的数列：

$$a_{i+1} = \frac{a_i}{2} \text{ 若}a_i\text{是偶数}$$ $$a_{i+1} = 3a_i+1\text{ 若}a_i\text{是奇数}$$

相应地，考拉兹猜想认为，从任何正整数开始，序列最终将进入循环1，4，2，1……
我们定义“序列前缀”p(n)为从a₁ = n开始的考拉兹序列的不包含2的幂次的子序列（2⁰=1在此也视为2的幂次）。例如：
p(13) = {13, 40, 20, 10, 5}
p(8) = {}
考拉兹猜想的反例将会有一个无限长的序列前缀。

记S_m为所有长度为m的序列前缀构成的集合。S_m中的两个序列前缀{a₁, a₂, …, a_m}和{b₁, b₂, …, b_m}属于同一个前缀族，如果对于任意1 ≤ i,j ≤ m，a_i < a_j当且仅当b_i < b_j。

例如，在S₄中，{6, 3, 10, 5}和{454, 227, 682, 341}在同一前缀族，而{113, 340, 170, 85}不在该前缀族。
记f(m)为S_m中不同前缀族的数量。
已知f(5) = 5，f(10) = 55，f(20) = 6771。

求f(90)。

---