The inverse Collatz Conjecture

Question

I think the Collatz Conjecture is already well-known. But what if we invert the rules?

Start with an integer n >= 1.

Repeat the following steps:

If n is even, multiply it by 3 and add 1.

If n is odd, subtract 1 and divide it by 2.

Stop when it reaches 0

Print the iterated numbers.

Test cases:

 1        => 1, 0
 2        => 2, 7, 3, 1, 0
 3        => 3, 1, 0
10        => 10, 31, 15, 7, 3...
14        => 14, 43, 21, 10, ...

Rules:

• This sequence does not work for a lot of numbers because it enters in an infinite loop. You do not need to handle those cases. Only printing the test cases above is enough.

• I suggested to subtract 1 and divide by two to give a valid integer to continue, but it is not required to be computed that way. You may divide by 2 and cast to integer or whatever other methods that will give the expected output.

• You need to print the initial input as well.

• The output does not need to be formatted as the test cases. It was just a suggestion. However, the iterated order must be respected.

• The smallest code wins.

Answer 1

Perl 6, 30 bytes

{$_,{$_%2??$_+>1!!$_*3+1}...0}

Try it online!

Anonymous code block that returns a sequence.

Explanation:

{$_,{$_%2??$_+>1!!$_*3+1}...0}
{                            }   # Anonymous code block
   ,                     ...     # Define a sequence
 $_                              # That starts with the given value
    {                   }        # With each element being
     $_%2??     !!               # Is the previous element odd?
           $_+>1                 # Return the previous element bitshifted right by 1
                  $_*3+1         # Else the previous element multiplied by 3 plus 1
                            0    # Until the element is 0

Answer 2

Haskell, 40 39 bytes

f 0=[]
f n=n:f(cycle[3*n+1,div n 2]!!n)

Try it online!

Now without the final 0.

Answer 3

Clean, 53 bytes

import StdEnv
$0=[0]
$n=[n: $if(isOdd n)(n/2)(n*3+1)]

Try it online!

Answer 4

Jelly, 9 bytes

:++‘ƊḂ?Ƭ2

Try it online!

Answer 5

Rust, 65 64 bytes

|mut n|{while n>0{print!("{} ",n);n=if n&1>0{n>>1}else{n*3+1};}}

Try it online!

Answer 6

JAEL, 18 bytes

![ؼw>î?èÛ|õÀ

Try it online!

Answer 7

Python 2, 54 52 44 bytes

n=input()
while n:print n;n=(n*3+1,n/2)[n%2]

-2 bytes thanks to Mr. Xcoder

There must certainly be a faster way. Oddly, when I tried a lambda it was the same bytecount. I'm probably hallucinating.

Try it online!

Answer 8

Haskell, 76 69 61 56 bytes

I feel like this is way too long. Here l produces an infinite list of the inverse-collatz sequence, and the anonymous function at the first line just cuts it off at the right place.

Thanks for -5 bytes @ØrjanJohansen!

fst.span(>0).l
l r=r:[last$3*k+1:[div k 2|odd k]|k<-l r]

Try it online!

Answer 9

05AB1E, 15 14 bytes

[Ð=_#Èi3*>ë<2÷

-1 byte thanks to @MagicOctopusUrn.

Try it online.

Explanation:

[             # Start an infinite loop
 Ð            #  Duplicate the top value on the stack three times
              #  (Which will be the (implicit) input in the first iteration)
  =           #  Output it with trailing newline (without popping the value)
   _#         #  If it's exactly 0: stop the infinite loop
     Èi       #  If it's even:
       3*     #   Multiply by 3
         >    #   And add 1
      ë       #  Else:
       <      #   Subtract 1
        2÷    #   And integer-divide by 2

Answer 10

JavaScript (ES6), 31 bytes

f=n=>n&&n+' '+f(n&1?n>>1:n*3+1)

Try it online!

Or 30 bytes in reverse order.

Answer 11

Pyth, 12 bytes

.u?%N2/N2h*3

Try it here as a test suite!

Answer 12

Wolfram Language (Mathematica), 35 bytes

0<Echo@#&&#0[3#+1-(5#+3)/2#~Mod~2]&

Try it online!

0<Echo@# && ...& is short-circuit evaluation: it prints the input #, checks if it's positive, and if so, evaluates .... In this case, ... is #0[3#+1-(5#+3)/2#~Mod~2]; since #0 (the zeroth slot) is the function itself, this is a recursive call on 3#+1-(5#+3)/2#~Mod~2, which simplifies to 3#+1 when # is even, and (#-1)/2 when # is odd.

Answer 13

Common Lisp, 79 bytes

(defun x(n)(cons n(if(= n 0)nil(if(=(mod n 2)0)(x(+(* n 3)1))(x(/(- n 1)2))))))

Try it online!

Answer 14

PowerShell, 53 52 bytes

param($i)for(;$i){$i;$i=(($i*3+1),($i-shr1))[$i%2]}0

Try it Online!

Edit:
-1 byte thanks to @mazzy

Answer 15

Emojicode 0.5, 141 bytes

aa 10▶️a 0a 2 1a➗a 2a➕✖️a 3 1a 10

Try it online!

a       input integer variable 'a'
a 10       print input int
▶️a 0       loop while number isn’t 0
a 2 1      if number is odd
a➗a 2        divide number by 2

       else
a➕✖️a 3 1    multiply by 3 and add 1

a 10      print iteration

Answer 16

Stax, 11 bytes

₧↑╔¶┘tÇ╣;↑è

Run and debug it

Answer 17

x86 machine code, 39 bytes

00000000: 9150 6800 0000 00e8 fcff ffff 5958 a901  .Ph.........YX..
00000010: 0000 0074 04d1 e8eb 066a 035a f7e2 4009  ...t.....j.Z..@.
00000020: c075 dec3 2564 20                        .u..%d 

Assembly (NASM syntax):

section .text
	global func
	extern printf
func:					;the function uses fastcall conventions
	xchg eax, ecx			;load function arg into eax
	loop:
		push eax
		push fmt
		call printf	;print eax
		pop ecx
		pop eax
		test eax, 1	;if even zf=1
		jz even		;if eax is even jmp to even
		odd:		;eax=eax/2
			shr eax, 1
			jmp skip
		even:		;eax=eax*3+1
			push 3
			pop edx
			mul edx
			inc eax
		skip:
		or eax, eax
		jne loop	;if eax!=0, keep looping
	ret			;return eax
section .data
	fmt db '%d '

Try it online!

Answer 18

MathGolf, 12 bytes

{o_¥¿½É3*)}∟

Try it online!

Explanation

{             Start block of arbitrary length
 o            Output the number
  _           Duplicate
   ¥          Modulo 2
    ¿         If-else with the next two blocks. Implicit blocks consist of 1 operator
     ½        Halve the number to integer (effectively subtracting 1 before)
      É       Start block of 3 bytes
       3*)    Multiply by 3 and add 1
          }∟  End block and make it do-while-true

Answer 19

R, 66 61 bytes

-5 bytes thanks to Robert S. in consolidating ifelse into if and removing brackets, and x!=0 to x>0

print(x<-scan());while(x>0)print(x<-`if`(x%%2,(x-1)/2,x*3+1))

instead of

print(x<-scan());while(x!=0){print(x<-ifelse(x%%2,(x-1)/2,x*3+1))}

Try it online!

Answer 20

Add++, 38 35 33 bytes

D,f,@:,d3*1+$2/iA2%D
+?
O
Wx,$f>x

Try it online!

How it works

First, we begin by defining a function \$f(x)\$, that takes a single argument, performs the inverted Collatz operation on \$x\$ then outputs the result. That is,

$$f(x) = \begin{cases} x \: \text{is even}, & 3x+1 \\ x \: \text{is odd}, & \lfloor\frac{x}{2}\rfloor \end{cases}$$

When in function mode, Add++ uses a stack memory model, otherwise variables are used. When calculating \$f(x)\$, the stack initially looks like \$S = [x]\$.

We then duplicate this value (d), to yield \$S = [x, x]\$. We then yield the first possible option, \$3x + 1\$ (3*1+), swap the top two values, then calculate \$\lfloor\frac{x}{2}\rfloor\$, leaving \$S = [3x+1, \lfloor\frac{x}{2}\rfloor]\$.

Next, we push \$x\$ to \$S\$, and calculate the bit of \$x\$ i.e. \$x \: \% \: 2\$, where \$a \: \% \: b\$ denotes the remainder when dividing \$a\$ by \$b\$. This leaves us with \$S = [3x+1, \lfloor\frac{x}{2}\rfloor, (x \: \% \: 2)]\$. Finally, we use D to select the element at the index specified by \$(x \: \% \: 2)\$. If that's \$0\$, we return the first element i.e. \$3x+1\$, otherwise we return the second element, \$\lfloor\frac{x}{2}\rfloor\$.

That completes the definition of \$f(x)\$, however, we haven't yet put it into practice. The next three lines have switched from function mode into vanilla mode, where we operate on variables. To be more precise, in this program, we only operate on one variable, the active variable, represented by the letter x. However, x can be omitted from commands where it is obviously the other argument.

For example, +? is identical to x+?, and assigns the input to x, but as x is the active variable, it can be omitted. Next, we output x, then entire the while loop, which loops for as long as \$x \neq 0\$. The loop is very simple, consisting of a single statement: $f>x. All this does is run \$f(x)\$, then assign that to x, updating x on each iteration of the loop.

Answer 21

perl -Minteger -nlE, 39 bytes

{say;$_=$_%2?$_/2:3*$_+1 and redo}say 0

Answer 22

Retina 0.8.2, 46 bytes

.+
$*
{*M`1
^(..)+$
$&$&$&$&$&$&111
1(.*)\1
$1

Try it online! Explanation:

.+
$*

Convert to unary.

{

Repeat until the value stops changing.

*M`1

Print the value in decimal.

^(..)+$
$&$&$&$&$&$&111

If it is even, multiply by 6 and add 3.

1(.*)\1
$1

Subtract 1 and divide by 2.

The trailing newline can be suppressed by adding a ; before the {.

Answer 23

Red, 70 bytes

func[n][print n if n = 0[exit]either odd? n[f n - 1 / 2][f n * 3 + 1]]

Try it online!

Answer 24

Racket, 75 bytes

(define(f n)(cons n(if(= n 0)'()(if(odd? n)(f(/(- n 1)2))(f(+(* 3 n)1))))))

Try it online!

Equivalent to JRowan's Common Lisp solution.

Answer 25

C# (.NET Core), 62 bytes

a=>{for(;a>0;a=a%2<1?a*3+1:a/2)Console.Write(a+" ");return a;}

Try it online!

Ungolfed:

a => {
    for(; a > 0;                // until a equals 0
        a = a % 2 < 1 ?             // set a depending on if a is odd or even
                a * 3 + 1 :             // even
                a / 2                   // odd (minus one unnecessary because of int casting)
    )
        Console.Write(a + " "); // writes the current a to the console
    return a;                   // writes a to the console (always 0)
}

Answer 26

Dart, 49 bytes

f(n){for(;n>0;n=n%2>0?(n-1)>>1:(n*3)+1)print(n);}

Try it online!

Answer 27

Gambit Scheme (gsi), 74 bytes

(define(f n)(if(= 0 n)'()(cons n(f(if(even? n)(+ (* 3 n)1)(/(- n 1)2))))))

Try it online!