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 RogerHui.

Essays/Egyptian Fraction (last edited 2008-12-08 10:45:34 by )