HP 71B, TI 84 Plus CE: Egyptian Fractions to Unit Fractions by the Greedy Algorithm
Introduction
An Egyptian fraction consists of a sum of unit fractions. A unit fraction is a fraction with 1 in its numerator and a positive integer in its denominator.
Yesterday, we calculated the Egyptian fraction given unit fractions, full simplified. Today, we will attempt the reverse process, breaking down an Egyptian fraction into a sum of unit fractions.
N/D = 1/A1 + 1/A2 + 1/A3 + 1/A4 + ....
The Algorithm
The Greedy Algorithm is used.
The Greedy Algorithm attempts to start the expansion by using the division of ceiling(D/N) = int(D/N) + 1. Please be aware that this may not be the fastest or more efficient way.
We also have the problem of a lot of calculators inability to display long integers, that is longer than 10 (usually) before switching to scientific notation mode. In order to accommodate for memory and the calculator's ability to display integers, I set the algorithm to stop should the denominator for the next step exceed 10^8. In that case, the remainder fraction is displayed.
TI-84 Plus CE Program EGYPTUNT
"2022-09-04 EWS"
Disp "EGYPT>SUM UNIT FRACS"
Input "NUM? ",N
Input "DEN? ",D
N→M:D→C
Disp "SUM: ":Wait .5
While M≠1
int(C/M)+1→B
Disp "1/"+toString(B)
Pause
M*B-C→M
B*C→C
If C>1E8:Goto 2
End
Disp "1/"+toString(C)
Stop
Lbl 2
Disp "REMAIN:"
Disp toString(M)+"/"+toString(C)
* This assumes your TI-84 Plus CE is at least has the 5.5 operating system.
HP 71B Program EGYPTUNT
100 DISP "EGYPT>SUM UNIT FRACS" @ WAIT .5
105 DESTROY N,D,C,M
110 INPUT "NUM? ";N
115 INPUT "DEN? ";D
120 M=N @ C=D
125 DISP "SUM=" @ WAIT .5
200 B=INT(C/M)+1
205 DISP "1/"&STR$(B) @ PAUSE
210 M=M*B-C @ C=C*B
215 IF C>10^8 THEN 400
220 IF M#1 THEN 200
300 DISP "1/"&STR$(C)
305 STOP
400 DISP "REMAIN: " @ WAIT .5
405 DISP STR$(M)&"/"&STR$(C)
410 STOP
Examples:
6/7
NUM = 6
DEN = 7
Results: 1/2, 1/3, 1/42
6/7 = 1/2 + 1/3 + 1/42
181/360
NUM = 181
DEN = 360
Results: 1/2, 1/361, 1/129961, REMAIN: 2/33779463120
Note: Please be aware that this Greedy Algorithm is only one approach and just because we get a REMAIN message does not conclude that the fraction cannot be broken into a sum of unit fractions. For example: 181/360 = 1/5 + 1/8 + 1/9 + 1/15
See the source below for more information.
"Greedy algorithm for Egyptian fractions" Wikipedia. Edited December 10, 2021. Last Accessed September 4, 2022. https://en.wikipedia.org/wiki/Greedy_algorithm_for_Egyptian_fractions
Eddie
Halloween is just around the corner!
All original content copyright, © 2011-2022. Edward Shore. Unauthorized use and/or unauthorized distribution for commercial purposes without express and written permission from the author is strictly prohibited. This blog entry may be distributed for noncommercial purposes, provided that full credit is given to the author.