Directed Graph for the Collatz Conjecture

Question

The following directed graph contains sample orbits of the Collatz Conjecture. I think it may have been originally produced with Mathematica.

Is it possible to produce something similar with Latex? If so, are there any paradigms to follow? I couldn't find a similar example on this site. Thank you.

Answer 1

Lua(La)TeX lets you do nice things via TikZ's graph and graphdrawing libraries. What I post is a first attempt and my Lua is better than my LaTeX I guess, so bells and whistles are up to you.

%!TEX program = lualatex
\documentclass[tikz]{standalone}
\usepackage{luacode}
\begin{luacode*}
--To avoid clashes
--A ConTeXt habit btw
userdata = userdata or {}

--This will actually give n + 1 levels as 1 is already included
function userdata.collatz_tree(levels)
local tree = {value = 1, children = {}}
--To avoid repetitions and loops
local hash = {} 
local function inner(t, n)
if n > 0 then
if not hash[t.value] then
hash[t.value] = true

--math.floor is not really necessary, but Lua numbers work in mysterious ways. I go for the safe option
if not hash[math.floor((t.value -1 ) // 3)] then 
if (t.value - 1) % 3 == 0 and t.value ~= 4 and t.value ~= 1 then
table.insert(t.children, {value = (math.floor(t.value-1)//3), children = {}})
end 
end

if not hash[2*t.value] then
table.insert(t.children, {value = 2*t.value, children = {}})
end

for _,v in ipairs(t.children) do
inner(v, n-1)
end
end
end
return t 
end
return inner(tree, levels)
end

-- So TikZ draws our structure
function userdata.print_tree(t)
if #t.children > 0 then
for _,v in ipairs(t.children) do
tex.sprint(t.value .. "->" .. v.value .. ";")
userdata.print_tree(v,result)
end
end
end
\end{luacode*}
\usetikzlibrary{graphs,graphs.standard,graphdrawing}
\usegdlibrary{trees}
\begin{document}
%https://tex.stackexchange.com/a/235376/226564
\def\zz#1{%
%Add options when needed
\begin{tikzpicture}%
\graph[tree layout, grow=left]{#1};
\end{tikzpicture}}
%Larger numbers require more time.
\expandafter\zz\expandafter{\directlua{userdata.print_tree(userdata.collatz_tree(10))}}
\end{document}

Answer 2

Here's a sagetex approach.

\documentclass[border={2mm 2mm 8mm 8mm}]{standalone}
\usepackage{sagetex,xcolor,tikz,tkz-graph}
\begin{document}
\begin{sagesilent}
V=[i for i in range(1,26)]
D = DiGraph([])
D.add_vertices(V)

def Collatz(D,v):
    while v != 1:
        if v%2==0:
            a = v/2
            D.add_vertex(a)
            D.add_edge(v,a)
            v = a
        else:
            a = 3*v+1
            D.add_vertex(a)
            D.add_edge(v,a)
            v = a

    return D

for i in range(2,26):
    Collatz(D,i)

D.set_latex_options(graphic_size=(20,20))
D.set_pos(D.layout(layout='tree'))
\end{sagesilent}
\begin{tikzpicture}
\tikzset{EdgeStyle/.append style = {color = blue!60, line width=1pt}}
\sage{D}
\end{tikzpicture}
\end{document}

Running in Cocalc we get:

Representation using digraphs involves directed edges (arcs) with a bend to them. To get rid of that you would have to create a graph and use tikz to get straight, directed edges. This would be a bit more time consuming. SAGE is a computer algebra system which is not a part of LaTeX. The documentation for generic graphs and digraphs is here. The best way to explore sagetex is through a free Cocalc account. The documentation for sagetex is on CTAN here.

Answer 3

(This answer is based on studying the earlier answer to this question, by user Jairo A. del Rio. It's probably redundant, but I had starting typing this a few hours ago so might as well finish it up…)

One of the TeX/LaTeX packages for drawing is TikZ, about which I don't know much, except that normally you can draw diagrams by specifying the positions of nodes, and drawing paths between them (see The Morse code of TikZ in TUGboat), with various shortcuts.

Here we probably don't want to (compute and) specify the position of each position manually: for this, TikZ has some support for algorithmic graph drawing, in particular its “tree layout” is suitable here. For example, you can obtain the following result:

with the following input:

\documentclass[tikz]{standalone}
\usetikzlibrary{graphs,graphdrawing}
\usegdlibrary{trees}
\begin{document}

\begin{tikzpicture}
  \graph[tree layout, grow=left]{
    2 -> 1;
    3 -> 10 -> 5;
    4 -> 2;
    5 -> 16 -> 8; 8 -> 4 -> 2;
    64 -> 32 -> 16;
  };
\end{tikzpicture}

\end{document}

(Just showed a variety of options for how we can specify the edges: we can chain multiple of them, whitespace doesn't matter, duplicate edges are ignored, etc.)

To get something closer to the image in the question:

• Note the slight problem in the above graph, which is that the 2→1 edge is drawn going leftwards: I think the reason is that, because “2” was the first node mentioned (in the “2 —> 1” edge), it is treated as the root of the tree. To avoid this, we can either declare the node “1” beforehand, or start with an invisible edge like “1 -> [draw=none] 1; ” so that it becomes the root of the tree.

• Though we have avoided having to specify the positions by using graph drawing (tree layout), it would further be convenient to avoid having to specify all the edges of the Collatz sequence. This can be done easily with Lua, if using LuaTeX (see below).

• There's another wrinkle: if we try to fill in the “…” in \graph[tree layout, grow=left]{…} using Lua or a macro, we run into issues of expansion (by the time TeX sees \graph it needs to be able to find already-expanded text ahead). To work around this, we can use an appropriate sequence of \expandafters (see this or this question), or we can simply output the whole thing from Lua.

From these ideas, we can assemble a solution. Put the following in a file called collatz.lua:

function collatz_edges(limit)
    -- Returns edges for the numbers 1 to `limit` under the Collatz function.
    -- E.g. for limit = 6, returns the following string (without linebreaks):
    --     1 -> [draw=none] 1; 
    --     2 -> 1; 
    --     3 -> 10; 10 -> 5; 5 -> 16; 16 -> 8; 8 -> 4; 4 -> 2;
    --     6 -> 3;
    local edges = {'1 -> [draw=none] 1;'}
    local next = {}
    next[1] = 1
    for x = 2, limit do
        -- All edges x -> y
        while not next[x] do
            if x % 2 == 0 then y = x // 2 else y = 3 * x + 1 end
            table.insert(edges, string.format('%s -> %s; ', x, y))
            next[x] = y
            x = y
        end
    end
    return table.concat(edges)
end

function collatz_graph(limit)
    return string.format([[
        \begin{tikzpicture}
            \graph[tree layout, grow=left]{%s};
        \end{tikzpicture}]], collatz_edges(limit))
end

And then your .tex document can be:

\documentclass[tikz]{standalone}
\usetikzlibrary{graphs,graphdrawing}
\usegdlibrary{trees}
\directlua{dofile('collatz.lua')}
\begin{document}
\directlua{tex.sprint(collatz_graph(25))}
\end{document}

Result:

---

Edit: Without the optimization to avoid duplicate edges using next, it takes significantly longer even at say n=40. I tried another optimization: that of printing each edge immediately with tex.sprint instead of accumulating all these strings and printing them once at the end, but it makes no noticeable difference even at n=10000 (running time of about 3 minutes). I guess that most of the time is taken inside TikZ itself (after Lua puts the edges into the TeX stream), and joining strings on the Lua side is relatively fast.