Understanding Egyptian Fractions with a Simple Java Program

Introduction

Have you ever heard of Egyptian Fractions? They are a way of representing fractions as a sum of distinct unit fractions (fractions with a numerator of 1). For example, instead of writing 5/6 directly, it can be written as the sum of 1/2 + 1/3. This method was used by the ancient Egyptians, which is why it’s called Egyptian Fraction.

In this blog post, we will break down a simple Java program that converts a given fraction into its Egyptian Fraction representation. The algorithm used here is a greedy approach, where we always subtract the largest possible unit fraction from the original fraction at each step.

Let’s get started!

What is the Algorithm?

The algorithm works by:

Finding the smallest unit fraction that is greater than or equal to the given fraction.
Subtracting this unit fraction from the original fraction.
Repeating the process until the numerator becomes zero.

For example, to convert 5/6:

First, we find the largest unit fraction smaller than 5/6, which is 1/2.
We subtract 1/2 from 5/6, leaving 4/12, which simplifies to 1/3.
Finally, we subtract 1/3, and we’re left with 0, so the process ends.

Step-by-Step Code Explanation

Let’s look at the Java code that implements this algorithm:

public class EgyptianFraction {
    public static void main(String[] args) {
        int numerator = 5, denominator = 6;
        System.out.print("Egyptian Fraction: ");
        printEgyptianFraction(numerator, denominator);
    }

    public static void printEgyptianFraction(int numerator, int denominator) {
        while (numerator != 0) {
            // Get the smallest unit fraction
            int unitDenominator = (int) Math.ceil((double) denominator / numerator);
            System.out.print("1/" + unitDenominator + " ");
            
            // Update numerator and denominator
            numerator = numerator * unitDenominator - denominator;
            denominator = denominator * unitDenominator;
        }
    }
}

Breaking Down the Code

Let’s go through the code step by step.

1. Main Method

int numerator = 5, denominator = 6;
System.out.print("Egyptian Fraction: ");
printEgyptianFraction(numerator, denominator);

Explanation:
- We initialize the fraction 5/6. Our goal is to convert this fraction into an Egyptian Fraction.
- The method printEgyptianFraction() is called with 5 as the numerator and 6 as the denominator.

2. printEgyptianFraction Method

public static void printEgyptianFraction(int numerator, int denominator) {
    while (numerator != 0) {
        // Get the smallest unit fraction
        int unitDenominator = (int) Math.ceil((double) denominator / numerator);
        System.out.print("1/" + unitDenominator + " ");
        
        // Update numerator and denominator
        numerator = numerator * unitDenominator - denominator;
        denominator = denominator * unitDenominator;
    }
}

Explanation:
- This method does the actual work of converting the fraction into its Egyptian Fraction form.
- The while loop keeps running as long as the numerator is not 0. In each iteration, we do the following:
  1. Find the smallest unit fraction:
    - We calculate the smallest possible denominator that forms a unit fraction smaller than or equal to the current fraction. This is done by finding the ceiling of denominator / numerator.
    - For example, for 5/6, we calculate Math.ceil(6 / 5), which results in 2. Therefore, the first unit fraction is 1/2.
  2. Subtract the unit fraction from the current fraction:
    - After printing the current unit fraction, we update the numerator and denominator to represent the new fraction left after subtracting the unit fraction.
    - The updated numerator is numerator * unitDenominator - denominator, and the updated denominator is denominator * unitDenominator.
    - For 5/6, after subtracting 1/2, we are left with 4/12 (or 1/3).

3. Output

The output is printed directly to the console. For the input fraction 5/6, the output will be:

Egyptian Fraction: 1/2 1/3

This means that 5/6 is represented as the sum of 1/2 + 1/3.

How Does the Program Work?

Here’s a quick breakdown of the process:

The program starts with a fraction, for example 5/6.
It calculates the largest unit fraction (1/2 for 5/6) and subtracts it.
This process continues until the remaining fraction is 0, and we get the Egyptian Fraction representation.

Example Walkthrough

Let’s go through the steps for 5/6 in more detail:

Initial Fraction: 5/6
Step 1: Find the smallest unit fraction. Math.ceil(6 / 5) gives 2, so we use 1/2.
Subtracting 1/2 from 5/6 gives 4/12, which simplifies to 1/3.
Step 2: Now, we repeat the process for 4/12:
- Math.ceil(12 / 4) gives 3, so we use 1/3.
Subtracting 1/3 leaves 0, and the process ends.

Thus, 5/6 is represented as 1/2 + 1/3.

Edge Cases

If the numerator is 0, the loop will not run, and no output will be generated.
If the fraction is already a unit fraction (e.g., 1/2), the program will simply output the fraction and terminate.

Conclusion

In this post, we’ve learned how to represent a fraction as an Egyptian Fraction using a greedy algorithm. The program works by repeatedly subtracting the largest possible unit fraction from the fraction until the remainder is zero. This is a fun and interesting way to break down fractions, and it’s an excellent example of using greedy algorithms in practice.

Here’s the complete code for reference:

public class EgyptianFraction {
    public static void main(String[] args) {
        int numerator = 5, denominator = 6;
        System.out.print("Egyptian Fraction: ");
        printEgyptianFraction(numerator, denominator);
    }

    public static void printEgyptianFraction(int numerator, int denominator) {
        while (numerator != 0) {
            // Get the smallest unit fraction
            int unitDenominator = (int) Math.ceil((double) denominator / numerator);
            System.out.print("1/" + unitDenominator + " ");
            
            // Update numerator and denominator
            numerator = numerator * unitDenominator - denominator;
            denominator = denominator * unitDenominator;
        }
    }
}

Feel free to experiment with different fractions and explore how the program generates the Egyptian Fraction representation!

That’s it for today! Happy coding!