 Math::PlanePath::CfracDigits(3) continued fraction terms encoded by digits

## SYNOPSIS

use Math::PlanePath::CfracDigits;
my \$path = Math::PlanePath::CfracDigits->new (tree_type => 'Kepler');
my (\$x, \$y) = \$path->n_to_xy (123);

## DESCRIPTION

This path enumerates reduced fractions 0 < X/Y < 1 with X,Y no common factor using a method by Jeffrey Shallit encoding continued fraction terms in digit strings, as per

Jeffrey Shallit, ``Number Theory and Formal Languages'', part 3, <https://cs.uwaterloo.ca/~shallit/Papers/ntfl.ps>

Fractions up to a given denominator are covered by roughly N=den^2.28. This is a much smaller N range than the run-length encoding in "RationalsTree" and "FractionsTree" (but is more than "GcdRationals").

```    15  |    25  27      91          61 115         307     105 104
14  |    23      48      65             119     111     103
13  |    22  24  46  29  66  59 113 120 101 109  99  98
12  |    17              60     114              97
11  |    16  18  30  64  58 112 118 102  96  95
10  |    14      28             100      94
9  |    13  15      20  38      36  35
8  |     8      21      39      34
7  |     7   9  19  37  33  32
6  |     5              31
5  |     4   6  12  11
4  |     2      10
3  |     1   3
2  |     0
1  |
Y=0 |
----------------------------------------------------------
X=0   1   2   3   4   5   6   7   8   9  10  11  12  13  14
```

A fraction 0 < X/Y < 1 has a finite continued fraction of the form

```                      1
X/Y = 0 + ---------------------
1
q + -----------------
1
q + ------------
....
1
q[k-1] + ----
q[k]
where each  q[i] >= 1
except last q[k] >= 2
```

The terms are collected up as a sequence of integers >=0 by subtracting 1 from each and 2 from the last.

```    # each >= 0
q-1,  q-1, ..., q[k-2]-1, q[k-1]-1, q[k]-2
```

These integers are written in base-2 using digits 1,2. A digit 3 is written between each term as a separator.

```    base2(q-1), 3, base2(q-1), 3, ..., 3, base2(q[k]-2)
```

If a term q[i]-1 is zero then its base-2 form is empty and there's adjacent 3s in that case. If the high q-1 is zero then a bare high 3, and if the last q[k]-2 is zero then a bare final 3. If there's just a single term q and q-2=0 then the string is completely empty. This occurs for X/Y=1/2.

The resulting string of 1s,2s,3s is reckoned as a base-3 value with digits 1,2,3 and the result is N. All possible strings of 1s,2s,3s occur (including the empty string) and so all integers N>=0 correspond one-to-one with an X/Y fraction with no common factor.

Digits 1,2 in base-2 means writing an integer in the form

```    d[k]*2^k + d[k-1]*2^(k-1) + ... + d*2^2 + d*2 + d
where each digit d[i]=1 or 2
```

Similarly digits 1,2,3 in base-3 which is used for N,

```    d[k]*3^k + d[k-1]*3^(k-1) + ... + d*3^2 + d*3 + d
where each digit d[i]=1, 2 or 3
```

This is not the same as the conventional binary and ternary radix representations by digits 0,1 or 0,1,2 (ie. 0 to radix-1). The effect of digits 1 to R is to change any 0 digit to instead R and decrement the value above that position to compensate.

## Axis Values

N=0,1,2,4,5,7,etc in the X=1 column is integers with no digit 0s in ternary. N=0 is considered no digits at all and so no digit 0. These points are fractions 1/Y which are a single term q=Y-1 and hence no ``3'' separators, only a run of digits 1,2. These N values are also those which are the same when written in digits 0,1,2 as when written in digits 1,2,3, since there's no 0s or 3s.

N=0,3,10,11,31,etc along the diagonal Y=X+1 are integers which are ternary ``10www...'' where the w's are digits 1 or 2, so no digit 0s except the initial ``10''. These points Y=X+1 points are X/(X+1) with continued fraction

```                     1
X/(X+1) =  0 + -------
1
1 + ---
X
```

so q0=1 and q1=X, giving N=``3,X-1'' in digits 1,2,3, which is N=``1,0,X-1'' in normal ternary. For example N=34 is ternary ``1021'' which is leading ``10'' and then X-1=7 ternary ``21''.

The optional "radix" parameter can select another base for the continued fraction terms, and corresponding radix+1 for the resulting N. The default is radix=2 as described above. Any integer radix>=1 can be selected. For example,

```    radix => 5
11  |    10   30  114  469   75  255 1549 1374  240  225
10  |     9       109                1369       224
9  |     8   24        74  254       234  223
8  |     7        78       258        41
7  |     5   18   73  253  228   40
6  |     4                  39
5  |     3   12   42   38
4  |     2        37
3  |     1    6
2  |     0
1  |
Y=0 |
----------------------------------------------------
X=0   1    2    3    4    5    6    7    8    9   10
```

The X=1 column is integers with no digit 0 in base radix+1, so in radix=5 means no 0 digit in base-6.

The radix=1 case encodes continued fraction terms using only digit 1, which means runs of q many ``1''s to add up to q, and then digit ``2'' as separator.

```    N =  11111 2 1111 2 ... 2 1111 2 11111     base2 digits 1,2
\---/   \--/         \--/   \---/
q-1  q-1     q[k-1]-1 q[k]-2
```

which becomes in plain binary

```    N = 100000  10000   ...  10000  011111     base2 digits 0,1
\----/  \---/        \---/  \----/
q    q       q[k-1]  q[k]-1
```

Each ``2'' becomes ``0'' in plain binary and carry +1 into the run of 1s above it. That carry propagates through those 1s, turning them into 0s, and stops at the ``0'' above them (which had been a ``2''). The low run of 1s from q[k]-2 has no ``2'' below it and is therefore unchanged.

```    radix => 1
11  |   511  32  18  21  39  55  29  26  48 767
10  |   255      17              25     383
9  |   127  16      19  27      24 191
8  |    63      10      14      95
7  |    31   8   9  13  12  47
6  |    15              23
5  |     7   4   6  11
4  |     3       5
3  |     1   2
2  |     0
1  |
Y=0 |
-------------------------------------------
X=0   1   2   3   4   5   6   7   8   9  10
```

The result is similar to ``HCS Continued Fraction'' in Math::PlanePath::RationalsTree. But the lowest run is ``0111'' here, instead of ``1000'' as it is in the HCS. So N-1 here, and a flip (Y-X)/X to map from X/Y<1 here to instead all rationals for the HCS tree. For example

```    CfracDigits radix=1       RationalsTree tree_type=HCS
X/Y = 5/6                 (Y-X)/X = 1/5
is at                     is at
N = 23 = 0b10111          N = 24 = 0b11000
^^^^                      ^^^^
```

## FUNCTIONS

See ``FUNCTIONS'' in Math::PlanePath for behaviour common to all path classes.
"\$path = Math::PlanePath::CfracDigits->new ()"
Create and return a new path object.
"\$n = \$path->n_start()"
Return 0, the first N in the path.

## OEIS

Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include

<http://oeis.org/A032924> (etc)

```    radix=1
A071766    X coordinate (numerator), except extra initial 1
A032924    N in X=1 column, ternary no digit 0 (but lacking N=0)
A023705    N in X=1 column, base-4 no digit 0 (but lacking N=0)
A023721    N in X=1 column, base-5 no digit 0 (but lacking N=0)
A052382    N in X=1 column, decimal no digit 0 (but lacking N=0)
```

<http://user42.tuxfamily.org/math-planepath/index.html>