Find Egyptian fractions in C#

[Egyptian fractions]

An Egyptian fraction is a fraction expressed as a sum of distinct unit fractions. For example, you can write 3/7 as 1/3 + 1/11 + 1/231.

You can write any fraction as an Egyptian fraction and there may be more than one way to do so.

One simple algorithm for finding Egyptian fractions is to subtract the largest unit fraction that is smaller than the original value and then repeat with the result.

This example uses the Fraction class described in the post Make a Fraction class in C#. See that example for most of the class’s details. To handle Egyptian fractions, I added some comparison operators. To make comparing fractions and integers easier, I also added an operator to convert from long to Fraction. The following code shows the most interesting new pieces of the code.

// Return a < b.
public static bool operator <(Fraction a, Fraction b)
{
    return (double)a < (double)b;
}

// Return a > b.
public static bool operator >(Fraction a, Fraction b)
{
    return (double)a > (double)b;
}

The following code shows how the program uses the revised Fraction class to find Egyptian fractions.

// Return a string representation of the Egyptian fraction.
private List<Fraction> GetEgyptianFraction(Fraction frac)
{
    List<Fraction> result = new List<Fraction>();

    // Remove any whole number part.
    int whole_part = (int)(frac.Numerator / frac.Denominator);
    if (whole_part > 0)
    {
        result.Add(whole_part);
        frac = frac - whole_part;
    }

    // Pull out unit fractions.
    long denom = 2;
    while (frac > 0)
    {
        // Make the unit fraction smaller until it fits.
        Fraction unit_fraction = new Fraction(1, denom);
        while (unit_fraction > frac)
        {
            denom++;
            unit_fraction = new Fraction(1, denom);
        }

        // Remove the unit fraction.
        result.Add(unit_fraction);
        frac -= unit_fraction;
        denom++;
    }

    return result;
}

The code first removes any whole number part from the fraction. For example, it converts 12/5 into 2 + 2/5.

Next, as long as the fraction is greater than 0, the code loops through successively smaller unit fractions subtracting any that fit. It tries 1/2, 1/3, 1/4, and so forth until it removes the last part of the fraction.


Download Example   Follow me on Twitter   RSS feed   Donate




This entry was posted in algorithms, classes, mathematics and tagged , , , , , , , , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *