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

asked Nov 4, 2018 at 20:24
\$\endgroup\$
8
  • 17
    \$\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\$ Commented Nov 4, 2018 at 20:38
  • 1
    \$\begingroup\$ Thank you @cairdcoinheringaahing. I didn't know about this page. \$\endgroup\$ Commented Nov 4, 2018 at 21:38
  • \$\begingroup\$ Do we have to print the 0 at the end? \$\endgroup\$ Commented 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\$ Commented Nov 4, 2018 at 23:07
  • 4
    \$\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\$ Commented Nov 5, 2018 at 2:40

47 Answers 47

1
2
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.

answered Nov 4, 2018 at 23:43
\$\endgroup\$
5
\$\begingroup\$

Clean, 53 bytes

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

Try it online!

answered Nov 4, 2018 at 21:19
\$\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
answered Nov 4, 2018 at 23:23
\$\endgroup\$
4
\$\begingroup\$

Jelly, 9 bytes

:++‘ƊḂ?Ƭ2

Try it online!

answered Nov 4, 2018 at 20:41
\$\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.

answered Nov 4, 2018 at 21:40
\$\endgroup\$
3
\$\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
🍉🍉
answered Nov 5, 2018 at 16:39
\$\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
answered Nov 5, 2018 at 9:02
\$\endgroup\$
2
  • 1
    \$\begingroup\$ [Ð=_#Èi3*>ë<2÷ with = instead of D,. \$\endgroup\$ Commented Nov 7, 2018 at 4:20
  • \$\begingroup\$ @MagicOctopusUrn Ah, that was pretty bad to forgot.. Thanks! :) \$\endgroup\$ Commented 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
answered Jan 31, 2023 at 10:19
\$\endgroup\$
2
\$\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, \3ドルx + 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. \3ドルx+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.

answered Nov 4, 2018 at 20:48
\$\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\$ Commented Nov 4, 2018 at 21:38
  • \$\begingroup\$ @EduardoHoefel Break line? \$\endgroup\$ Commented Nov 4, 2018 at 21:38
  • \$\begingroup\$ @cairdcoinheringaahing The newline characters, presumably. \$\endgroup\$ Commented Nov 4, 2018 at 22:13
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!

answered Nov 4, 2018 at 21:29
\$\endgroup\$
5
  • \$\begingroup\$ -2 bytes \$\endgroup\$ Commented Nov 4, 2018 at 21:48
  • 1
    \$\begingroup\$ 50 bytes \$\endgroup\$ Commented 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\$ Commented Nov 5, 2018 at 2:43
  • \$\begingroup\$ Indeed, now you can do it in 44 \$\endgroup\$ Commented Nov 5, 2018 at 11:16
  • \$\begingroup\$ @Mr.Xcoder Cool, I was asleep lol \$\endgroup\$ Commented Nov 5, 2018 at 13:28
2
\$\begingroup\$

Stax, 11 bytes 

₧↑╔¶┘tÇ╣;↑è

Run and debug it

answered Nov 5, 2018 at 17:51
\$\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:[last3ドル*k+1:[div k 2|odd k]|k<-l r]

Try it online!

answered Nov 4, 2018 at 23:31
\$\endgroup\$
1
  • \$\begingroup\$ There are no negative numbers, so (>0) should suffice. Also there's an odd function. \$\endgroup\$ Commented 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!

answered Nov 4, 2018 at 20:52
\$\endgroup\$
2
\$\begingroup\$

JAEL, 18 bytes

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

Try it online!

answered Nov 4, 2018 at 21:13
\$\endgroup\$
4
  • 2
    \$\begingroup\$ Your permalink doesn't seem to be working. The program just prints the input and halts. \$\endgroup\$ Commented Nov 9, 2018 at 3:30
  • \$\begingroup\$ Yes, you're right. I'll ask "them" to pull the latest version :P \$\endgroup\$ Commented 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\$ Commented 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\$ Commented Nov 12, 2018 at 0:36
2
\$\begingroup\$

MathGolf, 12 bytes

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

answered Nov 5, 2018 at 23:55
\$\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

answered Jan 28, 2023 at 17:58
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 30 bytes

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

Try it online!

answered Nov 4, 2018 at 20:34
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Both order are 30 \$\endgroup\$ Commented Feb 5, 2023 at 13:58
2
\$\begingroup\$

Vyxal, (削除) 15 (削除ここまで) 12 bytes

Thanks to @Steffan i learned more about Vyxal!

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

Try it Online!

Naive approach for beginners:

{...:Ṡ|:2[3*›|‹2/
answered Feb 5, 2023 at 14:56
\$\endgroup\$
1
  • \$\begingroup\$ 12 bytes or alternative \$\endgroup\$ Commented Feb 11, 2023 at 3:45
2
\$\begingroup\$

Pyt, 15 bytes

`ĐĐ2%?ŕ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
 ?ŕ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
answered Feb 12, 2023 at 14:21
\$\endgroup\$
2
\$\begingroup\$

Thunno 2, 12 bytes 

(×ばつ+:−1⁄2

Try it online!

Explanation

(×ばつ+:−1⁄2 # 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:
 ×ばつ # multiply it by 3
 + # and then add one
 : # otherwise:
 − # decrement it
 1⁄2 # and then halve it
answered Aug 12, 2023 at 17:27
\$\endgroup\$
2
\$\begingroup\$

Nekomata, 11 bytes

ɪ{Z:←1⁄23ドル*→I

Attempt This Online! 

ɪ{Z:←1⁄23ドル*→I
ɪ{ Iterate until failure:
 Z Check if nonzero
 : Duplicate
 ← Decrement
 1⁄2 Halve; fails if odd
 $ Swap
 3* Multiply by 3
 → Increment
 I Choose the first value that doesn't fail
answered Aug 27, 2023 at 6:49
\$\endgroup\$
2
\$\begingroup\$

Acc!!, 76 bytes

Count i while N {
i
}
Count i while _ {
Write 49)*(_
Write 9
(_*3+1)/6^(_%2)

Try it online!

Intput and Output are both in unary

answered May 4, 2024 at 7:21
\$\endgroup\$
2
\$\begingroup\$

Vyxal 3, 11 bytes

э:ḃ[v1⁄2|Tꜝ}L·

Try it Online!

Explanation

э:ḃ[v1⁄2|Tꜝ}L·­⁡​‎‎⁡⁠⁡‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁣‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁤‏⁠‎⁡⁠⁢⁣‏⁠‎⁡⁠⁣⁢‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁢⁤‏⁠‎⁡⁠⁣⁡‏‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁣⁣‏‏​⁡⁠⁡‌­
э # ‎⁡Convert the next three elements to a lambda function:
 : # ‎⁢ Duplicate
 ḃ # ‎⁣ Parity (1 if odd, 0 if even)
 [ | } # ‎⁤ Ternary expression based on that value:
 v1⁄2 # ‎⁢⁡ If truthy (1/odd), decrement and halve
 Tꜝ # ‎⁢⁢ If falsey (0/even), triple and increment
 L· # ‎⁢⁣Apply that function to the input until it repeats a value, and return
 # the list of unique values visited
💎

Created with the help of Luminespire.

Alternate 11 bytes, port of Mukundan314's Acc!! answer:

λ:Tꜝ6←ḃ*Ṡ}L·

Try it online!

answered May 4, 2024 at 4:44
\$\endgroup\$
1
\$\begingroup\$

Pyth, 12 bytes

.u?%N2/N2h*3

Try it here as a test suite!

answered Nov 4, 2018 at 20:53
\$\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!

answered Nov 4, 2018 at 22:00
\$\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

answered Nov 5, 2018 at 10:09
\$\endgroup\$
1
  • \$\begingroup\$ you can try for(;$i) instead while($i) \$\endgroup\$ Commented Nov 5, 2018 at 12:19
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!

answered Nov 14, 2018 at 16:20
\$\endgroup\$
1
  • 1
    \$\begingroup\$ 61 bytes \$\endgroup\$ Commented Dec 14, 2018 at 16:05
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...
answered Mar 27, 2021 at 2:02
\$\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!

answered Dec 14, 2021 at 0:34
\$\endgroup\$
1
  • \$\begingroup\$ Building on @c-- 42 bytes \$\endgroup\$ Commented Aug 22, 2022 at 4:16
1
2

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.