...

/

Solution: Find the Egyptian Fraction

Solution: Find the Egyptian Fraction

Learn how to convert a positive fraction to a series of Egyptian fractions.

We'll cover the following...

Solution #

using System;
using System.Collections.Generic;
class Program
{
/// <summary>
/// Finds the Egyptian fraction denominators.
/// </summary>
/// <param name="numerator">Numerator of the fraction.</param>
/// <param name="denominator">Denominator of the fraction.</param>
/// <returns>An array of denominators of the Egyptian fraction.</returns>
public static int[] EgyptianFraction(int numerator, int denominator)
{
// A List to store denominator
List<int> lstDenominator = new List<int>();
// While loop runs until fraction becomes 0 i.e., numerator becomes 0
while (numerator != 0)
{
// taking ceiling
int x = (int)Math.Ceiling((double)denominator / numerator);
// storing value in lstDenominator list
lstDenominator.Add(x);
// updating new numerator and denominator
numerator = x * numerator - denominator;
denominator = denominator * x;
}
return lstDenominator.ToArray();
}
// Driver code to test above method
public static void Main(string[] args)
{
Console.WriteLine("[" + string.Join(", ", EgyptianFraction(6, 14)) + "]");
Console.WriteLine("[" + string.Join(", ", EgyptianFraction(2, 3)) + "]");
}
}

Explanation

We can generate Egyptian fractions using the greedy algorithm. For a given number of the form ...