NAME

Math::Fraction::Egyptian - construct Egyptian representations of fractions

SYNOPSIS

    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

DESCRIPTION

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.

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.

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.

FUNCTIONS

to_egyptian($numer, $denom, %attr)

Converts fraction $numer/$denom to its Egyptian representation.

Example:

     my @egypt = to_egyptian(5,9);  # converts 5/9
     print "@egypt";                # prints FIXME

to_common(@denominators)

Converts an Egyptian fraction into a common fraction.

Example:

    my ($num,$den) = to_common(2,5,11);     # 1/2 + 1/5 + 1/11 = ?
    print "$num/$den";                      # prints "87/110"

GCD($x,$y)

Uses Euclid's algorithm to determine the greatest common denominator ("GCD") of $x and $y. Returns the GCD.

simplify($n,$d)

Reduces fraction $n/$d to simplest terms.

Example:

    my @x = simplify(25,100);   # @x is (1,4)

primes()

Returns a list of all prime numbers below 1000.

prime_factors($n)

Returns the prime factors of $n as a list of (prime,multiplicity) pairs. The list is sorted by increasing prime number.

Example:

    my @pf = prime_factors(120);    # 120 = 2 * 2 * 2 * 3 * 5
    # @pf = ([2,3],[3,1],[5,1])

decompose($n)

If $n is a composite number, returns ($p,$q) such that:

    * $p != 1
    * $q != 1
    * $p x $q == $n

sigma(@pairs)

Helper function for determining whether a number is "practical" or not.

STRATEGIES

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).
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.
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.

s_trivial($n,$d)

Strategy for dealing with "trivial" expansions--if $n is 1, then this fraction is already in Egyptian form.

Example:

    my @x = s_trivial(1,5);     # @x = (0,1,5)

s_small_prime($n,$d)

For a numerator of 2 with odd prime denominator d, one can use this expansion:

    2/d = 2/(d + 1) + 2/d(d + 1)

s_practical($n,$d)

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:

    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.

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.

s_greedy($n,$d)

Implements Fibonacci's greedy algorithm for computing Egyptian fractions:

    n/d => 1/ceil(d/n) + ((-d)%n)/(d*ceil(d/n))

Example:

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

AUTHOR

John Trammell, <johntrammell <at> gmail <dot> com>

BUGS

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.