3e:null 3f:["$","title",null,{"children":"Py Triples Again | Maxim Taldykin | Observable"}] 45:[{"id":"9ed508bf197225d0e618d8758001a03ae38382b17d7bc5455f8950dd4acc5add8ac74ae5928f6c8e6fba6adb294d348a9f1c445b64a32dc404cd4f76e3e9565c","href":"https://static.observableusercontent.com/files/9ed508bf197225d0e618d8758001a03ae38382b17d7bc5455f8950dd4acc5add8ac74ae5928f6c8e6fba6adb294d348a9f1c445b64a32dc404cd4f76e3e9565c","name":"triples.json","type":"application/json","lastModified":1702238159868.246,"size":336886}] 43:{"id":"9aa09aaa8b1609fb","slug":null,"title":"Py Triples Again","thumbnail":"803f60a3cc78a301dc4cd6074ea31c96ff35ec227aeff82977e0a1d6c83d8f94","access_level":"public","create_time":"$D2023-12-10T19:55:59.868Z","update_time":"$D2023-12-10T20:45:50.347Z","view_time":null,"first_public_time":"$D2023-12-10T19:55:59.868Z","has_unpublished_edits":null,"fork":{"id":"ba2a298972638e3e","slug":null,"title":"Py Triples Again","owner":{"id":"bdbed6e4505e8e57","login":"jorpic","name":"Maxim Taldykin"}},"stars":0,"starred":false,"owner":{"type":"team","id":"bdbed6e4505e8e57","login":"jorpic","name":"Maxim Taldykin","avatar_url":"https://avatars-next.observableusercontent.com/93d22477a947653107265a9d66c0181885f639e1105a3ec050197357579ed48b","tier":"starter_2024","bio":"","following":false},"version":1025,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"cb02791459828809","login":"jorpic","name":"Maxim Taldykin","avatar_url":"https://avatars-next.observableusercontent.com/93d22477a947653107265a9d66c0181885f639e1105a3ec050197357579ed48b","tier":null,"bio":"","following":false}],"members":[{"type":"individual","id":"cb02791459828809","login":"jorpic","name":"Maxim Taldykin","avatar_url":"https://avatars-next.observableusercontent.com/93d22477a947653107265a9d66c0181885f639e1105a3ec050197357579ed48b","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Py Triples Again","cells":[{"id":0,"value":"# Py Triples Again","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":20,"value":"Generate list of all triples.\n - Triple contains of three numbers.\n - Numbers in a triple are in ascending order.\n - Triples in the list are lexicographically ordered.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":5,"value":"function genTriples(n) {\n const ts = [];\n for(let a = 1; a < n; a++) {\n for(let b = a+1; b < n; b++) {\n const ab = a*a + b*b;\n const c = Math.floor(Math.sqrt(a*a + b*b));\n if(c <= n && ab == c*c) {\n ts.push([a,b,c]);\n }\n }\n }\n return ts;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":35,"value":"N = 7825","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":32,"value":"ALL_TRIPLES = genTriples(N);","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":22,"value":"There are **${ALL_TRIPLES.length}** triples. Each consists of numbers in the range [1..${N}].\n\nIt's obvious that some numbers are part of several triples. We say that this number _links_ those triples. So now we have a graph of linked triples.\n\nWe can group triples by links. `groupByLinks` returns a dictionary with links as keys and list of triples containing that link as value.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":9,"value":"function groupByLinks(ts) {\n const ls = {};\n ts.forEach(xs =>\n xs.map(x => {\n if (x in ls) { ls[x].push(xs); } else { ls[x] = [xs]; }\n })\n );\n return ls;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":42,"value":"ALL_LINKS = groupByLinks(ALL_TRIPLES)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":30,"value":"**${Object.keys(ALL_LINKS).length}** different numbers occur in triples. And **${Object.values(ALL_LINKS).filter(x => x.length < 2).length}** of them do not link anything — each of them is contained in a single triple.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":57,"value":"Let's call the number of triples connected by a given link a _link's weight_.\n\nWe are to filter out triples that contain links of weight == 1. We need to do this recursively because dropping a triple from a set of all triples may reduce weights of some links of some of the remaining triples.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":7,"value":"function filterByLinkWeight(ts, {minWeight}) {\n ts = new Set(ts);\n while(true) {\n let deleted = 0;\n Object.values(groupByLinks(ts)).forEach(xs => {\n if (xs.length < minWeight) {\n xs.forEach(x => ts.delete(x));\n deleted += 1;\n }\n });\n if (deleted == 0) return [...ts];\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":63,"value":"FILTERED_TRIPLES = filterByLinkWeight(ALL_TRIPLES, {minWeight: 2})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":92,"value":"FILTERED_LINKS = groupByLinks(FILTERED_TRIPLES)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":65,"value":"Now we are left with only **${FILTERED_TRIPLES.length}**/${ALL_TRIPLES.length} triples and **${Object.keys(FILTERED_LINKS).length}**/${Object.keys(ALL_LINKS).length} links.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":12,"value":"As now our triples form a graph, let`s extract tightly connected subgraphs from it.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":101,"value":"function neighbourhood(lnk, links, {radius}) {\n let nodes = {}; // this is a replacement for Set<[number]>()\n lnk.forEach(l => links[l].forEach(n => {nodes[n] = n;}));\n while(--radius > 0) {\n Object.values(nodes).forEach(n =>\n n.forEach(l => \n links[l].forEach(x => {nodes[x] = x;})\n ));\n }\n return Object.values(nodes);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":116,"value":"For each link we can take triples that it connects. Then take all the links in those triples, and get another layer of neighbors. This can be repeated several times.\n\nBut we are interested only in tightly linked neighbors. We take only those that have multiple links in the resulting neighborhood. \n\nIt is obvious that we can get identical groups starting from different links. We need to _normalize_ groups (i.e. order triples in them) to check for equality.\n\nWe also don't need groups that are too big in terms of number of links. So we limit maximum number of links to **27**.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":130,"value":"function compareArrays(xs, ys) {\n for(let i = 0; i < Math.min(xs.length, ys.length); i++) {\n if (xs[i] != ys[i]) return xs[i] - ys[i];\n }\n return 0;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":155,"value":"function linkSet(nodes) {\n const ls = new Set();\n nodes.forEach(n => n.forEach(l => ls.add(l)));\n return ls;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":161,"value":"function dropDuplicates(groups) {\n return Object.values(\n groups\n .map(group => group.sort(compareArrays))\n .reduce((set, grp) => {set[JSON.stringify(grp)] = grp; return set;}, {})\n );\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":104,"value":"function getTightGroups({radius, minWeight, maxWidth}) {\n let groups = Object.keys(FILTERED_LINKS)\n .map(lnk => neighbourhood([Number(lnk)], FILTERED_LINKS, {radius}))\n .map(group => filterByLinkWeight(group, {minWeight}))\n .filter(group => group.length > 0 && linkSet(group).size <= maxWidth);\n\n return dropDuplicates(groups);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":175,"value":"Some groups may contain all triples that share some link. In that case we say that _global weight_ of this link equal it's _local weight_ in this group.\n\nThis is an important information, so better we keep it close to a group.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":173,"value":"/**/\ntripleGroups = {\n let g_2_2 = getTightGroups({radius: 2, minWeight: 2, maxWidth: 39});\n let g_3_3 = getTightGroups({radius: 3, minWeight: 3, maxWidth: 39});\n return dropDuplicates(g_2_2.concat(g_3_3))\n .map(grp => ({grp}))\n}\n/**/","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":209,"value":"//tripleGroups = FileAttachment(\"triples.json\").json()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":191,"value":"Now we have **${tripleGroups.length}** groups that cover **${dropDuplicates(tripleGroups.flatMap(g => g.grp)).length}** triples (out of **${FILTERED_TRIPLES.length}**) and **${linkSet(tripleGroups.flatMap(g => g.grp)).size}** links (out of **${Object.keys(FILTERED_LINKS).length}**).","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":888,"value":"g27 = {\n let xxx = null;\n let linkSet = grp => new Set(grp.flat());\n let res = tripleGroups\n .filter(x => linkSet(x.grp).size <= x.grp.length)\n .map(x => ({...groupToNormalForm(x.grp), triples: x.grp}))\n .reduce((r,g) => {\n let k = JSON.stringify(g.schema);\n g.k = commonFactor(g.links);\n g.k = g.k ? g.links[0] / g.k[0] : 1;\n g.m = g.links[g.links.length-1];\n if (g.m == N) xxx = g;\n k in r ? r[k].push(g) : r[k] = [g];\n return r\n }, {});\n return Object.values(res)\n .map(xs => xs.sort((a,b) => a.links[0] - b.links[0]))\n .sort((a,b) => b.length - a.length);\n}\n \n\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":959,"value":"overdetermined = {\n let linkSet = grp => new Set(grp.flat());\n let res = tripleGroups\n .map(x => ({...x, links: linkSet(x.grp)}))\n .filter(x => x.links.size <= x.grp.length);\n return res;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":935,"value":"{\n const allGrp = g27.flat();\n const allLinks = allGrp.map(g => g.links).flat();\n const allTriples = allGrp.map(g => g.triples.map(JSON.stringify)).flat();\n return {uniqueLinks: new Set(allLinks).size,\n uniqueTriples: new Set(allTriples).size}\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":221,"value":"Some of these groups have identical structure. We want to highlight this by separating interconnections inside group from link labels.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":219,"value":"function groupToNormalForm(grp) {\n let links = [...new Set(grp.flatMap(t => t))].map(l => Number(l)).sort((a,b) => a - b);\n // `revLinks` is a monotinic mapping.\n let revLinks = links.reduce((map, l, ix) => { map[l] = ix; return map; }, {});\n let schema = grp.map(t => t.map(l => revLinks[l]));\n return {links, schema};\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":238,"value":"schema = {\n let tripleIx = FILTERED_TRIPLES.reduce((r, t, i) => { r[JSON.stringify(t)] = i; return r;}, {});\n let schemaGroups = {};\n let schemaIx = {};\n let sIx = 0;\n for (let g of tripleGroups) {\n let {links, schema} = groupToNormalForm(g.grp);\n let key = JSON.stringify(schema);\n if (!(key in schemaGroups)) {\n schemaGroups[key] = [];\n schemaIx[key] = sIx;\n sIx++;\n }\n schemaGroups[key].push({\n links,\n triples: g.grp, // .map(x => tripleIx[JSON.stringify(x)]),\n schema: schemaIx[key]\n });\n }\n return {\n groups: Object.values(schemaGroups)\n .sort((a,b) => b.length - a.length)\n .map(xs => xs.sort((a,b) => a.links[0] - b.links[0])),\n schemaIx,\n // tripleIx\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":989,"value":"Number of weight-2 links covered by tight groups:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":982,"value":"[...new Set(schema.groups.filter(g => g.length > 10).flat().map(g =>g.links).flat())].filter(l => FILTERED_LINKS[l].length == 2)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":992,"value":"{ let xxx = new Set(schema.groups.filter(g => g.length > 10).flat().map(g =>g.links).flat());\n let yyy = Object.entries(FILTERED_LINKS).filter(([l,v]) => !xxx.has(Number(l)) && v.length == 2);\n return yyy.map(([l,xs]) => neighbourhood(xs.flat(), FILTERED_LINKS, {radius: 0}))\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":785,"value":"schemaCoverage = {\n const count = xs => new Set(xs.flat()).size;\n const s0 = schema.groups[0];\n const ss = schema.groups.filter(gs => gs.length >= 10).flat();\n return {\n s0: {\n links: count(s0.map(g => g.links)),\n triples: count(s0.map(g => g.triples)),\n },\n ss: {\n links: count(ss.map(g => g.links)),\n triples: count(ss.map(g => g.triples)),\n },\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":337,"value":"Groups of schema 0 cover **${schemaCoverage.s0.links}**/3745 links and **${schemaCoverage.s0.triples}**/7336 triples","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":684,"value":"function commonFactor(xs) {\n for(let i = 550; i > 1; i--) {\n const res = xs.map(x => x/i);\n if (res.every(Number.isInteger)) return res;\n }\n return null;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":859,"value":"{\n const z = 1;\n const f = (k, xs) => ({\n ...xs,\n triples: xs.triples.map(t => t.map(x => x*k*z)),\n links: xs.links.map(x => x*k*z),\n });\n const xs = [\n f(24,primeGroups[0][0][1][0]),\n f(6, primeGroups[0][10][1][0]),\n f(2, primeGroups[0][22][1][0]),\n f(1, primeGroups[0][50][1][0]),\n f(2, primeGroups[1][1][1][0])\n ];\n const links = xs.map(x => x.links);\n const triples = xs.map(x => JSON.stringify(x.triples));\n // return [...new Set(links.flat().filter(l => l in FILTERED_LINKS))];\n return triples;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":677,"value":"primeGroups = {\n const groupByPrimes = xs => {\n const pg = xs.reduce((res,x) => {\n const f = commonFactor(x.links) || x.links;\n const k = JSON.stringify(f);\n if(k in res) { res[k].push(x); } else { res[k] = [x]; }\n return res;\n }, {});\n return Object.entries(pg).sort((a,b) => b[1].length - a[1].length);\n }\n return schema.groups.filter(g => g.length > 10).map(groupByPrimes);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":751,"value":"extendedPrimeGroups = {\n const extendGroup = (k, g) => {\n let f = g.links[0] / JSON.parse(k)[0];\n let res = neighbourhood(g.links, FILTERED_LINKS, {radius:4});\n return groupToNormalForm(res);\n }\n return primeGroups.filter(g => g[1].length > 5).map(([k, v]) => [k, v.map(g => extendGroup(k, g))])\n} ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":700,"value":"function applySchema(links, schema) {\n return schema.map(t => t.map(i => links[i]));\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":739,"value":"function checkTriple([a,b,c]) {\n return a*a + b*b == c*c;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":732,"value":"applySchema(\n [15,20,25,36,39,48,52,60,65].map(x => x*4),\n [[0,1,2],[0,3,4],[1,5,6],[2,7,8],[3,5,7],[4,6,8]]\n).map(checkTriple)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":957,"value":"","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"}],"files":"$W45","stdlib":"1"}} 44:"$43:body"