## egyptian fractions

### Data

in lua

#### Tags

conversion, mathematics

### Source Code

``````-- Egyptian fractions algorithm implementation
-- See : http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fractions/egyptian.html

-- Returns a representation of a fraction
local function fraction(num, denum)
return {num = num, denum = denum}
end

-- Returns the egyptian fraction (sum of unit fractions)
--  of a given fraction
-- @num   : the given fraction numerator
-- @denum : the given fraction denominator
-- returns: an array of fractions.
--  Each fraction is represented as {num=<value>, denum=<value>}
local function egypt(num, denum)
local x, y = num, denum
if x == 0 then return {} end
local denum = math.floor(math.ceil(y / x))
local remx, remy = -y % x, y * denum
local rems = egypt(remx, remy)
table.insert(rems, 1, {num = 1, denum = denum})
return rems
end

return egypt
``````
``````-- Tests for egyptian_fractions.lua
local egypt = require 'egyptian_fractions'

local total, pass = 0, 0

local function dec(str, len)
return #str < len
and str .. (('.'):rep(len-#str))
or str:sub(1,len)
end

local function run(message, f)
total = total + 1
local ok, err = pcall(f)
if ok then pass = pass + 1 end
local status = ok and 'PASSED' or 'FAILED'
print(('%02d. %68s: %s'):format(total, dec(message,68), status))
end

-- Checks if two given fractions are the same
-- Note, f2 has a simplified representation: f2[1] is num, f2[2] is denum
local function sameFract(f1, f2)
return (f1.num == f2[1] and f1.denum == f2[2])
end

-- Compares two Egyptian fractions
-- Note: see sameFract definition
local function same(t1, t2)
for k, v in ipairs(t1) do
if not sameFract(v, t2[k]) then return false end
end
return true
end

run('Egyptian fractions test', function()
assert(same(egypt(2, 5),      {{1,3},{1,15}}))
assert(same(egypt(2, 7),      {{1,4},{1,28}}))
assert(same(egypt(2, 9),      {{1,5},{1,45}}))
assert(same(egypt(2,11),      {{1,6},{1,66}}))
assert(same(egypt(1023,1024), {{1,2},{1,3},{1,7},{1,44},{1,9462},{1,373029888}}))
end)

print(('-'):rep(80))
print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
:format(total, pass, total-pass, (pass*100/total)))
``````