.\" 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::FactorRationals 3pm" .TH Math::PlanePath::FactorRationals 3pm "2014-08-30" "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::FactorRationals \-\- rationals by prime powers .SH "SYNOPSIS" .IX Header "SYNOPSIS" .Vb 3 \& use Math::PlanePath::FactorRationals; \& my $path = Math::PlanePath::FactorRationals\->new; \& my ($x, $y) = $path\->n_to_xy (123); .Ve .SH "DESCRIPTION" .IX Header "DESCRIPTION" This path enumerates rationals X/Y with no common factor, based on the prime powers in numerator and denominator, as per .IX Xref "McCrimmon, Kevin Freilich, Gerald Sagher, Yoram" .Sp .RS 4 Kevin McCrimmon, \*(L"Enumeration of the Positive Rationals\*(R", American Math. Monthly, Nov 1960, page 868. .Sp Gerald Freilich, \*(L"A Denumerability Formula for the Rationals\*(R", American Math. Monthly, Nov 1965, pages 1013\-1014. .Sp Yoram Sagher, \*(L"Counting the rationals\*(R", American Math. Monthly, Nov 1989, page 823. .RE .PP The result is .PP .Vb 10 \& 15 | 15 60 240 735 960 1815 \& 14 | 14 126 350 1134 1694 \& 13 | 13 52 117 208 325 468 637 832 1053 1300 1573 \& 12 | 24 600 1176 2904 \& 11 | 11 44 99 176 275 396 539 704 891 1100 \& 10 | 10 90 490 810 1210 \& 9 | 27 108 432 675 1323 1728 2700 3267 \& 8 | 32 288 800 1568 2592 3872 \& 7 | 7 28 63 112 175 252 448 567 700 847 \& 6 | 6 150 294 726 \& 5 | 5 20 45 80 180 245 320 405 605 \& 4 | 8 72 200 392 648 968 \& 3 | 3 12 48 75 147 192 300 363 \& 2 | 2 18 50 98 162 242 \& 1 | 1 4 9 16 25 36 49 64 81 100 121 \& Y=0 | \& \-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=0 1 2 3 4 5 6 7 8 9 10 11 .Ve .PP A given fraction X/Y with no common factor has a prime factorization .PP .Vb 1 \& X/Y = p1^e1 * p2^e2 * ... .Ve .PP The exponents e[i] are positive, negative or zero, being positive when the prime is in the numerator or negative when in the denominator. Those exponents are represented in an integer N by mapping the exponents to non-negative, .PP .Vb 1 \& N = p1^f(e1) * p2^f(e2) * ... \& \& f(e) = 2*e if e >= 0 \& = 1\-2*e if e < 0 \& \& f(e) e \& \-\-\- \-\-\- \& 0 0 \& 1 \-1 \& 2 1 \& 3 \-2 \& 4 2 .Ve .PP For example .PP .Vb 2 \& X/Y = 125/7 = 5^3 * 7^(\-1) \& encoded as N = 5^(2*3) * 7^(1\-2*(\-1)) = 5^6 * 7^1 = 5359375 \& \& N=3 \-> 3^\-1 = 1/3 \& N=9 \-> 3^1 = 3/1 \& N=27 \-> 3^\-2 = 1/9 \& N=81 \-> 3^2 = 9/1 .Ve .PP The effect is to distinguish prime factors of the numerator or denominator by odd or even exponents of those primes in N. Since X and Y have no common factor a given prime appears in one and not the other. The oddness or evenness of the p^f() exponent in N can then encode which of the two X or Y it came from. .PP The exponent f(e) in N has term 2*e in both cases, but the exponents from Y are reduced by 1. This can be expressed in the following form. Going from X,Y to N doesn't need to factorize X, only Y. .PP .Vb 3 \& X^2 * Y^2 \& N = \-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& distinct primes in Y .Ve .PP N=1,2,3,8,5,6,etc in the column X=1 is integers with odd powers of prime factors. These are the fractions 1/Y so the exponents of the primes are all negative and thus all exponents in N are odd. .PP N=1,4,9,16,etc in row Y=1 are the perfect squares. That row is the integers X/1 so the exponents are all positive and thus in N become 2*e, giving simply N=X^2. .IX Xref "Square numbers" .SS "Odd/Even" .IX Subsection "Odd/Even" Option \f(CW\*(C`factor_coding => "odd/even"\*(C'\fR changes the f() mapping to numerator exponents as odd numbers and denominator exponents as even. .PP .Vb 2 \& f(e) = 2*e\-1 if e > 0 \& = \-2*e if e <= 0 .Ve .PP The effect is simply to transpose X<\->Y. .PP \&\*(L"odd/even\*(R" is the form given by Kevin McCrimmon and Gerald Freilich. The default \*(L"even/odd\*(R" is the form given by Yoram Sagher. .SS "Negabinary" .IX Subsection "Negabinary" Option \f(CW\*(C`factor_coding => "negabinary"\*(C'\fR changes the f() mapping to negabinary as suggested in .IX Xref "Bradley, David M." .Sp .RS 4 David M. Bradley, \*(L"Counting the Positive Rationals: A Brief Survey\*(R", .RE .PP This coding is not as compact as odd/even and tends to make bigger N values, .PP .Vb 10 \& 13 | 2197 4394 6591 140608 10985 13182 15379 281216 \& 12 | 108 540 756 \& 11 | 1331 2662 3993 85184 6655 7986 9317 170368 \& 10 | 1000 3000 7000 \& 9 | 9 18 576 45 63 1152 \& 8 | 8192 24576 40960 57344 \& 7 | 343 686 1029 21952 1715 2058 43904 \& 6 | 216 1080 1512 \& 5 | 125 250 375 8000 750 875 16000 \& 4 | 4 12 20 28 \& 3 | 27 54 1728 135 189 3456 \& 2 | 8 24 40 56 \& 1 | 1 2 3 64 5 6 7 128 \& Y=0 | \& \-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=0 1 2 3 4 5 6 7 8 .Ve .SS "Reversing Binary" .IX Subsection "Reversing Binary" Option \f(CW\*(C`factor_coding => "revbinary"\*(C'\fR changes the f() mapping to \&\*(L"reversing binary\*(R" where a given integer is represented as a sum of powers 2^k with alternating signs .PP .Vb 1 \& e = 2^k1 \- 2^k2 + 2^k3 \- ... 0 <= k1 < k2 < k3 \& \& f(e) e \& \-\-\- \-\-\- \& 0 0 \& 1 1 \& 2 2 \& 3 \-1 \& 4 4 \& 5 \-3 \& 6 \-2 \& 7 3 .Ve .PP This representation is per Knuth volume 2 section 4.1 exercise 27. The exercise there is to show all integers can be represented this way. .PP .Vb 12 \& 9 | 729 1458 2916 3645 5103 93312 7290 \& 8 | 32 96 160 224 288 \& 7 | 343 686 1029 1372 1715 2058 43904 3087 3430 \& 6 | 216 1080 1512 \& 5 | 125 250 375 500 750 875 16000 1125 \& 4 | 64 192 320 448 576 \& 3 | 27 54 108 135 189 3456 270 \& 2 | 8 24 40 56 72 \& 1 | 1 2 3 4 5 6 7 128 9 10 \& Y=0 | \& \-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=0 1 2 3 4 5 6 7 8 9 10 .Ve .PP The X axis begins with the integers 1 to 7 because f(1)=1 and f(2)=2 so N=X until X has a prime p^3 or higher power. The first such is X=8=2^3 which is f(7)=3 so N=2^7=128. .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::FactorRationals\->new ()""" 4 .el .IP "\f(CW$path = Math::PlanePath::FactorRationals\->new ()\fR" 4 .IX Item "$path = Math::PlanePath::FactorRationals->new ()" .PD 0 .ie n .IP """$path = Math::PlanePath::FactorRationals\->new (factor_coding => $str)""" 4 .el .IP "\f(CW$path = Math::PlanePath::FactorRationals\->new (factor_coding => $str)\fR" 4 .IX Item "$path = Math::PlanePath::FactorRationals->new (factor_coding => $str)" .PD Create and return a new path object. \f(CW\*(C`factor_coding\*(C'\fR can be .Sp .Vb 4 \& "even/odd" (the default) \& "odd/even" \& "negabinary" \& "revbinary" .Ve .ie n .IP """($x,$y) = $path\->n_to_xy ($n)""" 4 .el .IP "\f(CW($x,$y) = $path\->n_to_xy ($n)\fR" 4 .IX Item "($x,$y) = $path->n_to_xy ($n)" Return X,Y coordinates of point \f(CW$n\fR on the path. If there's no point \&\f(CW$n\fR then the return is an empty list. .Sp This depends on factorizing \f(CW$n\fR and in the current code there's a hard limit on the amount of factorizing attempted. If \f(CW$n\fR is too big then the return is an empty list. .ie n .IP """$n = $path\->xy_to_n ($x,$y)""" 4 .el .IP "\f(CW$n = $path\->xy_to_n ($x,$y)\fR" 4 .IX Item "$n = $path->xy_to_n ($x,$y)" Return the N point number for coordinates \f(CW\*(C`$x,$y\*(C'\fR. If there's nothing at \&\f(CW\*(C`$x,$y\*(C'\fR, such as when they have a common factor, then return \f(CW\*(C`undef\*(C'\fR. .Sp This depends on factorizing \f(CW$y\fR, or factorizing both \f(CW$x\fR and \f(CW$y\fR for negabinary or revbinary. In the current code there's a hard limit on the amount of factorizing attempted. If the coordinates are too big then the return is \f(CW\*(C`undef\*(C'\fR. .PP The current factorizing limits handle anything up to 2^32, and above that numbers comprised of small factors. But big numbers with big factors are not handled. Is this a good idea? For large inputs there's no merit in disappearing into a nearly-infinite loop. Perhaps the limits could be configurable and/or some advanced factoring modules attempted for a while if/when available. .SH "OEIS" .IX Header "OEIS" This enumeration of the rationals is in Sloane's Online Encyclopedia of Integer Sequences in the following forms .Sp .RS 4 (etc) .RE .PP .Vb 5 \& A071974 X coordinate, numerators \& A071975 Y coordinate, denominators \& A019554 X*Y product \& A102631 N in column X=1, n^2/squarefreekernel(n) \& A072345 X and Y at N=2^k, being alternately 1 and 2^k \& \& A011262 permutation N at transpose Y/X (exponents mangle odd<\->even) \& \& A060837 permutation DiagonalRationals \-> FactorRationals \& A071970 permutation RationalsTree CW \-> FactorRationals .Ve .PP The last A071970 is rationals taken in order of the Stern diatomic sequence stern[i]/stern[i+1] which is the Calkin-Wilf tree rows (\*(L"Calkin-Wilf Tree\*(R" in Math::PlanePath::RationalsTree). .PP The negabinary representation is .PP .Vb 4 \& A053985 index \-> signed \& A005351 signed positives \-> index \& A039724 signed positives \-> index, in binary \& A005352 signed negatives \-> index .Ve .PP The reversing binary representation is .PP .Vb 3 \& A065620 index \-> signed \& A065621 signed positives \-> index \& A048724 signed negatives \-> index .Ve .SH "SEE ALSO" .IX Header "SEE ALSO" Math::PlanePath, Math::PlanePath::GcdRationals, Math::PlanePath::RationalsTree, Math::PlanePath::CoprimeColumns .SS "Other Ways to Do It" .IX Subsection "Other Ways to Do It" Niven gives another prime factor based construction but encoding N by runs of 1\-bits, .Sp .RS 4 Ivan Niven, \*(L"Note on a paper by L. S. Johnston\*(R", American Math. Monthly, volume 55, number 6, June-July 1948, page 358. .RE .PP N is written in binary each 0\-bit is considered a separator. The number of 1\-bits between each .PP .Vb 4 \& N = 11 0 0 111 0 11 binary \& | | | \& 2 0 3 2 f(e) = run lengths of 1\-bits \& \-1 0 +2 \-1 e exponent by "odd/even" style \& \& X/Y = 2^(\-1) * 3^(+2) * 5^0 * 7^(\-1) .Ve .PP Kevin McCrimmon's note begins with a further possible encoding for N where the prime powers from numerator are spread out to primes p[2i+1] and with 0 powers sending a p[2i] power to the denominator. In this form the primes from X and Y spread out to different primes rather than different exponents. .SH "HOME PAGE" .IX Header "HOME PAGE" .SH "LICENSE" .IX Header "LICENSE" Copyright 2011, 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 .