Math::Fraction::Egyptian - construct Egyptian representations of fractions
use Math::Fraction::Egyptian ':all'; my @e = to_egyptian(43, 48); # returns 43/48 in Egyptian format my @v = to_common(2, 3, 16); # returns 1/2 + 1/3 + 1/16 in common format
From Wikipedia:
An Egyptian fraction is the sum of distinct unit fractions, such as
1/2 + 1/3 + 1/16
That is, each fraction in the expression has a numerator equal to 1 and a denominator that is a positive integer, and all the denominators differ from each other. The sum of an expression of this type is a positive rational number a/b; for instance the Egyptian fraction above sums to 43/48.
a/b
43/48
Every positive rational number can be represented by an Egyptian fraction. Sums of this type, and similar sums also including 2/3 and 3/4 as summands, were used as a serious notation for rational numbers by the ancient Egyptians, and continued to be used by other civilizations into medieval times.
2/3
3/4
In modern mathematical notation, Egyptian fractions have been superseded by vulgar fractions and decimal notation. However, Egyptian fractions continue to be an object of study in modern number theory and recreational mathematics, as well as in modern historical studies of ancient mathematics.
A common fraction has an infinite number of different Egyptian fraction representations. This module only implements a handful of conversion strategies for conversion of common fractions to Egyptian form; see section STRATEGIES below for details.
Converts fraction $numer/$denom to its Egyptian representation.
$numer/$denom
Example:
my @egypt = to_egyptian(5,9); # converts 5/9 print "@egypt"; # prints FIXME
Converts an Egyptian fraction into a common fraction.
my ($num,$den) = to_common(2,5,11); # 1/2 + 1/5 + 1/11 = ? print "$num/$den"; # prints "87/110"
Uses Euclid's algorithm to determine the greatest common denominator ("GCD") of $x and $y. Returns the GCD.
$x
$y
Reduces fraction $n/$d to simplest terms.
$n/$d
my @x = simplify(25,100); # @x is (1,4)
Returns a list of all prime numbers below 1000.
Returns the prime factors of $n as a list of (prime,multiplicity) pairs. The list is sorted by increasing prime number.
$n
my @pf = prime_factors(120); # 120 = 2 * 2 * 2 * 3 * 5 # @pf = ([2,3],[3,1],[5,1])
If $n is a composite number, returns ($p,$q) such that:
* $p != 1 * $q != 1 * $p x $q == $n
Helper function for determining whether a number is "practical" or not.
Fibonacci, in his Liber Abaci, identifies seven different methods for converting common to Egyptian fractions:
The strategies as implemented below have the following features in common:
Each function call has a signature of the form strategy($numerator, $denominator).
strategy($numerator, $denominator)
The return value from a successful strategy call is the list ($numerator, $denominator, @egyptian): the new numerator, the new denominator, and zero or more new Egyptian factors extracted from the input fraction.
($numerator, $denominator, @egyptian)
Some strategies are not applicable to all inputs. If the strategy determines that it cannot determine the next number in the expansion, it throws an exception (via die()) to indicate the strategy is unsuitable.
die()
Strategy for dealing with "trivial" expansions--if $n is 1, then this fraction is already in Egyptian form.
1
my @x = s_trivial(1,5); # @x = (0,1,5)
For a numerator of 2 with odd prime denominator d, one can use this expansion:
2/d = 2/(d + 1) + 2/d(d + 1)
Attempts to find a multiplier $M such that the scaled denominator $M * $d is a practical number. This lets us break up the scaled numerator $M * $numer as in this example:
$M
$M * $d
$M * $numer
examining 2/9: 9 * 2 is 18, and 18 is a practical number choose $M = 2 scale 2/9 => 4/18 = 3/18 + 1/18 = 1/6 + 1/18
By definition, all numbers N < P, where P is practical, can be represented as a sum of distinct divisors of P.
Returns a true value if $n is a practical number.
For composite denominators, factored as p×q, one can expand 2/pq using the identity 2/pq = 1/aq + 1/apq, where a = (p+1)/2. Clearly p must be odd.
For instance, applying this method for d = pq = 21 gives p=3, q=7, and a=(3+1)/2=2, producing the expansion 2/21 = 1/14 + 1/42.
Implements Fibonacci's greedy algorithm for computing Egyptian fractions:
n/d => 1/ceil(d/n) + ((-d)%n)/(d*ceil(d/n))
# performing the greedy expansion of 3/7: # ceil(7/3) = 3 # new numerator = (-7)%3 = 2 # new denominator = 7 * 3 = 21 # so 3/7 => 1/3 + 2/21 my ($n,$d,$e) = greedy(2,7); print "$n/$d ($e)"; # prints "2/21 (3)"
John Trammell, <johntrammell <at> gmail <dot> com>
<johntrammell <at> gmail <dot> com>
Please report any bugs or feature requests to bug-math-fraction-egyptian at rt.cpan.org, or through the web interface at http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Math-Fraction-Egyptian. I will be notified, and then you'll automatically be notified of progress on your bug as I make changes.
bug-math-fraction-egyptian at rt.cpan.org
You can find documentation for this module with the perldoc command.
perldoc Math::Fraction::Egyptian
You can also look for information at:
GitHub
http://github.com/jotr/math-fraction-egyptian
RT: CPAN's request tracker
http://rt.cpan.org/NoAuth/Bugs.html?Dist=Math-Fraction-Egyptian
AnnoCPAN: Annotated CPAN documentation
http://annocpan.org/dist/Math-Fraction-Egyptian
CPAN Ratings
http://cpanratings.perl.org/d/Math-Fraction-Egyptian
Search CPAN
http://search.cpan.org/dist/Math-Fraction-Egyptian/
Thanks to Project Euler, http://projecteuler.net/, for stretching my mind into obscure areas of mathematics. :-)
:-)
Copyright 2008 John Trammell, all rights reserved.
This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.
1 POD Error
The following errors were encountered while parsing the POD:
Non-ASCII character seen before =encoding in 'p×q,'. Assuming UTF-8
To install Math::Fraction::Egyptian, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Math::Fraction::Egyptian
CPAN shell
perl -MCPAN -e shell install Math::Fraction::Egyptian
For more information on module installation, please visit the detailed CPAN module installation guide.