Here's a nice series of posts about how to list every rational number in its lowest terms, with no repeats (ie. only include 2/5 not 4/10). The key is to make a tree with 1/1 as the root and for each node i/j, put i+j/j as the left child and i/i+j as the right child. It's all laid out very clearly in the series of post which is based on a terse maths paper.
In the comments I found a link to another paper which comes at this using matrices and relates this tree with another previously known tree that also lists the rationals. It's a fairly readable paper too but a bit more technical.
No comments:
Post a Comment