21
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Should I handle k=0 as input? \$\endgroup\$ – Bubbler Oct 23 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\$ – Shieru Asakoto Oct 23 at 7:09
19
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • 1
    \$\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\$ – Shieru Asakoto Oct 23 at 7:13
5
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ how does the verification works? it doesn't seem to use functions \$\endgroup\$ – Nahuel Fouilleul Oct 23 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\$ – HyperNeutrino Oct 23 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\$ – Nahuel Fouilleul Oct 23 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\$ – HyperNeutrino Oct 23 at 11:13
4
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Ø.ṗ+.×\€ḞẠ€S saves one byte (assuming we can never get 1 in the products). \$\endgroup\$ – Jonathan Allan Oct 23 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\$ – HyperNeutrino Oct 23 at 14:08
4
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • 4
    \$\begingroup\$ golfed C so hard it became python \$\endgroup\$ – Dion Oct 23 at 8:04
3
\$\begingroup\$

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\$.)

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

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.

| improve this answer | |
\$\endgroup\$
  • 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 Oct 23 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\$ – Kevin Cruijssen Oct 23 at 8:27
2
\$\begingroup\$

Haskell, 45 bytes

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

Try it online!

À la Bubbler.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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.

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

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

Same method as Bubbler's answer.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ 14 bytes using #... \$\endgroup\$ – Dominic van Essen Oct 23 at 15:16
  • \$\begingroup\$ ...and 13 bytes by flipping last 2 arguments... \$\endgroup\$ – Dominic van Essen Oct 23 at 15:27
  • \$\begingroup\$ @DominicvanEssen what on earth is m+.?!?! \$\endgroup\$ – Razetime Oct 23 at 15:29
  • 1
    \$\begingroup\$ . on its own is evaluated as .5. It's in the Wiki somewhere... \$\endgroup\$ – Dominic van Essen Oct 23 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\$ – Dominic van Essen Oct 23 at 15:33
1
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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