# Count the Collatz survivors mod 2^n

### 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.

• Should I handle k=0 as input? – Bubbler Oct 23 '20 at 3:50
• @Bubbler You don't need to handle k=0, but if that makes it easier you can. By the way f(k)=1 for k=0 as per OEIS. – Shieru Asakoto Oct 23 '20 at 7:09

# APL (Dyalog Unicode), 18 bytes

+/∧/¨1<×\¨.5+,⍳⎕/2


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

• Wow, that's an insight I've never heard or thought of! I wondered why solving for $2^x<3^y$ is crucial as stated in the OEIS page, but I think that's why. – Shieru Asakoto Oct 23 '20 at 7:13

# Python 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!

• how does the verification works? it doesn't seem to use functions – Nahuel Fouilleul Oct 23 '20 at 8:16
• @NahuelFouilleul In Python. lambda <a...>: <b...> represents an anonymous function with arguments a and result b. I use two of them; the second one is recursive and referenced in my code so I need to assign it a name (here I chose g), and the first one is not recursive so I can leave out the name (as per site policy). – hyper-neutrino Oct 23 '20 at 11:01
• i mean in the tio link i can't see these functions called, if i remove them it still output the same – Nahuel Fouilleul Oct 23 '20 at 11:05
• @NahuelFouilleul Ah. Thanks for pointing that out. That's just me being silly; my output loop wasn't actually using the function itself. Fixed it now. – hyper-neutrino Oct 23 '20 at 11:13

# Jelly, 12 bytes

Ø.ṗ+.×\€ḞẠ€S


Try it online!

Port of Bubbler's approach, 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
€      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.

• Ø.ṗ+.×\€ḞẠ€S saves one byte (assuming we can never get 1 in the products). – Jonathan Allan Oct 23 '20 at 13:19
• @JonathanAllan Oh, I forgot about that (for k up to like a billion we won't get 1 even with Python precision so I think it's good). thanks!! – hyper-neutrino Oct 23 '20 at 14:08

# Python 3 (PyPy), 49 bytes

f=lambda n,p=1:n<1or(p>2)*f(n-1,p/2)+f(n-1,p*3/2)


Try it online!

# Python 2 (PyPy), 138136 134 bytes

A (slow) golf of the C implementation given on the OEIS page.

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!

PyPy is used here because this is just annoyingly slow in CPython.

• golfed C so hard it became python – Dion Oct 23 '20 at 8:04

# 05AB1E, 13 bytes

13S;Iã€ηP1›PO


Port of @Bubbler's APL answer, so make sure to upvote him!
(This results in 0 for $$\k=0\$$.)

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.

• Mine correctly computes 1 for $k=0$, though I did ask the question (behind story: one of the different versions was wrong for $k=0$, then another was wrong for $k=1$, then I gave up trying something else and went with the maximally correct one.) – Bubbler Oct 23 '20 at 8:25
• @Bubbler Ah ok, my bad. Since you asked the question I assumed yours didn't work for $k=0$ either. I've edited my answer to reflect only mine results in an incorrect result for $k=0$, since OP has edited the challenge description to exclude it. – Kevin Cruijssen Oct 23 '20 at 8:27

(!1)
n!p|p<1=0|n<1=1|d<-n-1=d!(p/2)+d!(p*1.5)


Try it online!

À la Bubbler.

# C (gcc), 72 $$\\cdots\$$ 66 65 bytes

Saved 3 6 7 bytes thanks to 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!

Using Bubbler's method from his APL answer.

# C (gcc), 175 $$\\cdots\$$ 138 135 bytes

Saved a whopping 29 bytes thanks to ovs!!!
Saved 4 7 bytes thanks to 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!

Golf of Phil Carmody's C code on the OEIS A076227 page.

• You can use ~m%2 instead of !(m&1), r-~r instead of r+(r+1), <<1 -> *2, >>1 -> /2 and shorten these longer variable names. – ovs Oct 23 '20 at 11:27
• @ovs Super, was a bit rushed posting this - thanks! :D – Noodle9 Oct 23 '20 at 13:38
• @ceilingcat That makes it a hat trick - thanks! :D – Noodle9 Oct 24 '20 at 0:32

# Husk, 15 14 13 12 bytes

#ȯΛ⌊G*m+.πḋ2


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?).

• 14 bytes using #... – Dominic van Essen Oct 23 '20 at 15:16
• ...and 13 bytes by flipping last 2 arguments... – Dominic van Essen Oct 23 '20 at 15:27
• @DominicvanEssen what on earth is m+.?!?! – Razetime Oct 23 '20 at 15:29
• . on its own is evaluated as .5. It's in the Wiki somewhere... – Dominic van Essen Oct 23 '20 at 15:32
• 12 bytes using ⌊ instead of >1 - but this is really Jonathan Allan's golf, not mine (see the Jelly answer)... – Dominic van Essen Oct 23 '20 at 15:33

# Forth (gforth), 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!

ovs and Noodle9 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