I suppose that everyone has heard of Raymond Smullyan. student of Kurt Godel, logician and mathematician 1919 -

I also suppose that everyone is familiar with his unique way of counting sets, which he tells in terms of a story about a brilliant, charming girl stuck in hell with the devil. She of course wishes to leave while he...
Let us stop right here, I was watching a rerun of Oprah that says it is unfair that God is always depicted as a man. We should start referring to him as her, says Oprah. Fair enough! So I will continue with Raymond's story and keep fairness in mind..

A charming, brilliant young girl is stuck in hell with the devil. She of course wishes to leave and pursue modelling and greenpeace. She (the devil)  because she has a quota to keep wishes to keep the young girl forever. The girls whining bothers the devil so the devil poses a problem. I am thinking of a counting number 1,2,3,4... you young girl get to guess what number I am thinking of. You get one pick per day. When you guess my number your out. The young girl is elated, she knows the ignorant devil has erred. She calls the devils pick n and knows that just by starting at 1 she will be out in n days.n could be large but it is not infinity.
The devil cannot hold her forever.

Raymond goes on to talk about the girls strategy in case the devil picks the integers.  ..., -3, -2 ,-1, 0, 1, 2 ,3 ... The devil reasons that if the girl starts at 0 and goes forward and the devil has picked a negative number then the young girl will be there for eternity. Of course the young girl reasons out an effective strategy and is elated. She knows the devil has erred and in some finite amount of time she will be out. Here is how: she starts at 0 and then picks 1 and then -1. 2 , -2. 3, -3 ...

Now we come to the point. What if the devil says I an thinking of a fraction young lady... The young girl thinks about it and smiles. She enumerates all the fractions in a table like this.

1/1, 2/1, 3/1, 4/1, 5/1, 6/1, 7/1...
1/2, 2/2, 3/2, 4/2, 5/2, 6/2, 7/2...
1/3, 2/3, 3/3, 4/3, 5/3, 6/3, 7/3...
1/4, 2/4, 3/4, 4/4, 5/4, 6/4, 7/4...
1/5, 2/5, 3/5, 4/5, 5/5, 6/5, 7/5 ...

She knows that if she goes down any column or across any row she will never come to the end.
Unless she guesses exactly what row the dirty devil's choice is in she is stuck there forever.
She smiles, she figures out how to go through the table and how to get out in a finite amount of days.
You should figure it too, in case this happens to you.

We are here to speedup the girls escape and hopefully manage her modelling career.
We look at the table, we agree it gets all the fractions and that she will eventually be out using her method.
We notice on some days she will guess a number that she has previously picked. 1/1 and 2/2 ... are the same so is 6/4 and 3/2.
Is there a way to generate all the fractions without all those duplicates?

It turns out there is, the marvelous Wilf - Calkin algorithm.



You start at 1 / 1 at the root node. This is a binary tree so each node has 2 branches. You populate the nodes like this, for each fraction  i / j (node) to the below and left of it you put i / ( i + j ) and to the below and  right ( i + j ) / j.
Now all the fractions are generated and there are no duplicates. We have streamlined her escape!