The inverse Collatz Conjecture

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

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.

• As this is your third question in as many hours, I'd recommend that you check out the Sandbox, the place where we usually post question drafts for feedback, and to make sure they aren't duplicates. Nov 4, 2018 at 20:38
• Do we have to print the 0 at the end? Nov 4, 2018 at 23:01
• You might want to expand the last two test cases, since they're not that long
– Jo King
Nov 4, 2018 at 23:07
• @JoKing I compressed it because it repeats the output from the other lines. At the point you reach 3, it has the same output of when you start from it. The same applies for 10 or any other number. Nov 5, 2018 at 2:40

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


Try it online!

Now without the final 0.

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


Jelly, 9 bytes

:++‘ƊḂ?Ƭ2


Try it online!

Clean, 53 bytes

import StdEnv
$0=[0]$n=[n: $if(isOdd n)(n/2)(n*3+1)]  Try it online! 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. 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  • [Ð=_#Èi3*>ë<2÷ with = instead of D,. Nov 7, 2018 at 4:20 • @MagicOctopusUrn Ah, that was pretty bad to forgot.. Thanks! :) Nov 7, 2018 at 7:37 Nibbles, 7.5 bytes .$?%$~@+*3@~  Attempt This Online! . Iterate while unique$   starting at input
?   if
%   modulo (also save the quotient)
$the number ~ 2 @ then the quotient + else add *3 multiply by 3 @ the number ~ 1  Python 2, 5452 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! • -2 bytes Nov 4, 2018 at 21:48 • 50 bytes – Jo King Nov 4, 2018 at 23:25 • Though the 0 is now optional, so it's shorter to get rid of the second print – Jo King Nov 5, 2018 at 2:43 • Indeed, now you can do it in 44 Nov 5, 2018 at 11:16 • @Mr.Xcoder Cool, I was asleep lol Nov 5, 2018 at 13:28 Emojicode 0.5, 141 bytes 🐖🎅🏿🍇🍮a🐕😀🔡a 10🔁▶️a 0🍇🍊😛🚮a 2 1🍇🍮a➗a 2🍉🍓🍇🍮a➕✖️a 3 1🍉😀🔡a 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 🍉🍉  Stax, 11 bytes ₧↑╔¶┘tÇ╣;↑è  Run and debug it 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!

• There are no negative numbers, so (>0) should suffice. Also there's an odd function. Nov 5, 2018 at 18:25

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!

JAEL, 18 bytes

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


Try it online!

• Your permalink doesn't seem to be working. The program just prints the input and halts. Nov 9, 2018 at 3:30
• Yes, you're right. I'll ask "them" to pull the latest version :P Nov 9, 2018 at 15:37
• I've added JAEL to the list of golfing languages. Please let me know if I got any information wrong :-) Nov 9, 2018 at 19:39
• @ETHproductions Thank you very much :D I think I could say that the specialty is the utility package that helps the programmer to compress the code, but that's just me trying to merchandise it. Nov 12, 2018 at 0:36

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!

Thunnod, $$\ 19 \log_{256}(96) \approx \$$ 15.64 bytes

[zuZK!)2%?1-2,(3*1+


(No ATO link since this needs v1.2.2 and ATO is on v1.2.1)

Explanation

[zuZK!)2%?1-2,(3*1+  # Implicit input
[                    # Loop forever:
zu                  #  Quadruplicate the value on the top of the stack
ZK                #  Print with a trailing newline
!)              #  If it's 0, break
2%?           #  If it's odd:
1-         #   Subtract one
2,       #   And integer divide by two
(      #  Else:
3*    #   Multiply by three
#  This value is on the top of the stack for the next iteration
# The d flag stops the implicit output at the end


Vyxal, 15 12 bytes

Thanks to @Steffan i learned more about Vyxal!

{…:|:∷[2ḭ|T›


Try it Online!

Naive approach for beginners:

{…:Ṡ|:₂[3*›|‹2/

• Feb 11, 2023 at 3:45

Pyt, 15 bytes

ĐĐ2%?ŕ₂:ŕ3*⁺;ł


Try it online!

             ł        do... while top of stack is not 0; implicit print upon exiting loop
ĐĐ                    duplicate top of stack twice (implicit input if empty)
2%                  modulo 2
?ŕ₂              if top of stack is truthy, then pop from stack and divide next by 2
:ŕ3*⁺          else: pop from stack and multiply next term by 3 and add 1
;         end if-then-else statement


Thunno 2, 12 bytes

(ß;DE?3×⁺:⁻½


Try it online!

Explanation

(ß;DE?3×⁺:⁻½  # implicit input
(             # while loop:
ß            #   (condition)  print the number without popping
#                and test if it's truthy (non-zero)
;D          #   (body)  duplicate the current integer
E?        #           if it's even:
3×      #             multiply it by 3
⁺     #             and then add one
:    #           otherwise:
⁻   #             decrement it
½  #             and then halve it


Nekomata, 11 bytes

ᶦ{Z:←½$3*→I  Attempt This Online! ᶦ{Z:←½$3*→I
ᶦ{              Iterate until failure:
Z                 Check if nonzero
:                Duplicate
←               Decrement
½              Halve; fails if odd
$Swap 3* Multiply by 3 → Increment I Choose the first value that doesn't fail  Pyth, 12 bytes .u?%N2/N2h*3  Try it here as a test suite! Add++, 3835 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.

• Just to understand: Is the break line part of the code? Or is it just for better explanation? I don't really know this language. Nov 4, 2018 at 21:38
• @EduardoHoefel Break line? Nov 4, 2018 at 21:38
• @cairdcoinheringaahing The newline characters, presumably.
– lynn
Nov 4, 2018 at 22: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!

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 • you can try for(;$i) instead while($i) Nov 5, 2018 at 12:19 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  • I've added MathGolf to the list of golfing langs--feel free to correct me if I got anything wrong :-) Nov 12, 2018 at 20:28 • Thanks for adding it! Everything looks right to me. – maxb Nov 12, 2018 at 22:31 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! • 61 bytes Dec 14, 2018 at 16:05 Factor + math.extras, 56 bytes [ [ .s dup odd? [ 1 - 2/ ] [ 3 * 1 + ] if ] until-zero ]  Try it online! Explanation: • [ ... ] A quotation. An anonymous function that lives on the data stack until called or used by a combinator. • Assuming a data stack with 3 on top when this quotation is called... • [ .s dup odd? [ 1 - 2/ ] [ 3 * 1 + ] if ] Push a quotation to the data stack to be used later by until-zero. Stack: 3 [ .s dup odd? [ 1 - 2/ ] [ 3 * 1 + ] if ] • until-zero Call a quotation repeatedly until its output is 0. Stack: 3 • .s Non-destructively print the data stack. Stack: 3 • dup Duplicate TOS (top-of-stack). Stack: 3 3 • odd? Return t if input is odd, else f. Stack: 3 t • [ 1 - 2/ ] Push a quotation to be used later by if. Stack: 3 t [ 1 - 2/ ] • [ 3 * 1 + ] Push another quotation to be used later by if. Stack: 3 t [ 1 - 2/ ] [ 3 * 1 + ] • if Takes a boolean and two quotations from the data stack. Calls the first quotation if the boolean is t, otherwise calls the second. (Now inside the first quotation...) Stack: 3 • 1 Push 1 to the data stack. Stack: 3 1 • - Subtract TOS from NOS (next on stack). Stack: 2 • 2/ Integer divide by 2. Like doing x>>1 in many languages. Stack: 1 • Now until-zero looks at the data stack and sees TOS is not 0, so calls its input quotation... C (gcc), 75 bytes #include<stdio.h> int g(int x){printf("%d ",x);x?g(x=x%2?(x-1)/2:3*x+1):0;}  Try it online! • Building on @c-- 42 bytes Aug 22, 2022 at 4:16 K (ngn/k), 25 bytes {x>0}{$[2!x;_x%2;1+3*x]}\


Try it online!

Nim, 65 50 bytes (-15 due to xigoi)

proc f(n:int)=
echo n;if n>0:f [n*3+1,n/%2][n%%2]

Attempt This Online!

Simple recursive solution cum array-based due to xigoi.

• -8 bytes: ato.pxeger.com/… Jan 31, 2023 at 10:10
• Also, TIL about /% and %%, thanks! Jan 31, 2023 at 10:11
• Or even better, 50 bytes by using an array instead of the if expression: ato.pxeger.com/… Jan 31, 2023 at 10:33
• Nicely done! Edited to include. Feb 4, 2023 at 21:13

JavaScript (ES6), 30 bytes

f=n=>n&&n+[,f(n&1?n>>1:n*3+1)]


Try it online!