# The Collatz sequence

Given a positive integer $$\a_1\$$, the Collatz sequence with starting value $$\a_1\$$ is defined as $$$$a_{n+1} = \begin{cases} a_n/2 & \mathrm{if}\ a_n\ \mathrm{is}\ \mathrm{even} \\ 3a_n+1 & \mathrm{if}\ a_n\ \mathrm{is}\ \mathrm{odd}. \end{cases}$$$$ It is conjectured that, for any starting value, this sequence always reaches the number $$\1\$$. This challenge assumes that the conjecture is true.

# The challenge

Given an integer $$\a_1 > 2\$$, compute the Collatz sequence until $$\1\$$ is reached for the first time. Let $$\N\$$ be the number of sequence terms (including $$\a_1\$$ and $$\a_N = 1\$$). From the sequence of numbers $$$$a_1, a_2, a_3, \ldots a_N$$$$ form a sequence of points in the plane by taking overlapping pairs $$$$(a_1, a_2), (a_2, a_3), \ldots, (a_{N-1}, a_N)$$$$ and plot these points on a 2D graph, joining consecutive points by a line segment.

# Example

For input $$\12\$$ the Collatz sequence is ($$\10\$$ terms); $$$$12, 6, 3, 10, 5, 16, 8, 4, 2, 1.$$$$ The sequence of points is ($$\9\$$ points): $$$$(12, 6), (6, 3), (3, 10), (10, 5), (5, 16), (16, 8), (8, 4), (4, 2), (2, 1).$$$$ The plot contains $$\8\$$ line segments, as shown in the following graph. Note that some of the segments partially overlap. For clarity, the plot includes markers at the $$\9\$$ points.

• Graphical output is required, with output being flexible as usual.
• Only the straight lines are required in the graph. Line width is flexible, as long as the plot can be seen reasonably well. Line color is also flexible, and may be different for each segment, as long as lines are distinguishable from the background.
• Other elements in the graph are not required, but are allowed (point markers, grid lines, axis labels, ...).
• Horizontal and vertical axis scales need not be the same. Axis limits are arbitrary, as long as the graph can be seen fully and clearly. The axes may be swapped, and each axis may be reversed.
• The code should work for any input given unlimited resources. It is acceptable if in practice it fails for large inputs due to time, memory or data-type limitations.
• If the input happens to be a counterexample for the Collatz conjecture the code can do anything, such as get stuck in an infinite loop or order a pizza.
• Programs or functions are accepted. Standard loopholes are forbidden.
• Shortest code in bytes wins.

# Test cases

Input Output
3
4
27
649
650
46720
345435
63728127
• Related – Luis Mendo Jun 11 at 22:39
• This is beautiful! – AviFS Jun 12 at 3:40
• Is an upside down y axis allowed? – Nick Kennedy Jun 12 at 8:02
• @Nick Yes, no problem – Luis Mendo Jun 12 at 9:12
• "If the Collatz conjecture is false the code can do anything, such as get stuck in an infinite loop or order a pizza." – I guess you want to say "If you hit a counter example for the Collatz conjecture, ..." – Paŭlo Ebermann Jun 12 at 19:50

# Jelly, 35 bytes

r0×€:⁸
×3‘ƊHḂ?Ƭ;Ɲ_/AÞṪçƊ+ṪƲƝẎŒṬx€€3


Try it online!

A pair of links that takes an integer argument and returns an RGB matrix on the (0 to 1) scale. Approach is the same as PBM output below but loses some bytes from the simpler output format.

# Previous PBM answer Jelly, 49 44 bytes

r0×€:⁸
×3‘ƊHḂ?Ƭ;Ɲ_/AÞṪçƊ+ṪƲƝẎŒṬµZL;L;FKṭ“P1


Try it online!

A full program that takes an integer argument and prints the contents of a PBM file.

Thanks to @cairdcoinheringaahing for some nice golfs totally 5 bytes!

# Original SVG-based answer: Jelly, 83 bytes

×3‘ƊHḂ?Ị¬$Ð¿µj”,$ƝKṭṀ,\$“¡×ȯFṗẓ"az⁺Ṭ*,ġẎlḣḂ⁷Ọ]Ẏɦ?÷hṖF.IØṣƘŻÇÄ<,Ḥ:ẆṡṂȮXȷḷ[eʂmJ]»Ỵ¤;"


Try it online!

A full program taking an integer argument and printing an SVG.

For example, with 45:

<svg width="136" height="136"><path stroke="red" fill="none" d="M45,136 136,68 68,34 34,17 17,52 52,26 26,13 13,40 40,20 20,10 10,5 5,16 16,8 8,4 4,2 2,1"/></svg>


• is upside-down y axis allowed? – Razetime Jun 12 at 8:01
• Yes, it is (I just included it in the challenge) – Luis Mendo Jun 12 at 9:14
• 46 bytes – caird coinheringaahing Jun 12 at 19:31
• 44 bytes if we can assume the Collatz conjecture is true (which we can) – caird coinheringaahing Jun 12 at 19:32
• @cairdcoinheringaahing thanks! Yes of course. We have to assume the conjecture is true either way but I’d missed the fact that the input will always be >2 and so the only path to 1 goes via 4, 2, 1 and prevents a bounce back up to 4. – Nick Kennedy Jun 12 at 19:37

# Python 3.8 with turtle, 156 127 bytes

Thanks to Noodle9 for catching a mistake!

from turtle import*
def f(n,x=0):
while~-n:goto(w:=n,n:=[n//2,3*n+1][n%2]);x<1!=clear();setworldcoordinates(0,0,x:=max(x,n),x)


Animation for $$\a_1=27\$$:

• It may just be my computer, but get weird outputs for $3$, $4$, and $650$. Also doesn't clear the screen in between runs. – Noodle9 Jun 12 at 12:24
• @Noodle9 I thought setworldcoordinates would clear the screen, but apparently this isn't the case. Here are my outputs for 3, 4 and 650. For 3 and 4 there is a lot of padding to the bottom/left, but I think this is fine with the rule Axis limits are arbitrary, as long as the graph can be seen fully and clearly – ovs Jun 12 at 13:11
• Makes sense, also $650$ looks fine now. – Noodle9 Jun 12 at 13:18
• Yes, no problem with padding – Luis Mendo Jun 12 at 18:39

# J, 52 bytes

load 'plot'
f=:[:plot[:(}:;}.)(2&|{-:,1+*&3)^:(>&1)^:a:


Try it online!

Wasn't sure if loading the graphics lib counted towards byte count, so I included it.

Here's an image of calling f 27 in the J console:

• Yes, you have to include any needed loads/imports/includes in the byte count, that's one of the big challenges golfing in Python. – Noodle9 Jun 12 at 13:23
• Is the TIO link any use in this case? – Luis Mendo Jun 12 at 18:38
• Not much. I mostly used it to count for me. But you could delete [:plot and run it to verify that it was producing the correct x and y coord lists. – Jonah Jun 12 at 18:40
• Is the f=: necessary? Can you not just have an anonymous function? – caird coinheringaahing Jun 13 at 12:34
• @caird I'm not counting those 3 bytes. I just wanted it to be clear how it's intended to be used, ie, calling it like f 27. If it were anonymous it would need parens around it to be called like that. – Jonah Jun 13 at 14:52

# R >= 4.1, 81 74 bytes

\(x,y=x){while(x>1)y=c(y,x<-c(x/2,3*x+1)[x%%2+1]);plot(y,c(y[-1],NA),"l")}


Try it at RDRR.io!

Note this uses RDRR because TIO doesn’t support graphical output. It also uses function in place of \ since RDRR doesn’t support R 4.1.0 yet.

Thanks to @DominicVanEssen for saving 7 bytes!

• 74 bytes - \(x,y=x){while(x>1)y=c(y,x<-c(x/2,3*x+1)[x%%2+1]);plot(y,c(y[-1],NA),"l")} – Dominic van Essen Jun 11 at 23:29

# Wolfram Language (Mathematica), 70 bytes

Graphics@Line@Last@Reap[#//.a_/;a>1:>Last@Sow@{a,If[2∣a,a/2,3a+1]}]&


-17 bytes from @att

63728127

• Graphics@Line@Partition[NestWhileList[If[OddQ@#,3#+1,#/2]&,#,#>1&],2,1]& for 72 – att Jun 12 at 3:49
• Another -1: Graphics@Line@Partition[NestWhileList[If[2∣#,#/2,3#+1]&,#,#>1&],2,1]& – att Jun 12 at 18:45
• 70 with Sow/Reap: Graphics@Line@Last@Reap[#//.a_/;a>1:>Last@Sow@{a,If[2∣a,a/2,3a+1]}]& – att Jun 13 at 19:29

# Julia using GR, 12199 77 bytes

Even better version by @MarcMush:

using GR
!x=while(X=x[end])>1 plot([x;],(x=[x;X%2>0 ? 3X+1 : X/2])[2:end])end


Improved version thanks to the tips found here:

using GR
c(a)=(i=1;while a[i]>1 a=[a;%(a[i],2)>0 ? 3a[i]+1 : a[i]/2];i+=1end;plot(a[1:i-1],a[2:i]))


What has been done:

• single-line notation for functions -10 bytes
• replace push! by array concatenation -3 bytes
• use input a as array - 6 bytes
• replace end by variable i that stores the length -3 bytes

Original version:

using GR
function c(x) a=[x]
while a[end]>1 push!(a,%(a[end],2)>0 ? 3a[end]+1 : a[end]/2)end
plot(a[1:end-1],a[2:end])end


Calling c(27) gives:

• nice first answer! check out Tips for golfing in Julia, you can reduce your answer a bit more – MarcMush Jun 13 at 22:17
• my turn to shave off 22 bytes ;) 77 bytes – MarcMush Jun 14 at 18:01
• Wow, that's amazing what you did there ... seams like there is still a lot to learn then :D – mapi1 Jun 15 at 13:36
• feel free to include my improvements in your answer and to continue improving it – MarcMush Jun 16 at 17:43

# SageMath, 81 $$\\cdots\$$ 74 71 bytes

Saved 3 bytes thanks to dingledooper!!!

f=lambda n,*r:n-1and f(c:=[n/2,3*n+1][n%2],*r,(n,c))or list_plot(r,1<2)


Try it online!

### f(63728127)

• 71 bytes – dingledooper Jun 12 at 0:55
• @dingledooper Nice one - thanks! :D – Noodle9 Jun 12 at 9:02

# Red, 230 212 bytes

func[n][a: to[]n while[n > 1][append a n: either odd? n[3 * n + 1][n / 2]]to-pair m: last sort copy a view[base 500x500 draw append[line]collect[while[a/2][keep as-pair a/1 / m * 500(first a: next a)/ m * 500]]]]


Try it online!

I don't know if red has a scalable plotting mechanism, but this was what I managed to get using the draw dialect. All outputs are scaled to 500x500 and there may be some inaccuracies for larger inputs due to downscaling and pairs being integers.

In the red interpreter, you will have to redefine the function before each run because the words get messed up.

-4 after using default axes.

-18 bytes from Galen Ivanov.

## Output(n=12) (old)

• I cleaned up you code a little for -18 bytes – Galen Ivanov Jun 12 at 18:23

# Factor + ui.gadgets.charts ui.gadgets.charts.lines math.unicode, 208 204 199 bytes

[ [ [ 3 dupn , odd? [ 3 * 1 + ] [ 2/ ] if dup 1 ≠ ] loop , ] f make chart new over supremum 1 + '[ 0 _ ] dup 2array >>axes line new COLOR: red >>color rot 2 clump >>data add-gadget "" open-window ]


It's quotation (anonymous function) that accepts an integer from the data stack and opens a window with the chart in it. This only works in recent-ish builds of Factor, as the chart gadget is fairly new; I used build 2074. Here's what it looks like for an input of 27:

Unfortunately, the chart gadget doesn't come with any constructors. It requires us to manually calculate axes, and build its subcomponents which themselves don't come with any constructors. This leads to a bit of verbosity.

# HTML + JS, 166 bytes

JS: 156 bytes

HTML: 14 bytes

This is a pretty basic implementation that renders to the DOM using an HTML canvas. A good chunk of the code is spent scaling the output to fit within the canvas. Anyone got any better ideas to handle this?

The input is specified inline in the code, set the number inside x=[...].

x=[9];c=C.getContext2d;c.beginPath();while((z=x[0])-1)x.unshift(z%2?3*z+1:z/2);r=Math.max(...x)/99;x.map((a,i)=>c.lineTo(a/r,99-x[i-1]/r));c.stroke()
<canvas id=C>

• -14: c.beginPath(); is useless here, a path is started automatically at context's init. Now, it's unclear how your script is embedded in the HTML here, so take a +8 for <script> after the canvas opening tag and you end with 160. (Note that in the snippet you'd also need a </script> end tag, but I think it's not necessary if there is a true EOF, I'm on a phone rn and can't test myself.) – Kaiido Jun 12 at 9:08
• A snippet may not be valid in which case your best bet may be a function which takes a and a canvas element as input and outputs by drawing on the passed-in canvas. – Neil Jun 12 at 16:40
• @Kaiido I/O needs to be an image. A 2d context isn't itself an image. – Neil Jun 12 at 23:48
• (A typed array of RGB values would be OK though; that counts as an image.) – Neil Jun 12 at 23:49
• @Kaiido There are two rules at play here: 1) functions that produce output may do so by writing to an (optionally additional) input rather than producing a return value 2) an image object is an acceptable i/o format (see the list of acceptable graphical i/o formats linked in the question). – Neil Jun 13 at 9:23

# Python 3 + matplotlib, 127 bytes

def f(n,r=[]):
k=n
while ~-n:n=[n//2,3*n+1][n%2];r+=[n]
p.plot(*zip(*[[k]+r,r]),'-o');p.show()
import matplotlib.pyplot as p


-5 bytes thanks to @ovs!!!

• If you use n//2 instead of n/2, you don't need to convert n%2 to an integer and the loop condition can be changed to ~-n. – ovs Jun 12 at 5:42
• And pyplot.plot can take x and y coordinates separately, so p.plot([k]+r,r[:-1],'-o') should work (I didn't test that) – ovs Jun 12 at 5:46
• @ovs thanks for the tips!! – wasif Jun 12 at 5:47
• Remove the space between while and ~. Maybe [[k,*r],r]? – Recursive Co. Jun 12 at 6:26

# Python + Pygame, 228 bytes

from pygame import*
d=display
n=int(input())
k=[]
while n>1:k+=[[n,n:=[n//2,3*n+1][n%2]]]
M=max(k)[0]
S=500
g=lambda s:[S*s[0]/M,S*s[1]/M]
s=d.set_mode([S,S])
for i,j in enumerate(k):draw.line(s,[99]*3,g(k[i-1]),g(j))
d.update()


No TIO link because Pygame is not supported there.

Reversed y-axis.

I could save one byte by setting S to 99 or something, but I chose not to for easier viewing. I could also change [99]*3 to [9]*3` but I chose not to for easier viewing.

Here is an example for input 63728127: