2b:null 2c:["$","title",null,{"children":"Collatz Conjecture | Christophe Yamahata | Observable"}] 31:T4d1,graph_Collatz = { const sequence = collatzSequence(n).numbers; const maxNumber = Math.max(...sequence); const magnitude = Math.floor(Math.log10(maxNumber)); const rounded = Math.ceil(maxNumber / Math.pow(10, magnitude)) * Math.pow(10, magnitude); const roundedMax = Math.ceil(maxNumber / Math.pow(10, magnitude)) * Math.pow(10, magnitude); const tickInterval = 10 ** magnitude; const customTicks = [1].concat(d3.range(tickInterval, roundedMax + tickInterval, tickInterval)); const graph = Plot.plot({ width: 500, height: 300, marginLeft: 80, marks: [ Plot.ruleX([0, sequence.length-1]), Plot.ruleY([1, roundedMax]), Plot.line(sequence, { x: (d, i) => i, y: d => d, stroke: "steelblue", strokeWidth: 0.8 }), Plot.dot(sequence, { x: (d, i) => i, y: d => d, fill: "steelblue", r: 2 }) ], x: { label: "Step (Index)", domain: [0, sequence.length-1], tickFormat: d => d }, y: { label: "Number", domain: [1, roundedMax], ticks: customTicks, tickFormat: d => d.toString(), nice: true, labelOffset: 50 }, }); return graph; } 32:T44d,function generateCollatzTree(n) { const root = { name: '1', children: [] }; // Root node as "1" // Find or create a node in the tree, skip adding "1" function findOrCreateNode(parent, value) { const stringValue = value.toString(); // Skip adding the node if its value is "1" if (stringValue === '1') { return parent; } let childNode = parent.children.find(child => child.name === stringValue); if (!childNode) { childNode = { name: stringValue, children: [] }; parent.children.push(childNode); } return childNode; } // Generate sequences and build the tree for each number from 1 to n for (let i = 1; i <= n; i++) { const sequence = collatzSequence(i).numbers; // Call the external function let currentNode = root; // Start with the same root node // Iterate through the sequence in reverse to build the tree for (let j = sequence.length - 1; j >= 0; j--) { currentNode = findOrCreateNode(currentNode, sequence[j]); // Find or create node } } return root; // Return the complete tree structure } 33:T1602,// Based on https://observablehq.com/@d3/radial-tree // The function was adapted for this notebook function Tree(data, sequence, { // data is either tabular (array of objects) or hierarchy (nested objects) path, // as an alternative to id and parentId, returns an array identifier, imputing internal nodes id = Array.isArray(data) ? d => d.id : null, // if tabular data, given a d in data, returns a unique identifier (string) parentId = Array.isArray(data) ? d => d.parentId : null, // if tabular data, given a node d, returns its parent’s identifier children, // if hierarchical data, given a d in data, returns its children tree = d3.tree, // layout algorithm (typically d3.tree or d3.cluster) separation = tree === d3.tree ? (a, b) => (a.parent == b.parent ? 1 : 2) / a.depth : (a, b) => a.parent == b.parent ? 1 : 2, sort, // how to sort nodes prior to layout (e.g., (a, b) => d3.descending(a.height, b.height)) label, // given a node d, returns the display name title, // given a node d, returns its hover text link, // given a node d, its link (if any) linkTarget = "_blank", // the target attribute for links (if any) width = 640, // outer width, in pixels height = 400, // outer height, in pixels margin = 60, // shorthand for margins marginTop = margin, // top margin, in pixels marginRight = margin, // right margin, in pixels marginBottom = margin, // bottom margin, in pixels marginLeft = margin, // left margin, in pixels radius = Math.min(width - marginLeft - marginRight, height - marginTop - marginBottom) / 2, // outer radius r = 3, // radius of nodes padding = 1, // horizontal padding for first and last column fill = "#999", // fill for nodes fillOpacity, // fill opacity for nodes stroke = "#555", // stroke for links strokeWidth = 1.5, // stroke width for links strokeOpacity = 0.4, // stroke opacity for links strokeLinejoin, // stroke line join for links strokeLinecap, // stroke line cap for links halo = "#fff", // color of label halo haloWidth = 3, // padding around the labels } = {}) { // If id and parentId options are specified, or the path option, use d3.stratify // to convert tabular data to a hierarchy; otherwise we assume that the data is // specified as an object {children} with nested objects (a.k.a. the “flare.json” // format), and use d3.hierarchy. const root = path != null ? d3.stratify().path(path)(data) : id != null || parentId != null ? d3.stratify().id(id).parentId(parentId)(data) : d3.hierarchy(data, children); // Sort the nodes. if (sort != null) root.sort(sort); // Compute labels and titles. const descendants = root.descendants(); const L = label == null ? null : descendants.map(d => label(d.data, d)); // Compute the layout. tree().size([2 * Math.PI, radius]).separation(separation)(root); const svg = d3.create("svg") .attr("viewBox", [-marginLeft - radius, -marginTop - radius, width, height]) .attr("width", width) .attr("height", height) .attr("style", "max-width: 100%; height: auto; height: intrinsic;") .style("border", "1px solid #aaa") .attr("font-family", "sans-serif") .attr("font-size", 10); svg.append("g") .attr("fill", "none") .attr("stroke", stroke) .attr("stroke-opacity", strokeOpacity) .attr("stroke-linecap", strokeLinecap) .attr("stroke-linejoin", strokeLinejoin) .attr("stroke-width", strokeWidth) .selectAll("path") .data(root.links()) .join("path") .attr("d", d3.linkRadial() .angle(d => d.x) .radius(d => d.y)); const targetValue = n.toString(); const simplify = !displayNumbers && n > 26; r = n > 26 ? 1.2 : r; const r2 = n > 26 ? 3*r : 1.6*r; const r3 = n > 26 ? 1.8*r : 1.2*r; const node = svg.append("g") .selectAll("a") .data(root.descendants()) .join("a") .attr("xlink:href", link == null ? null : d => link(d.data, d)) .attr("target", link == null ? null : linkTarget) .attr("transform", d => `rotate(${d.x * 180 / Math.PI - 90}) translate(${d.y},0)`); node.append("circle") .attr("fill", (d, i) => L[i] === targetValue ? "blue" : L[i] === "1" ? "green" : sequence.includes(d.data.name) ? "orange" : d.children ? stroke : fill) .attr("r", (d, i) => (L[i] === targetValue || L[i] === "1") ? r2 : (sequence.includes(d.data.name) || !d.children) ? r3 : r); if (L) { node.append("text") .attr("transform", (d, i) => (L[i] === targetValue || L[i] === "1") ? `rotate(${-d.x*180/Math.PI + 90})` : `rotate(${d.x > Math.PI / 2 && d.x < 3 * Math.PI / 2 ? -90 : 90})` ) .attr("dy", "0.32em") .attr("x", d => d.x < Math.PI === !d.children ? 6 : -6) .attr("text-anchor", d => d.x < Math.PI === !d.children ? "start" : "end") .attr("paint-order", "stroke") .attr("stroke", halo) .attr("stroke-width", haloWidth) .attr("opacity", (d, i) => (L[i] === targetValue || L[i] === "1") ? "1" : !d.children ? "0.8" : !simplify? "0.4" : "0") .attr("font-size", (d, i) => (L[i] === targetValue || L[i] === "1") ? "18px" : !d.children ? "12px" : "8px") .attr("fill", (d, i) => L[i] === targetValue ? "blue" : L[i] === "1" ? "green" : "black") // .text((d, i) => L[i]); node.each(function(d, i) { if (L[i] === targetValue || L[i] === "1" || !d.children) { d3.select(this).raise(); } }); } return svg.node(); }34:[] 2f:{"id":"e644c9bfd183de51","slug":"collatz-conjecture","title":"Collatz Conjecture","thumbnail":"340aad8a52c98777619696bbde52e64f33bd29629b5e5e76d665adec7f12a025","access_level":"public","create_time":"$D2024-10-10T22:52:04.226Z","update_time":"$D2024-10-11T14:00:29.519Z","view_time":null,"first_public_time":"$D2024-10-11T08:22:13.221Z","fork":true,"stars":0,"starred":false,"owner":{"type":"team","id":"dd67891d326bcfb1","login":"christophe-yamahata","name":"Christophe Yamahata","avatar_url":"https://avatars-next.observableusercontent.com/8256ac716aa8395babba412b2835913d186874fa4190df57a4a28f2e60129876","tier":"starter_2024"},"version":1168,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"06f083eba60f5a76","login":"christophe-yamahata","name":"Christophe Yamahata","avatar_url":"https://avatars-next.observableusercontent.com/8256ac716aa8395babba412b2835913d186874fa4190df57a4a28f2e60129876","tier":null}],"members":[{"type":"individual","id":"06f083eba60f5a76","login":"christophe-yamahata","name":"Christophe Yamahata","avatar_url":"https://avatars-next.observableusercontent.com/8256ac716aa8395babba412b2835913d186874fa4190df57a4a28f2e60129876","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"subscribed":null,"forks":1,"collection":{"id":"19262496cb287a16","slug":"mathematics","title":"Mathematics","owner":{"id":"dd67891d326bcfb1","login":"christophe-yamahata","name":"Christophe Yamahata"}},"type":"notebook","body":{"title":"Collatz Conjecture","cells":[{"id":513,"value":"# Collatz Conjecture \n## Visualizing the Collatz Conjecture on a Radial Cluster Tree\n\nThe Collatz conjecture, also known as the “${tex`3n + 1`} problem” or the “Syracuse conjecture,” is one of the most famous unsolved problems in mathematics — a puzzle that continues to perplex mathematicians and enthusiasts alike.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":547,"value":"### Collatz Function\n\nTo formulate the problem, we define the function ${tex`s(n)`} as follows:\n\n${tex.block`s(n) = \\begin{cases} \n\\dfrac{n}{2} & \\text{if } n \\text{ is even} \\\\[9pt] \n3n + 1 & \\text{if } n \\text{ is odd} \n\\end{cases}, \\quad \\text{where } n \\in \\mathbb{N}^+`}\n\nThe Collatz conjecture states that for any positive integer ${tex`n`}, repeatedly applying ${tex`s(n)`} will eventually lead to the number 1, regardless of the starting value.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":563,"value":"

\n### Visualization Style: Radial Cluster Tree\nThe Collatz conjecture can be visualized using a radial tree (see also d3-hierarchy). Below, we display the sequences for all starting positive integers between 1 and ${n}.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":767,"value":"#### Example: Starting Integer ${tex`n`} = ${n}\n\nFor the starting number **${tex`n`} = ${n}**, the sequence generated by repeatedly applying the function ${tex`s(n)`} is:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":570,"value":"yield html`

${collatzSequence(n).sequence.join(' → ')}

`; // Display formatted sequence","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":574,"value":"It takes a total of **${collatzSequence(n).numbers.length-1} step${collatzSequence(n).numbers.length-1 > 1?`s`:``}** for the sequence to reduce from **${tex`n`} = ${n}** to **1**. This sequence reaches a peak value of **${Math.max(...collatzSequence(n).numbers)}** before eventually descending to 1.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":873,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":782,"value":"
\n#### Visualization\nThe graph below shows all numbers and their respective sequences in a radial tree layout.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":364,"value":"viewof n = Inputs.range([3, 500], {value: 23, step: 1, label: html`Starting Integer`})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":614,"value":"viewof treeStyle = Inputs.radio([\"Cluster\", \"Tree\"], {label: html`Layout algorithm`, value: \"Cluster\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":539,"value":"viewof displayNumbers = Inputs.toggle({\n label: htl.html`Display all numbers`,\n value: false\n});","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":82,"value":"// Create the radial tree visualization using the imported Tree function\nCollatzTree = Tree(generateCollatzTree(n), collatzSequence(n).numbers.map(String), {\n label: d => d.name,\n width: 1000,\n height: 1000,\n fill: \"#ff00ff\",\n stroke: \"#bbb\",\n r: 2.5,\n tree: treeStyle ==\"Tree\"? d3.tree: d3.cluster,\n});","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":517,"value":"---\n## Appendix","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":555,"value":"function collatzSequence(n) {\n const numbers = [n], sequence = [n % 2 === 0 ? n : `${n}`]; \n \n while (n !== 1) {\n n = n % 2 === 0 ? n / 2 : 3 * n + 1;\n numbers.push(n); \n sequence.push(`${n % 2 === 0 ? n : `${n}`}`); \n }\n\n return { numbers, sequence };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":27,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":60,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W34","stdlib":"1","titling":"auto"}} 30:"$2f:body"