17
\$\begingroup\$

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.

\$\endgroup\$
8
  • 16
    \$\begingroup\$ 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. \$\endgroup\$ Nov 4, 2018 at 20:38
  • 1
    \$\begingroup\$ Thank you @cairdcoinheringaahing. I didn't know about this page. \$\endgroup\$ Nov 4, 2018 at 21:38
  • \$\begingroup\$ Do we have to print the 0 at the end? \$\endgroup\$
    – flawr
    Nov 4, 2018 at 23:01
  • 2
    \$\begingroup\$ You might want to expand the last two test cases, since they're not that long \$\endgroup\$
    – Jo King
    Nov 4, 2018 at 23:07
  • 3
    \$\begingroup\$ @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. \$\endgroup\$ Nov 5, 2018 at 2:40

45 Answers 45

7
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

Jelly, 9 bytes

:++‘ƊḂ?Ƭ2

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Clean, 53 bytes

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

Try it online!

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ [Ð=_#Èi3*>ë<2÷ with = instead of D,. \$\endgroup\$ Nov 7, 2018 at 4:20
  • \$\begingroup\$ @MagicOctopusUrn Ah, that was pretty bad to forgot.. Thanks! :) \$\endgroup\$ Nov 7, 2018 at 7:37
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
5
  • \$\begingroup\$ -2 bytes \$\endgroup\$
    – Mr. Xcoder
    Nov 4, 2018 at 21:48
  • 1
    \$\begingroup\$ 50 bytes \$\endgroup\$
    – Jo King
    Nov 4, 2018 at 23:25
  • \$\begingroup\$ Though the 0 is now optional, so it's shorter to get rid of the second print \$\endgroup\$
    – Jo King
    Nov 5, 2018 at 2:43
  • \$\begingroup\$ Indeed, now you can do it in 44 \$\endgroup\$
    – Mr. Xcoder
    Nov 5, 2018 at 11:16
  • \$\begingroup\$ @Mr.Xcoder Cool, I was asleep lol \$\endgroup\$
    – Quintec
    Nov 5, 2018 at 13:28
2
\$\begingroup\$

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
🍉🍉
\$\endgroup\$
2
\$\begingroup\$

Stax, 11 bytes

₧↑╔¶┘tÇ╣;↑è

Run and debug it

\$\endgroup\$
2
\$\begingroup\$

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!

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

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!

\$\endgroup\$
2
\$\begingroup\$

JAEL, 18 bytes

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

Try it online!

\$\endgroup\$
4
  • 2
    \$\begingroup\$ Your permalink doesn't seem to be working. The program just prints the input and halts. \$\endgroup\$
    – Dennis
    Nov 9, 2018 at 3:30
  • \$\begingroup\$ Yes, you're right. I'll ask "them" to pull the latest version :P \$\endgroup\$ Nov 9, 2018 at 15:37
  • \$\begingroup\$ I've added JAEL to the list of golfing languages. Please let me know if I got any information wrong :-) \$\endgroup\$ Nov 9, 2018 at 19:39
  • \$\begingroup\$ @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. \$\endgroup\$ Nov 12, 2018 at 0:36
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

Thunno d, \$ 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
                 1+  #   And add one
                     #  This value is on the top of the stack for the next iteration
                     # The d flag stops the implicit output at the end

Screenshot

Screenshot

\$\endgroup\$
2
\$\begingroup\$

Vyxal, 15 12 bytes

Thanks to @Steffan i learned more about Vyxal!

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

Try it Online!

Naive approach for beginners:

{…:Ṡ|:₂[3*›|‹2/
\$\endgroup\$
1
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

Pyth, 12 bytes

.u?%N2/N2h*3

Try it here as a test suite!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ 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. \$\endgroup\$ Nov 4, 2018 at 21:38
  • \$\begingroup\$ @EduardoHoefel Break line? \$\endgroup\$ Nov 4, 2018 at 21:38
  • \$\begingroup\$ @cairdcoinheringaahing The newline characters, presumably. \$\endgroup\$
    – lynn
    Nov 4, 2018 at 22:13
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ you can try for(;$i) instead while($i) \$\endgroup\$
    – mazzy
    Nov 5, 2018 at 12:19
1
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ I've added MathGolf to the list of golfing langs--feel free to correct me if I got anything wrong :-) \$\endgroup\$ Nov 12, 2018 at 20:28
  • \$\begingroup\$ Thanks for adding it! Everything looks right to me. \$\endgroup\$
    – maxb
    Nov 12, 2018 at 22:31
1
\$\begingroup\$

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!

\$\endgroup\$
1
1
\$\begingroup\$

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...
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
  • \$\begingroup\$ Building on @c-- 42 bytes \$\endgroup\$
    – ceilingcat
    Aug 22, 2022 at 4:16
1
\$\begingroup\$

K (ngn/k), 25 bytes

{x>0}{$[2!x;_x%2;1+3*x]}\

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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.

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

JavaScript (ES6), 30 bytes

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

Try it online!

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