## Every Possible Fraction

### December 9, 2014

Using the generators of a previous exercise, this is simple:

```(define-generator (rats)   (let loop ((x 1))     (yield x)     (let* ((n (floor x)) (y (- x n)))       (loop (/ (- n -1 y))))))```

Then it’s just a matter of taking terms from the sequence:

```> (define next (rats)) > (do ((i 1 (+ i 1))) ((< 120 i))     (display (next))     (if (zero? (modulo i 10))         (newline)         (display #\tab)))) 1       1/2     2       1/3     3/2     2/3     3       1/4     4/3     3/5 5/2     2/5     5/3     3/4     4       1/5     5/4     4/7     7/3     3/8 8/5     5/7     7/2     2/7     7/5     5/8     8/3     3/7     7/4     4/5 5       1/6     6/5     5/9     9/4     4/11    11/7    7/10    10/3    3/11 11/8    8/13    13/5    5/12    12/7    7/9     9/2     2/9     9/7     7/12 12/5    5/13    13/8    8/11    11/3    3/10    10/7    7/11    11/4    4/9 9/5     5/6     6       1/7     7/6     6/11    11/5    5/14    14/9    9/13 13/4    4/15    15/11   11/18   18/7    7/17    17/10   10/13   13/3    3/14 14/11   11/19   19/8    8/21    21/13   13/18   18/5    5/17    17/12   12/19 19/7    7/16    16/9    9/11    11/2    2/11    11/9    9/16    16/7    7/19 19/12   12/17   17/5    5/18    18/13   13/21   21/8    8/19    19/11   11/14 14/3    3/13    13/10   10/17   17/7    7/18    18/11   11/15   15/4    4/13```

You can run the program at http://programmingpraxis.codepad.org/Pzw6Hdu0. You might also be interested in Jeremy Gibbons’ derivation of the program (he called it `rats7`).

Pages: 1 2

### 13 Responses to “Every Possible Fraction”

1. Francesco said

```f (a:b:c) = a : (fst a + fst b, snd a + snd b) : f (b:c)
f r       = r

main = print \$ until ((> 9) . length) f [(0,1), (1,0)]
```
2. Paul said

In Python.

```from fractions import Fraction
from itertools import islice

def rats():
x = Fraction(1)
while 1:
yield x
n = int(x)
y = x - n
x = 1 / (n - y + 1)

r = rats()
for lines in xrange(10):
for f in islice(r, 10):
print "{:8s}".format(f),
print
```
3. Brett Warren said

Python 3.4, generator implementation

```def stern_brocot_gen():
from math import floor
from fractions import Fraction
x = 1
while True:
n = floor(x)
y = x - n
x = Fraction(1/(n - y + 1))
yield x

if __name__ == "__main__":
gen = stern_brocot_gen()
for n in range(10):
print(gen.__next__())
```
4. programmingpraxis said

I used a generator because I have an implementation of generators in the Standard Prelude and because it’s good to remind my readers that generators can be useful, but generators aren’t actually needed for this exercise, because only a single value is carried forward from one iteration to the next and because each iterative step is simple to compute. Here is an alternative solution:

```(define rat   (let ((x 0))     (lambda args       (when (pair? args)         (set! x (car args)))       (let* ((n (floor x))              (y (- x n)))         (set! x (/ (- n y -1))) x))))```

Calling `(rat)` repeatedly returns the same sequence of fractions as the original. Additionally, calling `(rat r)`, where r is some rational number, resets the sequence to start from r, so for instance `(rat 11/32)` returns 32/21, and `(rat 0)` restarts the sequence from the beginning.

5. Graham said

For more Haskell fun, check out this functional pearl.

[ EDIT: I linked that paper in the last paragraph of the solution page. As Graham says, it is well worth reading. Phil ]

6. Graham said

7. matthew said

Aha! Thanks for the link, I had just got the point of realizing that the sequence given didn’t actually generate the Stern-Brocot tree and that explains it.

Here’s a Python generator for the sequence that does the rational arithmetic itself – and we don’t need to do an explicit reduction to lowest terms.

```def rats():
p,q = 1,1
while True:
yield p,q
p,q = q, p-2*(p%q)+q
```
8. Lucas A. Brown said

I’m rather partial to the Calkin-Wilf tree. It contains also contains every positive rational number in lowest terms exactly once; it just has them in a different order.

```def calkinwilf(x):
if x == 0: return (0,1)
n, y, l = ilog(x, 2), 0, []
while x > 0:
x, y = divmod(x, 2)
l.append(y)
i, j = 1, 1
for t in xrange(n, 0, -1):
if l[t-1] == 0: j += i
if l[t-1] == 1: i += j
return (i,j)

def wilfcalkin(i, j):
# Inverse function of calkinwilf()
if i == 0: return 0
x, t = 0, -1
while i * j != 1:
t += 1
if i > j:
i -= j
x += 2**t
else: j -= i
return x + 2**(t+1)

from itertools import count
for n in count(): print n, calkinwilf(n)
```
9. matthew said

@Lucas – the rational enumeration we are after _is_ the Calkin-Wilf tree order.

This paper looks interesting & suggests we can do a similar direct enumeration of the elements in the Stern-Brocot tree as well:

Click to access RecountingRationalsTwice.pdf

10. matthew said

Here’s the algorithm from the Backhouse and Ferreira paper – it’s quite nifty: take Euclid’s GCD algorithm, for coprime p and q, this does (p,q) => (p-q,q) or (p,q) => (p,q-p) until p = q = 1; reverse the process ie. (p,q) maps to (p+q, q) or (p,p+q), these two operations generate all co-prime pairs (p,q); but this is just using the two matrices L = [1 1 0 1] and R = [1 0 1 1] to generate all invertible 2×2 integral matrices, so we can form a tree of all strings of { L, R } and map to the rationals by applying each matrix or its transpose to (1,1): whether we use the matrix or its transpose determines if we get the Stern-Brocot tree or the Calkin-Wilf tree. They also give a method for iteratively generating these matrices, which can then be used to generate the tree elements in order – for the Calkin-Wilf tree, this simplifies to the method described above:

```def mats():
a,b,c,d = 1,0,0,1
while True:
yield a,b,c,d
if a == 1 and b == 0 and d == 1:
a,b,c,d = 1,c+1,0,1
else:
j = (c+d-1)//(a+b)
k = 2*j+1
a,b,c,d = k*a-c,k*b-d,a,b

m = mats()
for i in range(15):
a,b,c,d = m.next()
print "[%d %d %d %d] %d/%d %d/%d"%(a,b,c,d,c+d,a+b,a+c,b+d)
```

and the output:

```[1 0 0 1] 1/1 1/1
[1 1 0 1] 1/2 1/2
[1 0 1 1] 2/1 2/1
[1 2 0 1] 1/3 1/3
[1 1 1 2] 3/2 2/3
[2 1 1 1] 2/3 3/2
[1 0 2 1] 3/1 3/1
[1 3 0 1] 1/4 1/4
[1 2 1 3] 4/3 2/5
[2 3 1 2] 3/5 3/5
[1 1 2 3] 5/2 3/4
[3 2 1 1] 2/5 4/3
[2 1 3 2] 5/3 5/3
[3 1 2 1] 3/4 5/2
[1 0 3 1] 4/1 4/1
```

There is an extended version of the paper I mentioned above at:
http://eprints.nottingham.ac.uk/1856/1/scp-rationals.pdf with some interesting historical details amongst other stuff.

Roland Backhouse was one of my lecturers years ago, nice guy.

11. Andras said

Scala

```package programmingpraxis

object Fraction {
class F(val num: Int, val den:Int) {
def n(): F = {
new F((num / den)*den, den)
}

def y(): F= {
new F(num - n().num, den)
}

def next():F = {
new F(den, n().num - y().num +den)
}

def stream(): Stream[F]={
this #:: next().stream
}

override def toString() = num+"/"+den
}

new F(1,1).stream().take(20).toList             //> res0: List[programmingpraxis.Fraction.F] = List(1/1, 1/2, 2/1, 1/3, 3/2, 2/3
//| , 3/1, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4/1, 1/5, 5/4, 4/7, 7/3, 3/8)
}
```
12. Andras said

a bit shorter Scala

```package programmingpraxis

object Fraction {
def stream(in:Tuple2[Int, Int]): Stream[Tuple2[Int, Int]]={
in #:: stream((in._2, (2 * (in._1 / in._2) + 1 ) * in._2 - in._1))
}                                               //> stream: (in: (Int, Int))Stream[(Int, Int)]

stream((1,1)).take(20).toList                   //> res0: List[(Int, Int)] = List((1,1), (1,2), (2,1), (1,3), (3,2), (2,3), (3,1
//| ), (1,4), (4,3), (3,5), (5,2), (2,5), (5,3), (3,4), (4,1), (1,5), (5,4), (4,
//| 7), (7,3), (3,8))
}
```
13. Jamie Hope said

Using unfold from SRFI-1:

```(import (only (srfi :1) unfold))

(define (next-fraction f)
(let* ((n (floor f))
(y (- f n)))
(/ (- n y -1))))

(define (fractions numterms)
(unfold (lambda (x) (> (car x) numterms))
cdr
(lambda (x) (cons (+ 1 (car x))
(next-fraction (cdr x))))
(cons 1 1)))

(define (display-as-grid list numcols)
(let loop ((i 1) (list list))
(if (null? list)
(values)
(begin (display (car list))
(if (zero? (modulo i numcols))
(newline)
(display #\tab))
(loop (+ i 1) (cdr list))))))

(display-as-grid (fractions 120) 10)
```