Egyptian Fraction

 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

  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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

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

class Solution:
    def __init__(self):
        # Cache for previously computed fractions: (a, b) -> list of denominators
        self.cache = {}

    def egyptian_fraction(self, a: int, b: int) -> List[int]:
        """
        Alternative (heuristic) Egyptian fraction generator that uses a bounded
        search over candidate first denominators and falls back to the greedy
        algorithm when needed. Signature matches Method 1: egyptian_fraction(a, b).
        Returns a list of denominators representing the unit fractions.
        """
        if (a, b) in self.cache:
            return self.cache[(a, b)]

        # Reduce to lowest terms
        g = gcd(a, b)
        a //= g
        b //= g

        if a == 1:
            self.cache[(a, b)] = [b]
            return [b]

        # Always compute the greedy fallback
        greedy_result = self._greedy_approach(a, b)

        # Bounded search parameters (tunable): limit candidates to small denominators
        MAX_CAND = min(b, 20)
        best_result = greedy_result
        best_max_denom = max(greedy_result) if greedy_result else float('inf')

        # Try a few small first-denominator candidates to improve the decomposition
        for d in range(2, MAX_CAND):
            unit_frac = Fraction(1, d)
            frac = Fraction(a, b)
            if unit_frac >= frac:
                break

            remainder = frac - unit_frac
            # avoid exploding denominators: skip if remainder denominator becomes huge
            if remainder.denominator > 10000:
                continue

            remainder_egyptian = self._greedy_approach(remainder.numerator, remainder.denominator)
            candidate = [d] + remainder_egyptian

            # Choose candidate with smaller maximal denominator (heuristic)
            cand_max = max(candidate) if candidate else float('inf')
            if cand_max < best_max_denom or (cand_max == best_max_denom and len(candidate) < len(best_result)):
                best_result = candidate
                best_max_denom = cand_max

        self.cache[(a, b)] = best_result
        return best_result

    def _greedy_approach(self, a: int, b: int) -> List[int]:
        """Standard greedy algorithm for Egyptian fractions."""
        result: List[int] = []
        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 //= g
                b //= g
        return result

    def _try_better_representation(self, a: int, b: int) -> List[int] | None:
        """
        (Optional helper) -- kept for completeness but not used by default in the
        bounded search above. Returns a candidate or None.
        """
        best_result = None
        min_max_denom = float('inf')

        for i in range(2, min(b, 50)):
            try:
                frac = Fraction(a, b)
                unit_frac = Fraction(1, i)
                if frac > unit_frac:
                    remainder = frac - unit_frac
                    if remainder.denominator <= 1000:
                        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 Exception:
                continue

        return best_result


def test_alternative_approach():
    sol = Solution()
    test_cases = [
        (2, 3),
        (4, 13),
        (5, 6),
        (7, 12),
        (11, 12),
    ]

    for a, b in test_cases:
        greedy = sol._greedy_approach(a, b)
        optimized = sol.egyptian_fraction(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()