Rosetta Code

Greedy algorithm for Egyptian fractions

Decompose sample rational numbers into Egyptian fractions with the standard greedy method, including inputs whose unit-fraction denominators run to 25 digits.

Medium View source

Edit the source, then Run. Checks start after your first Run. Ctrl/⌘ + Enter runs; Tab indents. Preview services use sample data and never contact a real service.

Sourcerosettacode/popular/greedy_algorithm_for_egyptian_fractions.vibe
type RunResult = {
  eight_elevenths: array<string>,
  five_one_hundred_twenty_firsts: array<string>,
  three_sevenths: array<string>
}

def gcd(a: int, b: int) -> int
  left = a.abs
  right = b.abs

  while right != 0
    remainder = left % right
    left = right
    right = remainder
  end

  left
end

def egyptian_fraction(numerator: int, denominator: int) -> array<string>
  terms: array<string> = []
  left = numerator
  right = denominator

  while left != 0
    unit = (right + left - 1) // left
    terms << "1/#{unit}"
    left = (left * unit) - right
    right = right * unit

    if left != 0
      divisor = gcd(left, right)
      left = left // divisor
      right = right // divisor
    end
  end

  terms
end

def run -> RunResult
  {
    three_sevenths: egyptian_fraction(3, 7),
    eight_elevenths: egyptian_fraction(8, 11),
    five_one_hundred_twenty_firsts: egyptian_fraction(5, 121)
  }
end

Output

Click Run example to see the result.

Code checks

Run once to load the checker. Your code stays in this browser.