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


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.


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.

  • 2
    \$\begingroup\$ Should I handle k=0 as input? \$\endgroup\$
    – Bubbler
    Commented Oct 23, 2020 at 3:50
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Oct 23, 2020 at 7:09

9 Answers 9


APL (Dyalog Unicode), 18 bytes


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
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ Commented Oct 23, 2020 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!

  • \$\begingroup\$ how does the verification works? it doesn't seem to use functions \$\endgroup\$ Commented Oct 23, 2020 at 8:16
  • 1
    \$\begingroup\$ @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). \$\endgroup\$
    – hyper-neutrino
    Commented Oct 23, 2020 at 11:01
  • 1
    \$\begingroup\$ i mean in the tio link i can't see these functions called, if i remove them it still output the same \$\endgroup\$ Commented Oct 23, 2020 at 11:05
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – hyper-neutrino
    Commented Oct 23, 2020 at 11:13

Jelly, 12 bytes


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!


Ø.ṗ+.×\€ḞẠ€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.

  • \$\begingroup\$ Ø.ṗ+.×\€ḞẠ€S saves one byte (assuming we can never get 1 in the products). \$\endgroup\$ Commented Oct 23, 2020 at 13:19
  • \$\begingroup\$ @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!! \$\endgroup\$
    – hyper-neutrino
    Commented Oct 23, 2020 at 14:08

Python 3 (PyPy), 49 bytes

Port of Bubbler's APL answer.

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), 138 136 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.

  • 4
    \$\begingroup\$ golfed C so hard it became python \$\endgroup\$
    – Dion
    Commented Oct 23, 2020 at 8:04

05AB1E, 13 bytes


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

Try it online or verify all test cases \$n\leq15\$.


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.

  • 1
    \$\begingroup\$ 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.) \$\endgroup\$
    – Bubbler
    Commented Oct 23, 2020 at 8:25
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Oct 23, 2020 at 8:27

Haskell, 45 bytes


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.

  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – ovs
    Commented Oct 23, 2020 at 11:27
  • \$\begingroup\$ @ovs Super, was a bit rushed posting this - thanks! :D \$\endgroup\$
    – Noodle9
    Commented Oct 23, 2020 at 13:38
  • \$\begingroup\$ @ceilingcat That makes it a hat trick - thanks! :D \$\endgroup\$
    – Noodle9
    Commented Oct 24, 2020 at 0:32

Husk, 15 14 13 12 bytes


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

Same method as Bubbler's answer.

  • 1
    \$\begingroup\$ 14 bytes using #... \$\endgroup\$ Commented Oct 23, 2020 at 15:16
  • \$\begingroup\$ ...and 13 bytes by flipping last 2 arguments... \$\endgroup\$ Commented Oct 23, 2020 at 15:27
  • \$\begingroup\$ @DominicvanEssen what on earth is m+.?!?! \$\endgroup\$
    – Razetime
    Commented Oct 23, 2020 at 15:29
  • 1
    \$\begingroup\$ . on its own is evaluated as .5. It's in the Wiki somewhere... \$\endgroup\$ Commented Oct 23, 2020 at 15:32
  • 1
    \$\begingroup\$ 12 bytes using instead of >1 - but this is really Jonathan Allan's golf, not mine (see the Jelly answer)... \$\endgroup\$ Commented Oct 23, 2020 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
: f ( n -- cnt ) 1e s ;  \ main function; call s with p=1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.