☰

Collat​​z 猜想的有向图

tag-icon • tag-icon tikz-pgf tikz-arrows nodes
Collat​​z 猜想的有向图

以下有向图包含 Collat​​z 猜想的样本轨道。我认为它最初可能是用 Mathematica 生成的。

在此处输入图片描述

是否可以使用 Latex 制作类似的东西？如果可以，有什么范例可以遵循吗？我在这个网站上找不到类似的例子。谢谢。

答案1

Lua(La)TeX 可让您通过 TikZgraph和graphdrawing库做一些很棒的事情。我发布的内容是第一次尝试，我想我的 Lua 比我的 LaTeX 更好，所以花哨的东西由您决定。

%!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}

在此处输入图片描述

答案2

这是一种sagetex方法。

\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}

在 Cocalc 中运行我们得到： 在此处输入图片描述

使用有向图表示涉及有向边（弧）及其弯曲。要摆脱它，您必须创建一个图形并使用 tikz 来获取直的有向边。这会花费更多时间。SAGE 是一个计算机代数系统，不属于 LaTeX。通用图形和有向图的文档是这里。探索的最佳方式sagetex是通过免费可钙帐户。的文档sagetex位于 CTAN这里。

答案3

（这个答案是基于对早期研究的回答这个问题， 经过用户 Jairo A. del Rio。这可能有些多余，但我几个小时前就开始打这个字了，所以最好把它写完……）

用于绘图的 TeX/LaTeX 软件包之一是蒂克兹，对此我了解不多，但通常你可以通过指定节点的位置来绘制图表，并在它们之间绘制路径（参见TikZ 的摩尔斯电码在拖船)，以及各种快捷方式。

这里我们可能不想手动（计算并）指定每个位置的位置：为此，TikZ 对算法图形绘制有一些支持，特别是它的“树布局”在这里很合适。例如，您可以获得以下结果：

简单的

输入如下内容：

\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}

（仅展示了如何指定边的各种选项：我们可以链接多个边，空格无关紧要，重复的边被忽略，等等。）

为了更接近问题中的图像：

  • 请注意上图中的小问题，即 2→1 边向左绘制：我认为原因是，由于“2”是第一个提到的节点（在“2 —> 1”边中），因此它被视为树的根。为了避免这种情况，我们可以事先声明节点“1”，或者从不可见的边开始，如“1 -> [draw=none] 1; ”，以便它成为树的根。

  • 虽然我们已经通过使用图形绘制（树形布局）避免了必须指定位置，但避免必须指定 Collat​​z 序列的所有边缘将更加方便。如果使用 LuaTeX，可以使用 Lua 轻松完成此操作（见下文）。

  • 还有另一个问题：如果我们尝试使用 Lua 或宏来填充“…” \graph[tree layout, grow=left]{…}，我们会遇到扩展问题（当 TeX 看到\graph它需要能够找到前面已经扩展的文本时）。为了解决这个问题，我们可以使用适当的\expandafters 序列（参见这或者这问题），或者我们可以直接从 Lua 输出整个内容。

从这些想法出发，我们可以提出一个解决方案。将以下内容放入名为的文件中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

然后你的.tex文档可以是：

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

结果：

真实的

编辑：如果不使用 来避免重复边next，即使在 n=40 时也会花费更长的时间。我尝试了另一种优化：立即使用 打印每条边，而tex.sprint不是累积所有这些字符串并在最后打印一次，但即使在 n=10000 时也没有明显的区别（运行时间约为 3 分钟）。我猜大部分时间是在 TikZ 本身内部花费的（在 Lua 将边放入 TeX 流之后），并且在 Lua 端连接字符串相对较快。

相关内容