2c:null 2d:["$","title",null,{"children":"Divisibility lattice | Bryan Gin-ge Chen | Observable"}] 32:Tedd,svg = { const svg = d3.select(DOM.svg(width, params.height*width/params.width)) .attr('viewBox', `0 0 ${params.width} ${params.height}`); // horizontal red lines const gHoriz = svg.append('g') .style('fill', 'none') .style('stroke', '#ffaaaa'); gHoriz.selectAll('path').data(horiz).enter() .append('path') .attr('d', d => `M0,${d}L${params.width},${d}`); const gDivis = svg.append('g') .style('fill', 'none') .style('stroke-width', 1.5) .style('stroke', '#0000cc'); function drawSegment([x1,y1], [x2,y2]) { return `M${x1.toFixed(2)},${y1.toFixed(2)}L${x2.toFixed(2)},${y2.toFixed(2)}`; } // warning: mutates seq (rather mildly) seq.forEach(d => d.ppos = place2(d.pos)); // edges const gSeq = gDivis.selectAll('g .edge').data(seq).enter() .append('g') .classed('edge', true); const pathSeq = gSeq.selectAll('path').data( ({ppos, children}) => children.map(({ppos:childppos}) => [ppos, childppos])).enter() .append('path') .attr('d', ([ppos, childppos]) => drawSegment(ppos, childppos)); // nodes const gSeq2 = gDivis.selectAll('g .node').data(seq).enter() .append('g') .classed('node', true) .attr('cursor', 'pointer') .attr('transform', ({ppos:[x,y]}) => `translate(${x},${y})`) .on('mousedown', () => d3.event.preventDefault()) // prevent text selection .on('click', nodeClick); gSeq2.append('title') .text(({val}) => val); const circSeq = gSeq2.append('circle') .attr('fill', '#ffffff') .attr('stroke', '#000000') .attr('r', config.r); const getFontSize = ({val}) => fontSizes.reduce((acc, [thresh, size]) => (thresh <= val) ? size : acc, 0); const textSeq = gSeq2.append('text') .attr('fill', '#000000') .attr('stroke', 'none') .attr('text-anchor', 'middle') .attr('dominant-baseline', 'central') .attr('font-size', getFontSize) .text(({val}) => `${val}`); // interactivity, LCM, GCD function nodeClick(data) { d3.event.preventDefault(); if (clickedNodes.has(data.val)) { // deselect clickedNodes.delete(data.val); } else { // select clickedNodes.set(data.val,true); } highlight(); } // update highlighting function highlight() { // reset circSeq .attr('fill', '#ffffff') .attr('r', config.r); textSeq .attr('fill', '#000000') .attr('font-size', getFontSize); if (clickedNodes.size > 0) { // clicked circSeq.filter(({val}) => clickedNodes.has(val)) .attr('fill', '#555555') .attr('r', 2*config.r); textSeq.filter(({val}) => clickedNodes.has(val)) .attr('fill', '#ffffff') .attr('font-size', d => 2*getFontSize(d)); // highlight GCD const filtGCD = ({val}) => Array.from(clickedNodes.keys()) .every((clickVal) => val !== clickVal && (clickVal % val === 0)); circSeq.filter(filtGCD) .attr('fill', '#FF0000') .attr('r', 1.5*config.r); textSeq.filter(filtGCD) .attr('fill', '#ffffff') .attr('font-size', d => 1.5*getFontSize(d)); // highlight LCM const filtLCM = ({val}) => Array.from(clickedNodes.keys()) .every((clickVal) => val !== clickVal && (val % clickVal === 0)); circSeq.filter(filtLCM) .attr('fill', '#aa00aa') .attr('r', 1.5*config.r);; textSeq.filter(filtLCM) .attr('fill', '#ffff00') .attr('font-size', d => 1.5*getFontSize(d)); } } // remove selected nodes that no longer appear Array.from(clickedNodes.keys()).forEach(v => { if (!seq.some(({val}) => val === v)) clickedNodes.delete(v); }); highlight(); return svg.node(); }33:T633,md`This notebook is a modified port of [David Eppstein's "Regular Divsibility Lattice" on Wikipedia](https://commons.wikimedia.org/wiki/File:Regular_divisibility_lattice.svg), which was inspired by diagrams in [Erkki Kurenniemi](https://en.wikipedia.org/wiki/Erkki_Kurenniemi)'s paper ["Chords, scales, and divisor lattices"](https://beige.org/projects/dimi/CSDL2.pdf) (which appears to have originally been a Mathematica notebook). I was inspired to make this by [@mbostock's 'Divisibility Network'](https://beta.observablehq.com/@mbostock/divisibility-network). The image above displays all numbers below ${Math.floor(config.limit)} whose only prime divisors are in the input array \`primes\`, namely [${primes.join(',')}], with edges connecting two numbers if they are related by a single multiplication or division by one of those primes. (The original shows [regular numbers](https://en.wikipedia.org/wiki/Regular_number) up to 400, where "regular" here means that the list of prime divisors is [2,3,5].) The y-coordinates of the numbers are proportional to their logarithms; note the bunching of the red horizontal lines which are drawn at the heights of 1, 2, 3, ..., 10, 20, 30, ..., 100, 200, ..., 1000, 2000, ... Clicking on a number selects it and highlights its divisors in red and its multiples in purple. Selecting multiple numbers highlights the common divisors and common multiples. Note how the [GCD](https://en.wikipedia.org/wiki/Greatest_common_divisor) and the [LCM](https://en.wikipedia.org/wiki/Least_common_multiple) appear at the extreme points of those sets.`34:T592,md`The title turns out to be a little math pun: the term ["lattice"](https://en.wikipedia.org/wiki/Lattice_%28order%29) can be understood in the sense of [order theory](https://en.wikipedia.org/wiki/Order_theory), that is, it can refer to a certain formal mathematical structure with "join" and "meet" operations. Indeed, in fancy terms, this notebook depicts a [Hasse diagram](https://en.wikipedia.org/wiki/Hasse_diagram) of (a small portion of) the lattice structure on the natural numbers generated by the divisibility relation. However, the fact that the image resembles a lattice in the informal sense (a grid) is no accident! Every number with prime factors coming from a restricted set ${tex`\{p_1,\dots,p_n\}`} can be written in the form ${tex`p_1^{q_1}p_2^{q_2}\cdots p_n^{q_n}`} and so we can also represent it by the vector of exponents ${tex`(q_1,\dots,q_n)`}. These points lie at the vertices of a standard integer grid in ${tex`n-`}dimensions, and multiplying or dividing by a prime ${tex`p_j`} is equivalent to incrementing or decrementing the corresponding component of the exponent vector. Geometrically, this is the same as moving along an edge of the ${tex`n-`}dimensional grid. The logarithmic layout causes the edges corresponding to multiplication by the same prime to be parallel, and so by the above discussion, the resulting image is a projection of the ${tex`n-`}dimensional grid to your screen. ` 35:[] 30:{"id":"7ee733f6b61368b3","slug":"divisibility-lattice","title":"Divisibility lattice","thumbnail":"061d6e59db04e34ec650d69783f09a6dd638f1130cc8c71695c3acb092f075dd","access_level":"public","create_time":"$D2018-12-12T18:23:14.839Z","update_time":"$D2019-03-08T00:17:41.549Z","view_time":null,"first_public_time":"$D2018-12-14T00:29:19.950Z","has_unpublished_edits":null,"fork":false,"stars":12,"starred":false,"owner":{"type":"team","id":"d2fd23101beb2a61","login":"bryangingechen","name":"Bryan Gin-ge Chen","avatar_url":"https://avatars-next.observableusercontent.com/73f0dccc0b7fc5c845e6a52a58e01a2ae432cc529aaada0d10ab602137e603c0","tier":"starter_2024"},"version":733,"publish_version":733,"role":null,"authored":false,"authors":[{"type":"individual","id":"5c13a1a27cf52564","login":"bryangingechen","name":"Bryan Gin-ge Chen","avatar_url":"https://avatars-next.observableusercontent.com/73f0dccc0b7fc5c845e6a52a58e01a2ae432cc529aaada0d10ab602137e603c0","tier":null}],"members":[{"type":"individual","id":"5c13a1a27cf52564","login":"bryangingechen","name":"Bryan Gin-ge Chen","avatar_url":"https://avatars-next.observableusercontent.com/73f0dccc0b7fc5c845e6a52a58e01a2ae432cc529aaada0d10ab602137e603c0","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":{"id":"1bd9754ae5c8b895","slug":"morsels","title":"Morsels","owner":{"id":"d2fd23101beb2a61","login":"bryangingechen","name":"Bryan Gin-ge Chen"}},"type":"notebook","body":{"titling":"auto","title":"Divisibility lattice","cells":[{"id":0,"value":"md`# Divisibility lattice`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":23,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":96,"value":"viewof primes = {\n const form = html`

primes:`;\n [2,3,5,7,11,13,17,19,23,29,31].forEach(p => form.appendChild(\n html`${p}`));\n\n form.onchange = (event) => {\n form.value = [];\n for (let checkbox of form.querySelectorAll('input')) {\n if (checkbox.checked)\n form.value.push(parseInt(checkbox.id));\n }\n form.dispatchEvent(new CustomEvent('input'));\n };\n \n form.value = [2,3,7,13];\n return form;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":570,"value":"viewof lim = {\n const div = html`maximum number = 2000:
\n `;\n const span = div.querySelector('span');\n const inp = div.querySelector('input');\n inp.oninput = (ev) => {\n div.value = inp.value;\n span.textContent = `max number = ${Math.floor(Math.exp(inp.value/1000))}`;\n div.dispatchEvent(new CustomEvent('input'));\n };\n \n div.value = inp.value;\n return div;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":14,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":723,"value":"{\n const num = primes.reduce((a,b) => a*b,1);\n const markd = md`Since \\`primes\\` is currently [${primes.join(',')}], the image shows a ${primes.length}-dimensional grid, and if you select ${num}=${primes.map(p => p).join('×')}, the red highlighted numbers will sit at the corners of a ${primes.length}-dimensional hypercube.`;\n const a = markd.querySelector('a');\n a.onclick = () => {\n mutable clickedNodes = new Map([[num,true]]);\n }\n \n return markd;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":79,"value":"config = {\n const scale = 128/1363*width*0.9;\n return ({r: 17/1363*width*0.9, margin: 20*width/1363, xScale: scale, yScale: scale, skew: Math.log(2), \n limit: navigator.userAgent.match('HeadlessChrome') ? 600 : Math.exp(lim/1000)});\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":178,"value":"fontSizes = [[1,33], [5,30], [10,27], [100,20], [200,18], [1000,16], [10000,13]]\n .map(([h,size]) => [h, size*width/1363*0.7])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":30,"value":"// def A051037():\n// yield 1\n// seq = [1]\n// spiders = [(2,2,0,0),(3,3,0,1),(5,5,0,2)]\n// while True:\n// x,p,i,j = min(spiders)\n// if x != seq[-1]:\n// yield x\n// seq.append(x)\n// spiders[j] = (p*seq[i+1],p,i+1,j)\n\n// yields 1 and all numbers whose only prime factors are in the array `primes`,\n// i.e. if `primes` = [p1,p2,...,pj] then it yields all numbers of the form\n// p1^q1*p2^q2*...*pj^qj for qi >= 0\nfunction* smoothGenerator(primes) {\n yield 1;\n const seq = [1];\n let spiders = primes.map((p,i) => [p,p,0,i]);\n while (true) {\n const [x,p,i,j] = spiders.reduce((acc, val) => (arrayComp(acc,val) <= 0) ? acc : val, spiders[0]);\n if (x !== seq[seq.length-1]) {\n yield x;\n seq.push(x);\n }\n spiders[j] = [p*seq[i+1], p, i+1, j];\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":72,"value":"// def nfactors(h,p):\n// nf = 0\n// while h % p == 0:\n// nf += 1\n// h //= p\n// return nf\nfunction nFactors(h,p) {\n let nf = 0;\n while (h % p === 0) {\n nf ++;\n h /= p;\n }\n return nf;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":89,"value":"seq = {\n const seq = [];\n const map = new Map();\n for (let h of smoothGenerator(primes)) {\n if (h > config.limit)\n break;\n const fact = ({});\n const children = [];\n primes.forEach(p => {\n const f = nFactors(h,p);\n fact[p] = f;\n if (f > 0)\n children.push(map.get(h / p));\n });\n const dat = ({val:h, fact:fact, pos:place(h,fact), children:children});\n map.set(h, dat);\n seq.push(dat);\n }\n return seq;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":104,"value":"params = {\n const leftWidth = Math.max(...seq.map(({pos}) => pos[0]));\n const rightWidth = Math.abs(Math.min(...seq.map(({pos}) => pos[0])));\n return ({leftWidth:leftWidth, rightWidth:rightWidth,\n width: config.xScale*(leftWidth+rightWidth) + 2*config.r + 2*config.margin,\n height: Math.floor(0.5 + Math.log(config.limit)*config.yScale + 2*(config.r + config.margin))});\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":108,"value":"horiz = {\n const horiz = [];\n let l = 1,\n base = 1;\n while (l <= config.limit) {\n const y = -config.yScale*Math.log(l) + params.height - config.r - config.margin;\n horiz.push(y);\n l += base;\n if (l === 10*base) \n base = l;\n }\n return horiz;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":78,"value":"// def place(h,i,j,k):\n// # logical coordinates\n// x = j * log(3) - k * log(5) + i * skew\n// y = log(h)\n \n// # physical coordinates\n// x = (x*xscale) + leftwidth\n// y = (-y*yscale) + height - radius - margin\n \n// return (x,y)\n\nfunction place(h, dat) {\n // const x = 0.3*i * Math.log(2) + j * Math.log(3) - k * Math.log(5),\n const x = primes.reduceRight(([sum,sign,i],p) => [sum + dat[p]*sign*Math.log(p) / Math.floor((i+2)/2), -sign, i+1], [0,-1,0])[0],\n y = Math.log(h);\n return [x,y];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":160,"value":"function place2([x,y]) {\n x = (x*config.xScale) + params.rightWidth*config.xScale + 2*config.margin;\n y = (-y*config.yScale) + params.height - config.r - config.margin;\n return [x,y];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":33,"value":"function arrayComp(a,b) { \n for (let i=0; i