Essays/Egyptian Fraction
< Essays
Jump to navigation
Jump to search
An Egyptian fraction is a sum of distinct unit fractions, reciprocals of positive integers. An Egyptian fraction of x where (0<x)*.x<:1 can be computed using a greedy algorithm discovered by Leonardo Pisano Fibonacci in 1202:
ef=: 3 : 'if. (=<.) %y do. y else. y (] , ef@-) %1+<.%y end.' ef 19r20 1r2 1r3 1r9 1r180 +/ ef 19r20 19r20
ef can produce some large numbers:
v=: ef 11r199
+/ v
11r199
# v
11
5{. v
1r19 1r379 1r159223 1r28520799973 1r929641178371338400861
#@":"0 % v
2 3 6 11 21 43 85 169 337 674 1348
That is, the last denominator in v has 1348 decimal digits. In contrast, another Egyptian fraction for 11r199 is:
+/ 1r20 1r199 1r3980 11r199
See also
Contributed by Roger Hui.