Greedy algorithm for Egyptian fractions: Difference between revisions
Content added Content deleted
(Add Rust implementation) |
(Added Wren) |
||
Line 3,623: | Line 3,623: | ||
Term max is 97/53 with 9 terms |
Term max is 97/53 with 9 terms |
||
Denominator max is 8/97 with 150 digits 57950...89665</pre> |
Denominator max is 8/97 with 150 digits 57950...89665</pre> |
||
=={{header|Wren}}== |
|||
{{trans|Kotlin}} |
|||
{{libheader|Wren-big}} |
|||
We use the BigRat class in the above module to represent arbitrary size fractions. |
|||
<lang ecmascript>import "/big" for BigInt, BigRat |
|||
var toEgyptianHelper // recursive |
|||
toEgyptianHelper = Fn.new { |n, d, fracs| |
|||
if (n == BigInt.zero) return |
|||
var divRem = d.divMod(n) |
|||
var div = divRem[0] |
|||
if (divRem[1] > BigInt.zero) div = div.inc |
|||
fracs.add(BigRat.new(BigInt.one, div)) |
|||
var n2 = (-d) % n |
|||
if (n2 < BigInt.zero) n2 = n2 + n |
|||
var d2 = d * div |
|||
var f = BigRat.new(n2, d2) |
|||
if (f.num == BigInt.one) { |
|||
fracs.add(f) |
|||
return |
|||
} |
|||
toEgyptianHelper.call(f.num, f.den, fracs) |
|||
} |
|||
var toEgyptian = Fn.new { |r| |
|||
if (r.num == BigInt.zero) return [r] |
|||
var fracs = [] |
|||
if (r.num.abs >= r.den.abs) { |
|||
var div = BigRat.new(r.num/r.den, BigInt.one) |
|||
var rem = r - div |
|||
fracs.add(div) |
|||
toEgyptianHelper.call(rem.num, rem.den, fracs) |
|||
} else { |
|||
toEgyptianHelper.call(r.num, r.den, fracs) |
|||
} |
|||
return fracs |
|||
} |
|||
BigRat.showAsInt = true |
|||
var fracs = [BigRat.new(43, 48), BigRat.new(5, 121), BigRat.new(2014, 59)] |
|||
for (frac in fracs) { |
|||
var list = toEgyptian.call(frac) |
|||
System.print("%(frac) -> %(list.join(" + "))") |
|||
} |
|||
for (r in [98, 998]) { |
|||
if (r == 98) { |
|||
System.print("\nFor proper fractions with 1 or 2 digits:") |
|||
} else { |
|||
System.print("\nFor proper fractions with 1, 2 or 3 digits:") |
|||
} |
|||
var maxSize = 0 |
|||
var maxSizeFracs = [] |
|||
var maxDen = BigInt.zero |
|||
var maxDenFracs = [] |
|||
var sieve = List.filled(r + 1, null) // to eliminate duplicates |
|||
for (i in 0..r) sieve[i] = List.filled(r + 2, false) |
|||
for (i in 1..r) { |
|||
for (j in (i + 1)..(r + 1)) { |
|||
if (!sieve[i][j]) { |
|||
var f = BigRat.new(i, j) |
|||
var list = toEgyptian.call(f) |
|||
var listSize = list.count |
|||
if (listSize > maxSize) { |
|||
maxSize = listSize |
|||
maxSizeFracs.clear() |
|||
maxSizeFracs.add(f) |
|||
} else if (listSize == maxSize) { |
|||
maxSizeFracs.add(f) |
|||
} |
|||
var listDen = list[-1].den |
|||
if (listDen > maxDen) { |
|||
maxDen = listDen |
|||
maxDenFracs.clear() |
|||
maxDenFracs.add(f) |
|||
} else if (listDen == maxDen) { |
|||
maxDenFracs.add(f) |
|||
} |
|||
if (i < r / 2) { |
|||
var k = 2 |
|||
while (true) { |
|||
if (j * k > r + 1) break |
|||
sieve[i * k][j * k] = true |
|||
k = k + 1 |
|||
} |
|||
} |
|||
} |
|||
} |
|||
} |
|||
System.print(" largest number of items = %(maxSize)") |
|||
System.print(" fraction(s) with this number : %(maxSizeFracs)") |
|||
var md = maxDen.toString |
|||
System.write(" largest denominator = %(md.count) digits, ") |
|||
System.print("%(md[0...20])...%(md[-20..-1])") |
|||
System.print(" fraction(s) with this denominator : %(maxDenFracs)") |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
43/48 -> 1/2 + 1/3 + 1/16 |
|||
5/121 -> 1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795642093418846225 |
|||
2014/59 -> 34 + 1/8 + 1/95 + 1/14947 + 1/670223480 |
|||
For proper fractions with 1 or 2 digits: |
|||
largest number of items = 8 |
|||
fraction(s) with this number : [8/97, 44/53] |
|||
largest denominator = 150 digits, 57950458706754280171...62011424993909789665 |
|||
fraction(s) with this denominator : [8/97] |
|||
For proper fractions with 1, 2 or 3 digits: |
|||
largest number of items = 13 |
|||
fraction(s) with this number : [529/914, 641/796] |
|||
largest denominator = 2847 digits, 83901882683345018663...38431266995525592705 |
|||
fraction(s) with this denominator : [36/457, 529/914] |
|||
</pre> |
|||
=={{header|zkl}}== |
=={{header|zkl}}== |