[Question]
  [
### 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](https://en.m.wikipedia.org/wiki/Collatz_conjecture) 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](https://oeis.org/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.
  
[Answer]
# [APL (Dyalog Unicode)](https://www.dyalog.com/), 18 [bytes](https://github.com/abrudz/SBCS)
```
+/∧/¨1<×\¨.5+,⍳⎕/2
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT///qG@qp/@jtgkGXGlAsvq/tv6jjuX6h1YY2hyeHnNohZ6pts6j3s2PerfqG/2v/Z92aAWQZ2gGAA "APL (Dyalog Unicode) – Try It Online")
A full program. Fails to compute the answer for \$k>15\$ due to system limitations (rank of intermediate array).
### How it works
If we call the \$\frac{x}{2}\$ the \$D\$-step and \$\frac{3x+1}{2}\$ as the \$U\$-step, it is known that each residue class \$0 \dots 2^k-1\$ modulo \$2^k\$ corresponds to exactly one \$UD\$-sequence of length \$k\$.
In the original formula, the coefficient of \$a\$ is multiplied by \$\frac32\$ for the \$U\$-step, and \$\frac12\$ for the \$D\$-step, and it suffices to count the \$UD\$-sequences where the coefficient never drops under 1.
The program computes this by generating all length-\$k\$ sequences of 0.5 and 1.5 (skipping the \$UD\$ part), and counts the ones where the multiplicative scan `×\` gives all numbers greater than 1.
```
+/∧/¨1<×\¨.5+,⍳⎕/2  ⍝ Full program; input: k
               ⎕/2  ⍝ k copies of 2
             ,⍳     ⍝ indices in an array of shape 2 2 ... 2
                    ⍝ which generates all binary sequences of length k
          .5+  ⍝ Add 0.5 to get all sequences of 0.5 and 1.5
       ×\¨     ⍝ Product scan
     1<        ⍝ Test if each number is greater than 1
  ∧/¨          ⍝ ... for all numbers in each sequence
+/             ⍝ Count ones
```
[Answer]
# [Python 3](https://docs.python.org/3/), 154 bytes
```
lambda k:sum(min(g(2**k,b,q+1)for q in range(k))>=(2**k,b)for b in range(2**k))
g=lambda x,y,z:z and g(*(x+y)%2and(3/2*x,(3*y+1)/2)or(x/2,y/2),z-1)or(x,y)
```
[Try it online!](https://tio.run/##RY7RjsIgEEWfy1eQJpvMVFa3oG41qV@xj/tCldamtkXEbNH47V10cSWBnGHunTva2X3fibHMv8eDbIudpM36dG6hrTuogCdJwwp2nKRY9oYead1RI7tKQYO4yUP/0StevfsvIqnyMHFgjl3WFyq7Ha0ggWHi8I37CsSMJwMDkTifMOPYGxhmnDmP7PKePmrmcPzZ1wdFv8xZrUlkjfNvJJnPzGkrNdSdZQ84WTP1t9bMb6PPFnB60ofaQryJ0a8URdp4MZRxCVd5Q@@/liDxRkENWm2t2tFrccPYS9WwVdrekwqjZDOm9H42NCX8n0QgTuaBBFkEmpNloIx8Ph2CZE9ckdXTk5H04w@Xc5IugoCvFr8 "Python 3 – Try It Online")
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 12 bytes
```
Ø.ṗ+.×\€ḞẠ€S
```
[Try it online!](https://tio.run/##y0rNyan8///wDL2HO6dr6x2eHvOoac3DHfMe7loAZAT/f9S49XA7kPUfAA "Jelly – Try It Online")
Port of [Bubbler's approach](https://codegolf.stackexchange.com/a/213994/68942), which is really clever and seems to be unbeatable with a straightforward approach lol. Make sure you upvote that answer!
## Explanation
```
Ø.ṗ+.×\€ḞẠ€S  Main Link
Ø.            [0, 1]
  ṗ           Cartesian product; gives all k-length binary sequences
   +.         Add 0.5
       €      For each sequence of 0.5, 1.5
     ×\       Take the cumulative products
        Ḟ     Floor (if it's less than 1, this returns 0; otherwise, it returns a positive/truthy value; 1 isn't a possible product at least for k up to a billion)
          €   For each sequence
         Ạ    1 if they're all truthy (so all are greater than 1), 0 otherwise
           S  Sum (counts the number of truthy results)
```
-1 byte thanks to Jonathan Allan with the observation that 1 is not a possible product (in practice up to like a billion, at least), so checking >=1 and >1 are the same, and you can do the former with floor, saving a byte.
[Answer]
# [Python 3 (PyPy)](http://pypy.org/), 49 bytes
Port of [Bubbler's APL answer](https://codegolf.stackexchange.com/a/213994/64121).
```
f=lambda n,p=1:n<1or(p>2)*f(n-1,p/2)+f(n-1,p*3/2)
```
[Try it online!](https://tio.run/##LcexDsIgFEbh3af4l6aAEAvEpbF9EeOAQZTEXm5IF54eO7icfIfb/inkDTduvaflG7ZnDCDNi53pZksVvDqpkiBjNV@cPP@p/DE9lYqMTLirGuj9ElbDWnnkquEmDT895hPANdMuxsFFmBVDHDFAZI0kspSy/wA "Python 3 (PyPy) – Try It Online")
---
# [Python 2 (PyPy)](http://pypy.org/), ~~138~~ ~~136~~ 134 bytes
A (slow) golf of the [C implementation](https://tio.run/##hZPbboMwDIbv8xRep1aJaCcIPQrIk0yaqkJbJMJQgO6i6rMzh3aUXTiNEHbs/7PjIA6LQ7EvT133npeHok0ziOsmzb8/zor9D5WNjbEWnfXyq4G6NZf8ktV8iJg5DL4e@QVu0IdK3u2xkoKxK2OA6@ecFxl/43oWCJjNgGuVFFoIeOTtyo/c2PQVjJdw4wVCqSAC7SW6d25PaVbUmdUplVjF3dz69EOFxXSMHawqa1pTgh@NcpVMEnvAZ/rZ4BEYJseBdRwHc5ywN5X08H0f7@9A3kjuaRKIGMMm9nb0Pi@5uPYFKoORI59MZQoLBdP0s5zMAZGhpt9v8bGOwDI0JglMurGQwEI3tiSwpRtbEdjKja0JbO3GNgS2cWNbAtu6sR2B7dxY4FPf238BUpcZvLhNSXWULzqGFBj24Pgn8iN267pf) given on the [OEIS page](https://oeis.org/A076227).
```
f=lambda k,r=0,m=1,w=1,q=0:f(k,r+r%2*-~r>>1,r%2*2*m+m>>1,w,q)if(w<=m)>m&1else m>=w and(q==k or sum(f(k,x,m*2,w*2,q+1)for x in(r,r+m)))
```
[Try it online!](https://tio.run/##FY3BDoIwGIPvPkUv6AY/CZvxYtxexHjAwHSRf8LUTC6@Oo5Dk/Zr0o7z@/4Muh7ncV4WZ4aWr12LB0XTEBtFKWsyzdGJzKpY6LL@RWsVrVaXXPEaEk3SO5FOhqXlreqHVw@2JqENnZiMeeAZ8fqwWHe@xKWmlDVVSrrcfOGDiPmApZTLSnwmiG249UIRlJKocFYHgm4I@@Zy3ABj9OGNXaE71BZFt0MB4QlO@LzyBw "Python 2 (PyPy) – Try It Online")
PyPy is used here because this is just annoyingly slow in CPython.
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), 13 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
13S;Iã€ηP1›PO
```
Port of [*@Bubbler*'s APL answer](https://codegolf.stackexchange.com/a/213994/52210), so make sure to upvote him!  
(This results in `0` for \$k=0\$.)
[Try it online](https://tio.run/##yy9OTMpM/f/f0DjY2vPw4kdNa85tDzB81LArwB8oaAAA) or [verify all test cases \$n\leq15\$](https://tio.run/##yy9OTMpM/W9o6upnr6TwqG2SgpL9f0PjYGu/w4sfNa05tz3A8FHDrgD//zr/AQ).
**Explanation:**
```
13S            # Push 13 as a list of digits: [1,3]
   ;           # Halve each: [0.5,1.5]
    Iã         # Take the cartesian product of this pair with the input-integer
      €        # Map over each inner list:
       η       #  And get all its prefixes
        P      # Take the product of each inner-most prefix
         1›    # Check for each value if it's larger than 1 (1 if truthy; 0 if falsey)
           P   # Check if an entire inner-most list is truthy by taking the product
            O  # Sum the list, to get the total amount of truthy values
               # (after which this sum is output implicitly as result)
```
Some equal-bytes alternatives for `13S;` could be `3ÅÉ;`; `₂€;;`; `₂S4/`; etc.
[Answer]
# [Haskell](https://www.haskell.org/), 45 bytes
```
(!1)
n!p|p<1=0|n<1=1|d<-n-1=d!(p/2)+d!(p*1.5)
```
[Try it online!](https://tio.run/##FcVBDsIgEADAu69YEg8gBdkmvRV/0Be0PZBWlEg3G@uRt0v1MvMM@@uec41@qlKgOpHgwj16V@gnlrU3ZNCvQvK1Vfr/BW2n6hYSgYct8ABySmBuwO9EH5kaiJCUgjOMaC26WesRu6Z1c/0uMYfHXs3CfAA "Haskell – Try It Online")
À la Bubbler.
[Answer]
# [C (gcc)](https://gcc.gnu.org/), ~~72~~ \$\cdots\$ ~~66~~ 65 bytes
Saved ~~3~~ ~~6~~ 7 bytes thanks to [ceilingcat](https://codegolf.stackexchange.com/users/52904/ceilingcat)!!!
```
f(n){n=s(n,1.);}s(n,p)float p;{n=n--?(p>2)*s(n,p/=2)+s(n,p*3):1;}
```
[Try it online!](https://tio.run/##XVHRaoMwFH33Ky5CIdHr2sS2rsvsHsa@YsoQjZuwpaJ5kBW/3V2tlXbCNSfn5Bxyb/LgM8@HoWSGn03cMoPigat@BDUvv0@ZhVqRYoLghdVHyb1JWseS@xPyQv4kVD9UxsJPVhnGnbMD9I2E1a39MO8pxHAWCBIhRNgi7BD2CBHCI8IBQWyoiJO0hpteLX7d1Tq3ulgSbkPIKwgJCggJ74kS8jDGRKEcRRlFVNs5L//KGg@aS5SbdG8y6Q6vVDsX4XYfurOjPDVsvEVlCt2Ra6Nm@Axt9atPJbvej69nwlsYBb4/neZwmce1J0NJ81wmPVV3siV5fI17VhO7DOO/rW7oSMncVQHBEei/ahNDTRkEi9SxjmObzoG90w9/ "C (gcc) – Try It Online")
Using [Bubbler](https://codegolf.stackexchange.com/users/78410/bubbler)'s method from his [APL answer](https://codegolf.stackexchange.com/a/213994/9481).
# [C (gcc)](https://gcc.gnu.org/), ~~175~~ \$\cdots\$ ~~138~~ 135 bytes
Saved a whopping 29 bytes thanks to [ovs](https://codegolf.stackexchange.com/users/64121/ovs)!!!  
Saved ~~4~~ 7 bytes thanks to [ceilingcat](https://codegolf.stackexchange.com/users/52904/ceilingcat)!!!
```
f(n){n=s(1,0,1,0,n);}s(m,r,l,p,q)long m;{for(;~m&m>0;)r-=r&1?m+=m/2,~r/2:(m/=2,r/2);m=m<l?0:p-q?s(m+=m,r+m,l+=l,++p,q)+s(m,r,l,p,q):1;}
```
[Try it online!](https://tio.run/##XZHRboJAEEXf/YqJiQZkCOyiUl1XH5p@RTWNQbAk7IoLD6QEf50OFomWZGC4M/ewM0TuOYraNrG0XWtZWAx97ELboikshQYzzPFqZxd9BiXq5GIscVNTtfWFbVxppmynHKk8jjfj8bWlPMmRMlsoqTbZzl/n7nVHKGpC4yjMHJmh43RQ5/kLayaaNtUlqGOqLXtUj4CuTijjovzSnweQUDMEjhAgzBEWCEuEEOENYYXAfArSOD0DvxGDP67yOCrj00B4hpCXUcYIEFC@JInxVYcJA94VeRhSzHte9H00MzB/qPG@@uD7avVOsRgjPL8H497Rbaw7RapPcUUuX/TpBor0J74k1uN8ttcLs0ER4Dj3bhv@9vGYSROp38u9fhAv5ZLK3T99VWNSh2X8t@WGWhJrPDmBuwW6T4q9pqE0Qok0cSxleeiBzahpfwE "C (gcc) – Try It Online")
Golf of [Phil Carmody](https://oeis.org/wiki/User:Phil_Carmody)'s C code on the OEIS [A076227](https://oeis.org/A076227) page.
[Answer]
# [Husk](https://github.com/barbuz/Husk), ~~15 14 13~~ 12 bytes
```
#ȯΛ⌊G*m+.πḋ2
```
[Try it online!](https://tio.run/##ASQA2/9odXNr/23igoHhuKMxMP8jyK/Om@KMikcqbSsuz4DhuIsy//8 "Husk – Try It Online")
-1 byte from Dominic van Essen.
-1 more byte from Dominic van Essen.
-1 more more byte from Dominic van Essen([Or is it?](https://codegolf.stackexchange.com/a/214009/80214)).
Same method as Bubbler's answer.
[Answer]
# [Forth (gforth)](http://www.complang.tuwien.ac.at/forth/gforth/Docs-html/), 107 bytes
```
: s ?dup if 1- fdup 2e f> abs fdup f2/ over recurse * swap 1.5e f* recurse + else fdrop 1 then ;
: f 1e s ;
```
[Try it online!](https://tio.run/##PU1LCsMgFNx7iiHLFC0K3URIz5LG95pAqKKmPb59UuhqvsxwzHXTT@7Q2oSCezgTdobV4E4dgWcsj/KT7K6Ib8rItJ65EEaUz5JgzU2K49@@gA4BDjlKiLrRC15NkGGSFy9flUpVgLOSh4gdBmaAnjEIZ1FrxhFjUl71avsC "Forth (gforth) – Try It Online")
[ovs](https://codegolf.stackexchange.com/a/213999/78410) and [Noodle9](https://codegolf.stackexchange.com/a/214010/78410) transformed the APL solution into a nice recursive function, so here is a translation of those into Forth.
```
\ recursive helper function
: s ( n f:p -- cnt )
  ?dup if                    \ if n is nonzero ( n f:p )
    1-                       \ ( n-1 f:p )
    fdup 2e f> abs fdup f2/  \ ( n-1 p>2 ) ( f: p p/2 )
    over recurse *           \ ( n-1 p>2*cnt1 ) ( f: p ) *0.5 branch
    swap 1.5e f* recurse     \ ( p>2*cnt1 cnt2 ) *1.5 branch
    +                        \ ( cnt )
  else        \ otherwise ( f:p )
    fdrop 1   \ remove p and push 1
  then
;
: f ( n -- cnt ) 1e s ;  \ main function; call s with p=1
```
]