Greedy algorithm for Egyptian fractions: Difference between revisions
Greedy algorithm for Egyptian fractions (view source)
Revision as of 08:44, 10 June 2023
, 11 months agoadd RPL
(add RPL) |
|||
Line 2,928:
largest denominator in the Egyptian fractions is 2847 digits is for 36/457
</pre>
=={{header|RPL}}==
<code>GCD</code> is defined at [[Greatest common divisor#RPL|Greatest common divisor]]
{{works with|Halcyon Calc|4.2.7}}
{| class="wikitable" ≪
! RPL code
! Comment
|-
|
≪
DUP IM LAST RE / CEIL
SWAP RE LAST IM DUP NEG ROT MOD
SWAP 3 PICK *
DUP2 <span style="color:blue">GCD</span> ROT OVER / ROT ROT / R→C
≫ '<span style="color:blue">SPLIT</span>' STO
≪
DUP 3 EXGET SWAP 1 EXGET
'''IF''' DUP2 > '''THEN'''
SWAP OVER MOD LAST / IP SWAP ROT
'''ELSE''' 0 ROT ROT '''END'''
R→C
'''WHILE''' DUP RE '''REPEAT'''
<span style="color:blue">SPLIT</span>
"'1/" ROT →STR + "'" + STR→
ROT SWAP + SWAP
'''END'''
≫ '<span style="color:blue">EGYPF</span>' STO
|
<span style="color:blue">SPLIT</span> ''( (x1,y1) → n1 (x2,y2) ) ''
n1 = ceil(y1/x1)
x2 = mod(-y1,x1)
y2 = n1*y1
simplify x2/y2
<span style="color:blue">EGYPF</span> ''( 'x/y' → 'sum_of_Egyptian_fractions') ''
put x and y in stack
if x > y
first term of sum is x//y and x = mod(x,y)
else first term is 0
convert to complex to ease handling in stack
loop while x<sub>k</sub> ≠ 0
get n<sub>k</sub> and (x<sub>k</sub>, y<sub>k</sub>)
convert n<sub>k</sub> into '1/n<sub>k</sub>'
add '1/n<sub>k</sub>' to the sum
end loop
return sum
|}
'43/48' <span style="color:blue">EGYPF</span>
'5/121' <span style="color:blue">EGYPF</span>
'2014/59' <span style="color:blue">EGYPF</span>
{{out}}
<pre>
3: 'INV(2)+INV(3)+INV(16)'
2: 'INV(25)+INV(757)+INV(763309)+INV(873960180913)+INV(1.52761279564E+24)'
1: '34+INV(8)+INV(95)+INV(14947)+INV(670223480)'
</pre>
In algebraic expressions, RPL automatically replaces <code>1/n</code> by <code>INV(n)</code>
=={{header|Ruby}}==
| |||