Stern–Brocot Tree Experiment
I wanted to graphically see how the spacing of the fractions on the Stern–Brocot tree (or if you like, in a Farey sequence) compares to a straight linear scale. Also known as Minkowski's question-mark function.
plot.node()
See also @mike’s notebook, “Stern–Brocot Tree”. Chart from there reproduced below:
chart
import {chart} from "@mbostock/stern-brocot-tree"
L = ([a, b]) => [a + b, b]
R = ([a, b]) => [a, a + b]
binary_to_fraction = function (int) { const [a, b] = int .toString(2) .slice(1) .split('') .reduce( (s,v) => [R, L][+v](s), [1, 1]); return a / b; }
n = 15
I think there’s something a bit wrong with my code here, and the original fractions might not be coming out in the proper order. Luckily we can just sort them to fix it as a hack (and we wanted to sort them anyway, before plotting).
data = [...Array(1<<(n+1)).keys()] .map(binary_to_fraction) .slice(1) .sort((a,b) => a-b) .slice(0, (1<<n)-1)
plot = { const height = width; const svg = d3.select(DOM.svg(width, height)) const margin = 10; const y = d3.scaleLinear().domain([0, 1]).range([height-margin, margin]) const x = d3.scaleLinear().domain([0, 1]).range([margin, width-margin]) const reference = svg.append('path') .attr("stroke", "#aaa").attr("stroke-width", 0.4) .attr('d', `M${x(0)},${y(0)}L${x(1)},${y(1)}`); const point = svg.append("g").selectAll("circle") .data(data) .enter().append("circle") .attr("r", .3).attr("fill", 'black') .attr("cy", (d, i) => y(i / (1<<n) + 1/(1<<(n+1)))) .attr("cx", (d, i) => x(d)); const endpoints = svg.append("g").selectAll("circle") .data([[0,0],[1,1]]) .enter().append("circle") .attr("r", .3).attr("fill", 'black') .attr("cx", d=>x(d[0])) .attr("cy", d=>y(d[1])); return svg; }
d3 = require("https://d3js.org/d3.v5.min.js")