user
The **Calkin-Wilf sequence** contains every nonnegative rational number exactly once.

It can be calculated recursively as follows:

```
       a1   =  1 
       an+1  =  1/(2⌊an⌋+1-an) for n > 1 

```

Task part 1

* Show on this page terms 1 through 20 of the Calkin-Wilf sequence.

To avoid floating point error, you may want to use a rational number data type.

It is also possible, given a non-negative rational number, to determine where it appears in the sequence without calculating the sequence. The procedure is to get the continued fraction representation of the rational and use it as the run-length encoding of the binary representation of the term number, beginning from the end of the continued fraction.
It only works if the number of terms in the continued fraction is odd- use either of the two equivalent representations to achieve this:

```
       [a0; a1, a2, ..., an]  =  [a0; a1, a2 ,..., an-1, 1] 

```

Example

The fraction   **9/4**   has odd continued fraction representation      2; 3, 1,     giving a binary representation of   **100011**,
  
which means   **9/4**   appears as the   **35th**   term of the sequence.

Task part 2

* Find the position of the number   **83116****/****51639**   in the Calkin-Wilf sequence.

Related tasks
:   * Fusc sequence.

See also

* Wikipedia entry: Calkin-Wilf tree
* Continued fraction
* Continued fraction/Arithmetic/Construct from rational number
assistant
In Raku, arrays are indexed from 0. The Calkin-Wilf sequence does not have a term defined at 0.

This implementation includes a bogus undefined value at position 0, having the bogus first term shifts the indices up by one, making the ordinal position and index match. Useful due to how reversibility function works.

```
my @calkin-wilf = Any, 1, {1 / (.Int × 2 + 1 - $_)} … *;

# Rational to Calkin-Wilf index
sub r2cw (Rat $rat) { :2( join '', flat (flat (1,0) xx *) Zxx reverse r2cf $rat ) }

# The task

say "First twenty terms of the Calkin-Wilf sequence: ",
    @calkin-wilf[1..20]».&prat.join: ', ';

say "\n99991st through 100000th: ",
    (my @tests = @calkin-wilf[99_991 .. 100_000])».&prat.join: ', ';

say "\nCheck reversibility: ", @tests».Rat».&r2cw.join: ', ';

say "\n83116/51639 is at index: ", r2cw 83116/51639;


# Helper subs
sub r2cf (Rat $rat is copy) { # Rational to continued fraction
    gather loop {
	    $rat -= take $rat.floor;
	    last if !$rat;
	    $rat = 1 / $rat;
    }
}

sub prat ($num) { # pretty Rat
    return $num unless $num ~~ Rat|FatRat;
    return $num.numerator if $num.denominator == 1;
    $num.nude.join: '/';
}

```

Output:

```
First twenty terms of the Calkin-Wilf sequence: 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

99991st through 100000th: 1085/303, 303/1036, 1036/733, 733/1163, 1163/430, 430/987, 987/557, 557/684, 684/127, 127/713

Check reversibility: 99991, 99992, 99993, 99994, 99995, 99996, 99997, 99998, 99999, 100000

83116/51639 is at index: 123456789
```