## Collatz prefix families

### Problem 494

The Collatz sequence is defined as: $a_{i+1} = \left\{ \large{\frac {a_i} 2 \atop 3 a_i+1} {\text{if }a_i\text{ is even} \atop \text{if }a_i\text{ is odd}} \right.$.

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 _{1} = n` as the sub-sequence of all numbers not a power of 2 (2

^{0}=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

_{1}, a

_{2}, ..., a

_{m}} and {b

_{1}, b

_{2}, ..., b

_{m}} in

`S`are said to belong to the same prefix family if a

_{m}_{i}< a

_{j}if and only if b

_{i}< b

_{j}for all 1 ≤ i,j ≤

`m`.

For example, in `S`_{4}, {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).