Problem

The ancient Egyptians used to express fractions as a sum of several terms where each numerator is one. For example, 4/13 can be represented as 1/(4 + 1/(18 + 1/468)).

Create an algorithm to turn an ordinary fraction a/b, where a < b, into an Egyptian fraction.

Examples

Example 1

1
2
3

Input: a = 2, b = 3
Output: 1/2 + 1/6
Explanation: 2/3 = 1/2 + 1/6

Example 2

1
2
3

Input: a = 4, b = 13
Output: 1/4 + 1/18 + 1/468
Explanation: 4/13 = 1/4 + 1/18 + 1/468

Example 3

1
2
3

Input: a = 6, b = 14
Output: 1/3 + 1/11 + 1/231
Explanation: 6/14 = 3/7 = 1/3 + 1/11 + 1/231

Example 4

1
2
3

Input: a = 12, b = 13
Output: 1/2 + 1/3 + 1/12 + 1/156
Explanation: 12/13 = 1/2 + 1/3 + 1/12 + 1/156

Solutions

Method 1 - Greedy Algorithm

Intuition

The Greedy Algorithm for Egyptian fractions works by repeatedly finding the largest unit fraction (fraction with numerator 1) that is smaller than or equal to the current fraction, subtracting it, and continuing with the remainder.

The key insight is: for any fraction a/b, the largest unit fraction ≤ a/b is 1/⌈b/a⌉ where ⌈⌉ is the ceiling function.

Approach

  1. Find the largest unit fraction: Calculate ceiling(b/a) to get the denominator of the largest unit fraction ≤ a/b
  2. Subtract this unit fraction: Update the fraction to a/b - 1/ceiling(b/a)
  3. Simplify the remainder: Reduce the resulting fraction to its simplest form
  4. Repeat: Continue until the numerator becomes 1
  5. Handle edge cases: Ensure proper fraction (a < b) and handle when a = 1

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

#include <vector>
#include <string>
#include <algorithm>
#include <cmath>

class Solution {
public:
    std::vector<int> egyptianFraction(int a, int b) {
        std::vector<int> result;
        
        // Reduce to lowest terms first
        int g = gcd(a, b);
        a /= g;
        b /= g;
        
        while (a != 0) {
            // Find ceiling of b/a
            int unitDenom = (b + a - 1) / a;  // Ceiling division
            result.push_back(unitDenom);
            
            // Update fraction: a/b - 1/unitDenom
            // = (a * unitDenom - b) / (b * unitDenom)
            a = a * unitDenom - b;
            b = b * unitDenom;
            
            // Reduce to lowest terms
            if (a != 0) {
                int g = gcd(a, b);
                a /= g;
                b /= g;
            }
        }
        
        return result;
    }
    
    std::string egyptianFractionString(int a, int b) {
        std::vector<int> fractions = egyptianFraction(a, b);
        std::string result = "";
        
        for (size_t i = 0; i < fractions.size(); i++) {
            if (i > 0) result += " + ";
            result += "1/" + std::to_string(fractions[i]);
        }
        
        return result;
    }
    
private:
    int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

package main

import (
    "fmt"
    "strconv"
    "strings"
)

func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}

func egyptianFraction(a, b int) []int {
    var result []int
    
    // Reduce to lowest terms first
    g := gcd(a, b)
    a /= g
    b /= g
    
    for a != 0 {
        // Find ceiling of b/a
        unitDenom := (b + a - 1) / a
        result = append(result, unitDenom)
        
        // Update fraction: a/b - 1/unitDenom
        a = a*unitDenom - b
        b = b * unitDenom
        
        // Reduce to lowest terms
        if a != 0 {
            g := gcd(a, b)
            a /= g
            b /= g
        }
    }
    
    return result
}

func egyptianFractionString(a, b int) string {
    fractions := egyptianFraction(a, b)
    var parts []string
    
    for _, denom := range fractions {
        parts = append(parts, "1/"+strconv.Itoa(denom))
    }
    
    return strings.Join(parts, " + ")
}

func main() {
    fmt.Println(egyptianFractionString(2, 3))  // 1/2 + 1/6
    fmt.Println(egyptianFractionString(4, 13)) // 1/4 + 1/18 + 1/468
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

import java.util.*;

class Solution {
    public List<Integer> egyptianFraction(int a, int b) {
        List<Integer> result = new ArrayList<>();
        
        // Reduce to lowest terms first
        int g = gcd(a, b);
        a /= g;
        b /= g;
        
        while (a != 0) {
            // Find ceiling of b/a
            int unitDenom = (b + a - 1) / a;
            result.add(unitDenom);
            
            // Update fraction: a/b - 1/unitDenom
            a = a * unitDenom - b;
            b = b * unitDenom;
            
            // Reduce to lowest terms
            if (a != 0) {
                g = gcd(a, b);
                a /= g;
                b /= g;
            }
        }
        
        return result;
    }
    
    public String egyptianFractionString(int a, int b) {
        List<Integer> fractions = egyptianFraction(a, b);
        StringBuilder result = new StringBuilder();
        
        for (int i = 0; i < fractions.size(); i++) {
            if (i > 0) result.append(" + ");
            result.append("1/").append(fractions.get(i));
        }
        
        return result.toString();
    }
    
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
    // Test cases
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.egyptianFractionString(2, 3));   // 1/2 + 1/6
        System.out.println(sol.egyptianFractionString(4, 13));  // 1/4 + 1/18 + 1/468
        System.out.println(sol.egyptianFractionString(6, 14));  // 1/3 + 1/11 + 1/231
        System.out.println(sol.egyptianFractionString(12, 13)); // 1/2 + 1/3 + 1/12 + 1/156
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class Solution {
    fun egyptianFraction(a: Int, b: Int): List<Int> {
        val result = mutableListOf<Int>()
        var numerator = a
        var denominator = b
        
        // Reduce to lowest terms first
        val g = gcd(numerator, denominator)
        numerator /= g
        denominator /= g
        
        while (numerator != 0) {
            // Find ceiling of denominator/numerator
            val unitDenom = (denominator + numerator - 1) / numerator
            result.add(unitDenom)
            
            // Update fraction: numerator/denominator - 1/unitDenom
            numerator = numerator * unitDenom - denominator
            denominator = denominator * unitDenom
            
            // Reduce to lowest terms
            if (numerator != 0) {
                val gcdVal = gcd(numerator, denominator)
                numerator /= gcdVal
                denominator /= gcdVal
            }
        }
        
        return result
    }
    
    fun egyptianFractionString(a: Int, b: Int): String {
        val fractions = egyptianFraction(a, b)
        return fractions.joinToString(" + ") { "1/$it" }
    }
    
    private fun gcd(a: Int, b: Int): Int {
        var x = a
        var y = b
        while (y != 0) {
            val temp = y
            y = x % y
            x = temp
        }
        return x
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

from typing import List
from math import gcd

class Solution:
    def egyptian_fraction(self, a: int, b: int) -> List[int]:
        """
        Convert fraction a/b to Egyptian fraction representation.
        Returns list of denominators for unit fractions.
        """
        result = []
        
        # Reduce to lowest terms first
        g = gcd(a, b)
        a //= g
        b //= g
        
        while a != 0:
            # Find ceiling of b/a
            unit_denom = (b + a - 1) // a
            result.append(unit_denom)
            
            # Update fraction: a/b - 1/unit_denom
            # = (a * unit_denom - b) / (b * unit_denom)
            a = a * unit_denom - b
            b = b * unit_denom
            
            # Reduce to lowest terms
            if a != 0:
                g = gcd(a, b)
                a //= g
                b //= g
        
        return result
    
    def egyptian_fraction_string(self, a: int, b: int) -> str:
        """
        Convert fraction a/b to Egyptian fraction string representation.
        """
        fractions = self.egyptian_fraction(a, b)
        return " + ".join(f"1/{denom}" for denom in fractions)
    
    def verify_egyptian_fraction(self, a: int, b: int, denominators: List[int]) -> bool:
        """
        Verify that the Egyptian fraction equals the original fraction.
        """
        from fractions import Fraction
        
        original = Fraction(a, b)
        egyptian_sum = sum(Fraction(1, denom) for denom in denominators)
        
        return original == egyptian_sum

# Example usage and testing
def test_egyptian_fractions():
    sol = Solution()
    
    test_cases = [
        (2, 3),   # Expected: 1/2 + 1/6
        (4, 13),  # Expected: 1/4 + 1/18 + 1/468
        (6, 14),  # Expected: 1/3 + 1/11 + 1/231
        (12, 13), # Expected: 1/2 + 1/3 + 1/12 + 1/156
        (5, 8),   # Expected: 1/2 + 1/8
        (3, 7),   # Expected: 1/3 + 1/11 + 1/231
    ]
    
    for a, b in test_cases:
        result = sol.egyptian_fraction_string(a, b)
        denominators = sol.egyptian_fraction(a, b)
        is_valid = sol.verify_egyptian_fraction(a, b, denominators)
        
        print(f"{a}/{b} = {result}")
        print(f"Verification: {is_valid}")
        print()

if __name__ == "__main__":
    test_egyptian_fractions()
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

fn gcd(mut a: i32, mut b: i32) -> i32 {
    while b != 0 {
        let temp = b;
        b = a % b;
        a = temp;
    }
    a
}

fn egyptian_fraction(mut a: i32, mut b: i32) -> Vec<i32> {
    let mut result = Vec::new();
    
    // Reduce to lowest terms first
    let g = gcd(a, b);
    a /= g;
    b /= g;
    
    while a != 0 {
        // Find ceiling of b/a
        let unit_denom = (b + a - 1) / a;
        result.push(unit_denom);
        
        // Update fraction: a/b - 1/unit_denom
        a = a * unit_denom - b;
        b = b * unit_denom;
        
        // Reduce to lowest terms
        if a != 0 {
            let g = gcd(a, b);
            a /= g;
            b /= g;
        }
    }
    
    result
}

fn egyptian_fraction_string(a: i32, b: i32) -> String {
    let fractions = egyptian_fraction(a, b);
    fractions.iter()
        .map(|&denom| format!("1/{}", denom))
        .collect::<Vec<_>>()
        .join(" + ")
}

fn main() {
    println!("{}", egyptian_fraction_string(2, 3));   // 1/2 + 1/6
    println!("{}", egyptian_fraction_string(4, 13));  // 1/4 + 1/18 + 1/468
    println!("{}", egyptian_fraction_string(6, 14));  // 1/3 + 1/11 + 1/231
    println!("{}", egyptian_fraction_string(12, 13)); // 1/2 + 1/3 + 1/12 + 1/156
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

function gcd(a: number, b: number): number {
    while (b !== 0) {
        const temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

function egyptianFraction(a: number, b: number): number[] {
    const result: number[] = [];
    
    // Reduce to lowest terms first
    const g = gcd(a, b);
    a = Math.floor(a / g);
    b = Math.floor(b / g);
    
    while (a !== 0) {
        // Find ceiling of b/a
        const unitDenom = Math.floor((b + a - 1) / a);
        result.push(unitDenom);
        
        // Update fraction: a/b - 1/unitDenom
        a = a * unitDenom - b;
        b = b * unitDenom;
        
        // Reduce to lowest terms
        if (a !== 0) {
            const g = gcd(a, b);
            a = Math.floor(a / g);
            b = Math.floor(b / g);
        }
    }
    
    return result;
}

function egyptianFractionString(a: number, b: number): string {
    const fractions = egyptianFraction(a, b);
    return fractions.map(denom => `1/${denom}`).join(" + ");
}

// Example usage
console.log(egyptianFractionString(2, 3));   // 1/2 + 1/6
console.log(egyptianFractionString(4, 13));  // 1/4 + 1/18 + 1/468
console.log(egyptianFractionString(6, 14));  // 1/3 + 1/11 + 1/231
console.log(egyptianFractionString(12, 13)); // 1/2 + 1/3 + 1/12 + 1/156

Complexity

  • ⏰ Time complexity: O(log(min(a,b))) - Each iteration significantly reduces the fraction
  • 🧺 Space complexity: O(k) where k is the number of unit fractions in the result

Method 2 - Alternative Approach with Better Bounds

Enhanced Intuition

While the greedy algorithm always works, sometimes it can produce unit fractions with very large denominators. This alternative approach tries to find a representation that might have smaller denominators in some cases.

Alternative Implementation

Python Alternative
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100

from typing import List, Tuple
from math import gcd
from fractions import Fraction

class EgyptianFractionAlternative:
    def __init__(self):
        self.cache = {}
    
    def egyptian_fraction_optimized(self, a: int, b: int) -> List[int]:
        """
        Alternative approach that tries to find representations with smaller denominators.
        """
        if (a, b) in self.cache:
            return self.cache[(a, b)]
        
        # Reduce to lowest terms
        g = gcd(a, b)
        a, b = a // g, b // g
        
        if a == 1:
            return [b]
        
        # Try the greedy approach
        greedy_result = self._greedy_approach(a, b)
        
        # For small fractions, try to find better representations
        if a <= 10 and b <= 100:
            better_result = self._try_better_representation(a, b)
            if better_result and len(better_result) <= len(greedy_result):
                self.cache[(a, b)] = better_result
                return better_result
        
        self.cache[(a, b)] = greedy_result
        return greedy_result
    
    def _greedy_approach(self, a: int, b: int) -> List[int]:
        """Standard greedy algorithm."""
        result = []
        while a > 0:
            unit_denom = (b + a - 1) // a
            result.append(unit_denom)
            a = a * unit_denom - b
            b = b * unit_denom
            if a != 0:
                g = gcd(a, b)
                a, b = a // g, b // g
        return result
    
    def _try_better_representation(self, a: int, b: int) -> List[int]:
        """
        Try to find a representation with potentially smaller denominators.
        This is a simplified heuristic approach.
        """
        best_result = None
        min_max_denom = float('inf')
        
        # Try splitting the fraction in different ways
        for i in range(2, min(b, 20)):  # Limit search space
            if b % i == 0:
                # Try representing as sum of simpler fractions
                try:
                    frac = Fraction(a, b)
                    unit_frac = Fraction(1, i)
                    if frac > unit_frac:
                        remainder = frac - unit_frac
                        if remainder.denominator <= 1000:  # Avoid very large denominators
                            remainder_egyptian = self._greedy_approach(remainder.numerator, remainder.denominator)
                            candidate = [i] + remainder_egyptian
                            max_denom = max(candidate)
                            if max_denom < min_max_denom:
                                best_result = candidate
                                min_max_denom = max_denom
                except:
                    continue
        
        return best_result

# Test the alternative approach
def test_alternative_approach():
    alt_solver = EgyptianFractionAlternative()
    
    test_cases = [
        (2, 3),
        (4, 13),
        (5, 6),
        (7, 12),
        (11, 12)
    ]
    
    for a, b in test_cases:
        greedy = alt_solver._greedy_approach(a, b)
        optimized = alt_solver.egyptian_fraction_optimized(a, b)
        
        print(f"{a}/{b}:")
        print(f"  Greedy: {' + '.join(f'1/{d}' for d in greedy)}")
        print(f"  Optimized: {' + '.join(f'1/{d}' for d in optimized)}")
        print()

if __name__ == "__main__":
    test_alternative_approach()

Alternative Complexity

  • ⏰ Time complexity: O(k * log(min(a,b))) where k is the search space limit
  • 🧺 Space complexity: O(k) for caching and result storage

Analysis

Algorithm Properties

Greedy Algorithm Guarantees:

  • Always terminates for proper fractions (a < b)
  • Produces a valid Egyptian fraction representation
  • Each successive unit fraction has a larger denominator
  • Number of terms is typically small for most practical inputs

Mathematical Background:

  • Based on the Fibonacci-Sylvester algorithm
  • The denominators grow approximately exponentially
  • For fraction a/b, the number of terms is usually O(log b)

Historical Context:

  • Ancient Egyptians used this representation in the Rhind Papyrus (1650 BCE)
  • All fractions except 2/3 were represented as sums of unit fractions
  • This method ensures unique representation when using the greedy approach

Edge Cases

  1. Unit fractions: If a = 1, return [b]
  2. Reducible fractions: Always reduce to lowest terms first
  3. Large denominators: The greedy algorithm can sometimes produce very large denominators
  4. Verification: Always verify that the sum equals the original fraction

Applications

  • Number theory: Understanding fraction representations
  • Computer algebra: Symbolic computation systems
  • Educational: Teaching fraction concepts
  • Historical mathematics: Studying ancient calculation methods

The greedy algorithm is the most commonly used approach due to its simplicity and guaranteed termination, making it ideal for the Egyptian fraction problem.