NAME¶

Math::PlanePath::CfracDigits -- 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

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] + -----------------
                                  1
                     q[2] + ------------
                         ....
                                      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]-1,  q[2]-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]-1), 3, base2(q[2]-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]-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[1] and q[1]-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^2 + d[1]*2 + d[0]
    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[2]*3^2 + d[1]*3 + d[0]
    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.

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

    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

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

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

    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

    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 ()"

"$path = Math::PlanePath::CfracDigits->new (radix => $radix)"

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

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

SEE ALSO¶

Math::PlanePath, Math::PlanePath::FractionsTree, Math::PlanePath::CoprimeColumns

Math::PlanePath::RationalsTree, Math::PlanePath::GcdRationals, Math::PlanePath::DiagonalRationals

Math::ContinuedFraction

HOME PAGE¶

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

LICENSE¶

Copyright 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 Kevin Ryde

This file is part of Math-PlanePath.

Math-PlanePath is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

Math-PlanePath is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.