Introduction
We have 22 Collatz conjecture-related challenges as of October 2020, but none of which cares about the restrictions on counter-examples, if any exists, to the conjecture.
Considering a variant of the operation defined in the conjecture:
$$f(x)= \cases{ \frac{x}{2}&for even x \cr \frac{3x+1}{2}&for odd x }$$
The Wikipedia article suggests that a modular restriction can be easily calculated and used to speed up the search for the first counter-example. For a pair of \$k\$ and \$b\$ where \$0\le b\lt2^k\$, if it is possible to prove that \$f^k(2^ka+b)<2^ka+b\$ for all sufficiently large non-negative integers \$a\$, the pair can be discarded. This is because if the inequality holds for the counter-example, we can find a smaller counter-example from that, contradicting the assumption that the counter-example is the first one.
For example, \$b=0, k=1\$ is discarded because \$f(2a)=a<2a\$, while \$b=3, k=2\$ is not because \$f^2(4a+3)=9a+8>4a+3\$. Indeed, for \$k=1\$ we only have \$b=1\$ and for \$k=2\$, \$b=3\$, to remain (survive) after the sieving process. When \$k=5\$, though, we have 4 survivors, namely 7, 15, 27 and 31.
However, there are still 12,771,274 residues mod \$2^{30}\$ surviving, so just still about a 100x boost even at this level
Challenge
Write a program or function, given a natural number \$k\$ as input, count the number of moduli mod \$2^k\$ that survives the sieving process with the operation applied \$k\$ times. The algorithm used must in theory generalize for arbitrary size of input.
The sequence is indeed A076227.
Examples
Input > Output
1 > 1
2 > 1
3 > 2
4 > 3
5 > 4
6 > 8
7 > 13
8 > 19
9 > 38
10 > 64
15 > 1295
20 > 27328
30 > 12771274
Winning criteria
This is a code-golf challenge, so the shortest submission of each language wins. Standard loopholes are forbidden.
