Instantly share code, notes, and snippets.

Embed
What would you like to do?
Stern–Brocot generator: generate all positive rational numbers
frac[1] = {{0, 1}, {1, 1}, {1,0}}
frac[n_] := frac[n] = frac[n - 1] ~Riffle~ newFracs[n - 1]
newFracs[n_] := Apply[Plus, #] & /@ Partition[frac[n], 2, 1]
(* Example usage: *)
Map[Apply[Divide, #] &, frac[14]]
(*
A few very surprising things happen here:
1) By the nth generation (i.e. frac[n]), all of the fractions with the denominator N have been generated.
2) It appears that every fraction is always generated in reduced form.
*)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment