14
\$\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\$
  • 9
    \$\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\$ – caird coinheringaahing Nov 4 '18 at 20:38
  • \$\begingroup\$ Thank you @cairdcoinheringaahing. I didn't know about this page. \$\endgroup\$ – Eduardo Hoefel Nov 4 '18 at 21:38
  • \$\begingroup\$ Do we have to print the 0 at the end? \$\endgroup\$ – flawr Nov 4 '18 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 '18 at 23:07
  • 2
    \$\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\$ – Eduardo Hoefel Nov 5 '18 at 2:40

28 Answers 28

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

Clean, 53 bytes

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

Try it online!

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

Jelly, 9 bytes

:++‘ƊḂ?Ƭ2

Try it online!

\$\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\$
  • \$\begingroup\$ -2 bytes \$\endgroup\$ – Mr. Xcoder Nov 4 '18 at 21:48
  • \$\begingroup\$ @Mr.Xcoder Ah, thanks. \$\endgroup\$ – Quintec Nov 4 '18 at 21:50
  • 1
    \$\begingroup\$ 50 bytes \$\endgroup\$ – Jo King Nov 4 '18 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 '18 at 2:43
  • \$\begingroup\$ Indeed, now you can do it in 44 \$\endgroup\$ – Mr. Xcoder Nov 5 '18 at 11:16
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\$
  • \$\begingroup\$ There are no negative numbers, so (>0) should suffice. Also there's an odd function. \$\endgroup\$ – Ørjan Johansen Nov 5 '18 at 18:25
  • \$\begingroup\$ @ØrjanJohansen Thanks a lot! \$\endgroup\$ – flawr Nov 5 '18 at 20:32
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\$

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

JAEL, 18 bytes

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

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Your permalink doesn't seem to be working. The program just prints the input and halts. \$\endgroup\$ – Dennis Nov 9 '18 at 3:30
  • \$\begingroup\$ Yes, you're right. I'll ask "them" to pull the latest version :P \$\endgroup\$ – Eduardo Hoefel Nov 9 '18 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\$ – ETHproductions Nov 9 '18 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\$ – Eduardo Hoefel Nov 12 '18 at 0:36
1
\$\begingroup\$

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.

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

Pyth, 12 bytes

.u?%N2/N2h*3

Try it here as a test suite!

\$\endgroup\$
1
\$\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\$
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\$
  • \$\begingroup\$ you can try for(;$i) instead while($i) \$\endgroup\$ – mazzy Nov 5 '18 at 12:19
1
\$\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\$
1
\$\begingroup\$

Stax, 11 bytes

₧↑╔¶┘tÇ╣;↑è

Run and debug it

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

perl -Minteger -nlE, 39 bytes

{say;$_=$_%2?$_/2:3*$_+1 and redo}say 0
\$\endgroup\$
0
\$\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\$
  • \$\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\$ – Eduardo Hoefel Nov 4 '18 at 21:38
  • \$\begingroup\$ @EduardoHoefel Break line? \$\endgroup\$ – caird coinheringaahing Nov 4 '18 at 21:38
  • \$\begingroup\$ @cairdcoinheringaahing The newline characters, presumably. \$\endgroup\$ – Lynn Nov 4 '18 at 22:13
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

PHP, 51 bytes

<?for(;$n=&$argn;$n=$n%2?$n>>1:$n*3+1)echo"$n "?>0

(trailing newline)

Using -n to ignore the config file (use default settings) , and -F to read input (each line of input is passed to the script as $argn).

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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)
}
\$\endgroup\$
0
\$\begingroup\$

Dart, 49 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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!

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