.\" Automatically generated by Pod::Man 2.28 (Pod::Simple 3.28) .\" .\" Standard preamble: .\" ======================================================================== .de Sp \" Vertical space (when we can't use .PP) .if t .sp .5v .if n .sp .. .de Vb \" Begin verbatim text .ft CW .nf .ne \\$1 .. .de Ve \" End verbatim text .ft R .fi .. .\" Set up some character translations and predefined strings. \*(-- will .\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left .\" double quote, and \*(R" will give a right double quote. \*(C+ will .\" give a nicer C++. Capital omega is used to do unbreakable dashes and .\" therefore won't be available. \*(C` and \*(C' expand to `' in nroff, .\" nothing in troff, for use with C<>. .tr \(*W- .ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p' .ie n \{\ . ds -- \(*W- . ds PI pi . if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch . if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\" diablo 12 pitch . ds L" "" . ds R" "" . ds C` "" . ds C' "" 'br\} .el\{\ . ds -- \|\(em\| . ds PI \(*p . ds L" `` . ds R" '' . ds C` . ds C' 'br\} .\" .\" Escape single quotes in literal strings from groff's Unicode transform. .ie \n(.g .ds Aq \(aq .el .ds Aq ' .\" .\" If the F register is turned on, we'll generate index entries on stderr for .\" titles (.TH), headers (.SH), subsections (.SS), items (.Ip), and index .\" entries marked with X<> in POD. Of course, you'll have to process the .\" output yourself in some meaningful fashion. .\" .\" Avoid warning from groff about undefined register 'F'. .de IX .. .nr rF 0 .if \n(.g .if rF .nr rF 1 .if (\n(rF:(\n(.g==0)) \{ . if \nF \{ . de IX . tm Index:\\$1\t\\n%\t"\\$2" .. . if !\nF==2 \{ . nr % 0 . nr F 2 . \} . \} .\} .rr rF .\" .\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2). .\" Fear. Run. Save yourself. No user-serviceable parts. . \" fudge factors for nroff and troff .if n \{\ . ds #H 0 . ds #V .8m . ds #F .3m . ds #[ \f1 . ds #] \fP .\} .if t \{\ . ds #H ((1u-(\\\\n(.fu%2u))*.13m) . ds #V .6m . ds #F 0 . ds #[ \& . ds #] \& .\} . \" simple accents for nroff and troff .if n \{\ . ds ' \& . ds ` \& . ds ^ \& . ds , \& . ds ~ ~ . ds / .\} .if t \{\ . ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u" . ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u' . ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u' . ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u' . ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u' . ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u' .\} . \" troff and (daisy-wheel) nroff accents .ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V' .ds 8 \h'\*(#H'\(*b\h'-\*(#H' .ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#] .ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H' .ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u' .ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#] .ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#] .ds ae a\h'-(\w'a'u*4/10)'e .ds Ae A\h'-(\w'A'u*4/10)'E . \" corrections for vroff .if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u' .if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u' . \" for low resolution devices (crt and lpr) .if \n(.H>23 .if \n(.V>19 \ \{\ . ds : e . ds 8 ss . ds o a . ds d- d\h'-1'\(ga . ds D- D\h'-1'\(hy . ds th \o'bp' . ds Th \o'LP' . ds ae ae . ds Ae AE .\} .rm #[ #] #H #V #F C .\" ======================================================================== .\" .IX Title "Math::PlanePath::CfracDigits 3pm" .TH Math::PlanePath::CfracDigits 3pm "2014-06-14" "perl v5.20.1" "User Contributed Perl Documentation" .\" For nroff, turn off justification. Always turn off hyphenation; it makes .\" way too many mistakes in technical documents. .if n .ad l .nh .SH "NAME" Math::PlanePath::CfracDigits \-\- continued fraction terms encoded by digits .SH "SYNOPSIS" .IX Header "SYNOPSIS" .Vb 3 \& use Math::PlanePath::CfracDigits; \& my $path = Math::PlanePath::CfracDigits\->new (tree_type => \*(AqKepler\*(Aq); \& my ($x, $y) = $path\->n_to_xy (123); .Ve .SH "DESCRIPTION" .IX Header "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 .IX Xref "Shallit, Jeffrey" .Sp .RS 4 Jeffrey Shallit, \*(L"Number Theory and Formal Languages\*(R", part 3, .RE .PP 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 \f(CW\*(C`RationalsTree\*(C'\fR and \f(CW\*(C`FractionsTree\*(C'\fR (but is more than \f(CW\*(C`GcdRationals\*(C'\fR). .PP .Vb 10 \& 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 .Ve .PP A fraction 0\ <\ X/Y\ <\ 1 has a finite continued fraction of the form .PP .Vb 10 \& 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 .Ve .PP The terms are collected up as a sequence of integers >=0 by subtracting 1 from each and 2 from the last. .PP .Vb 2 \& # each >= 0 \& q[1]\-1, q[2]\-1, ..., q[k\-2]\-1, q[k\-1]\-1, q[k]\-2 .Ve .PP These integers are written in base\-2 using digits 1,2. A digit 3 is written between each term as a separator. .PP .Vb 1 \& base2(q[1]\-1), 3, base2(q[2]\-1), 3, ..., 3, base2(q[k]\-2) .Ve .PP 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. .PP 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. .PP Digits 1,2 in base\-2 means writing an integer in the form .PP .Vb 2 \& 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 .Ve .PP Similarly digits 1,2,3 in base\-3 which is used for N, .PP .Vb 2 \& 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 .Ve .PP 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. .SS "Axis Values" .IX Subsection "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[1]=Y\-1 and hence no \*(L"3\*(R" 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. .PP N=0,3,10,11,31,etc along the diagonal Y=X+1 are integers which are ternary \&\*(L"10www...\*(R" where the w's are digits 1 or 2, so no digit 0s except the initial \*(L"10\*(R". These points Y=X+1 points are X/(X+1) with continued fraction .PP .Vb 5 \& 1 \& X/(X+1) = 0 + \-\-\-\-\-\-\- \& 1 \& 1 + \-\-\- \& X .Ve .PP so q0=1 and q1=X, giving N=\*(L"3,X\-1\*(R" in digits 1,2,3, which is N=\*(L"1,0,X\-1\*(R" in normal ternary. For example N=34 is ternary \*(L"1021\*(R" which is leading \*(L"10\*(R" and then X\-1=7 ternary \*(L"21\*(R". .SS "Radix" .IX Subsection "Radix" The optional \f(CW\*(C`radix\*(C'\fR 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, .PP .Vb 1 \& 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 .Ve .PP 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. .SS "Radix 1" .IX Subsection "Radix 1" The radix=1 case encodes continued fraction terms using only digit 1, which means runs of q many \*(L"1\*(R"s to add up to q, and then digit \*(L"2\*(R" as separator. .PP .Vb 3 \& N = 11111 2 1111 2 ... 2 1111 2 11111 base2 digits 1,2 \& \e\-\-\-/ \e\-\-/ \e\-\-/ \e\-\-\-/ \& q[1]\-1 q[2]\-1 q[k\-1]\-1 q[k]\-2 .Ve .PP which becomes in plain binary .PP .Vb 3 \& N = 100000 10000 ... 10000 011111 base2 digits 0,1 \& \e\-\-\-\-/ \e\-\-\-/ \e\-\-\-/ \e\-\-\-\-/ \& q[1] q[2] q[k\-1] q[k]\-1 .Ve .PP Each \*(L"2\*(R" becomes \*(L"0\*(R" 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 \*(L"0\*(R" above them (which had been a \*(L"2\*(R"). The low run of 1s from q[k]\-2 has no \*(L"2\*(R" below it and is therefore unchanged. .PP .Vb 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 .Ve .PP The result is similar to \*(L"\s-1HCS\s0 Continued Fraction\*(R" in Math::PlanePath::RationalsTree. But the lowest run is \*(L"0111\*(R" here, instead of \*(L"1000\*(R" as it is in the \s-1HCS. \s0 So N\-1 here, and a flip (Y\-X)/X to map from X/Y<1 here to instead all rationals for the \s-1HCS\s0 tree. For example .PP .Vb 1 \& 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 \& ^^^^ ^^^^ .Ve .SH "FUNCTIONS" .IX Header "FUNCTIONS" See \*(L"\s-1FUNCTIONS\*(R"\s0 in Math::PlanePath for behaviour common to all path classes. .ie n .IP """$path = Math::PlanePath::CfracDigits\->new ()""" 4 .el .IP "\f(CW$path = Math::PlanePath::CfracDigits\->new ()\fR" 4 .IX Item "$path = Math::PlanePath::CfracDigits->new ()" .PD 0 .ie n .IP """$path = Math::PlanePath::CfracDigits\->new (radix => $radix)""" 4 .el .IP "\f(CW$path = Math::PlanePath::CfracDigits\->new (radix => $radix)\fR" 4 .IX Item "$path = Math::PlanePath::CfracDigits->new (radix => $radix)" .PD Create and return a new path object. .ie n .IP """$n = $path\->n_start()""" 4 .el .IP "\f(CW$n = $path\->n_start()\fR" 4 .IX Item "$n = $path->n_start()" Return 0, the first N in the path. .SH "OEIS" .IX Header "OEIS" Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include .Sp .RS 4 (etc) .RE .PP .Vb 2 \& 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) .Ve .SH "SEE ALSO" .IX Header "SEE ALSO" Math::PlanePath, Math::PlanePath::FractionsTree, Math::PlanePath::CoprimeColumns .PP Math::PlanePath::RationalsTree, Math::PlanePath::GcdRationals, Math::PlanePath::DiagonalRationals .PP Math::ContinuedFraction .SH "HOME PAGE" .IX Header "HOME PAGE" .SH "LICENSE" .IX Header "LICENSE" Copyright 2012, 2013, 2014 Kevin Ryde .PP This file is part of Math-PlanePath. .PP Math-PlanePath is free software; you can redistribute it and/or modify it under the terms of the \s-1GNU\s0 General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version. .PP Math-PlanePath is distributed in the hope that it will be useful, but \&\s-1WITHOUT ANY WARRANTY\s0; without even the implied warranty of \s-1MERCHANTABILITY\s0 or \s-1FITNESS FOR A PARTICULAR PURPOSE. \s0 See the \s-1GNU\s0 General Public License for more details. .PP You should have received a copy of the \s-1GNU\s0 General Public License along with Math-PlanePath. If not, see .