Sunday, October 23, 2022

HP 71B, TI 84 Plus CE: Egyptian Fractions to Unit Fractions by the Greedy Algorithm

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.