กราฟกำกับสำหรับ Collatz Conjecture

Question

กราฟกำกับต่อไปนี้มีวงโคจรตัวอย่างของ Collatz Conjecture ฉันคิดว่ามันอาจถูกผลิตขึ้นโดย Mathematica

เป็นไปได้ไหมที่จะผลิตสิ่งที่คล้ายกับลาเท็กซ์ ถ้าเป็นเช่นนั้นมีกระบวนทัศน์ที่จะปฏิบัติตามหรือไม่? ฉันไม่พบตัวอย่างที่คล้ายกันในไซต์นี้ ขอบคุณ.

Answer 1

Lua (La) TeX ให้คุณทำสิ่งดีๆผ่าน TikZ graphและ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}

Answer 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 เราได้รับ:

การแทนค่าโดยใช้ digraphs เกี่ยวข้องกับขอบกำกับ (ส่วนโค้ง) โดยมีส่วนโค้งงอ ในการกำจัดสิ่งนั้นคุณจะต้องสร้างกราฟและใช้ tikz เพื่อให้ได้ขอบที่ตรงและตรง จะต้องเสียเวลาอีกสักหน่อย SAGE เป็นระบบพีชคณิตของคอมพิวเตอร์ซึ่งไม่ได้เป็นส่วนหนึ่งของ LaTeX เอกสารสำหรับกราฟทั่วไปและ digraphs เป็นที่นี่ วิธีที่ดีที่สุดในการสำรวจsagetexคือผ่านบัญชีCocalcฟรี เอกสารสำหรับการsagetexอยู่บน CTAN ที่นี่

Answer 3

( คำตอบนี้อ้างอิงจากการศึกษาคำตอบก่อนหน้านี้สำหรับคำถามนี้โดยผู้ใช้ Jairo A. del Rioอาจจะซ้ำซ้อน แต่ฉันได้เริ่มพิมพ์ข้อความนี้เมื่อไม่กี่ชั่วโมงที่ผ่านมาดังนั้นอาจจะเสร็จสิ้น ... )

หนึ่งในแพ็คเกจ TeX / LaTeX สำหรับการวาดภาพคือTikZซึ่งฉันไม่รู้มากนักยกเว้นว่าโดยปกติคุณสามารถวาดไดอะแกรมโดยระบุตำแหน่งของโหนดและวาดเส้นทางระหว่างพวกเขา (ดูรหัสมอร์สของ TikZในTUGboat ) ด้วยทางลัดต่างๆ

ในที่นี้เราอาจไม่ต้องการ (คำนวณและ) ระบุตำแหน่งของแต่ละตำแหน่งด้วยตนเองด้วยเหตุนี้ 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; ” เพื่อให้มันกลายเป็นรากของต้นไม้

• แม้ว่าเราจะหลีกเลี่ยงที่จะไม่ต้องระบุตำแหน่งโดยใช้การวาดกราฟ (โครงร่างต้นไม้) แต่ก็ยังสะดวกกว่าที่จะหลีกเลี่ยงการระบุขอบทั้งหมดของลำดับ Collatz สิ่งนี้สามารถทำได้อย่างง่ายดายด้วย Lua หากใช้ LuaTeX (ดูด้านล่าง)

• ยังมีริ้วรอยอื่น ๆ อีก: ถ้าเราพยายามเติมคำว่า“ …” ในการ\graph[tree layout, grow=left]{…}ใช้ Lua หรือมาโครเราจะพบปัญหาการขยายตัว (เมื่อถึงเวลาที่ 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 = 10,000 (เวลาทำงานประมาณ 3 นาที) ฉันเดาว่าเวลาส่วนใหญ่อยู่ใน TikZ เอง (หลังจาก Lua วางขอบลงในสตรีม TeX) และการเข้าร่วมสตริงที่ฝั่ง Lua นั้นค่อนข้างเร็ว