43 lines
3.2 KiB
Text
43 lines
3.2 KiB
Text
An [[wp:Egyptian fraction|<u>Egyptian fraction</u>]] is the sum of distinct unit fractions such as:
|
|
|
|
:::: <big><big> <math> \tfrac{1}{2} + \tfrac{1}{3} + \tfrac{1}{16} \,(= \tfrac{43}{48})</math> </big></big>
|
|
|
|
Each fraction in the expression has a numerator equal to '''1''' (unity) and a denominator that is a positive integer, and all the denominators are distinct (i.e., no repetitions).
|
|
|
|
Fibonacci's [[wp:Greedy algorithm for Egyptian fractions|<u>Greedy algorithm for Egyptian fractions</u>]] expands the fraction <big> <math> \tfrac{x}{y} </math> </big> to be represented by repeatedly performing the replacement
|
|
|
|
:::: <big> <math> \frac{x}{y} = \frac{1}{\lceil y/x\rceil} + \frac{(-y)\!\!\!\!\mod x}{y\lceil y/x\rceil} </math> </big>
|
|
|
|
|
|
(simplifying the 2<sup>nd</sup> term in this replacement as necessary, and where <big> <math> \lceil x \rceil </math> </big> is the ''ceiling'' function).
|
|
|
|
<!--
|
|
This Rosetta Code task will be using the Fibonacci greedy algorithm for computing Egyptian fractions; however, if different method is used instead, please note which method is being employed. Having all the programming examples use the Fibonacci greedy algorithm will make for easier comparison and compatible results.
|
|
-->
|
|
|
|
For this task, [[wp:Fraction (mathematics)#Simple.2C_common.2C_or_vulgar_fractions|<u>Proper and improper fractions</u>]] must be able to be expressed.
|
|
|
|
|
|
Proper fractions are of the form <big> <math>\tfrac{a}{b}</math> </big> where <big> <math>a</math> </big> and <big> <math>b</math> </big> are positive integers, such that <big> <math>a < b</math></big>, and
|
|
|
|
improper fractions are of the form <big> <math>\tfrac{a}{b}</math> </big> where <big> <math>a</math> </big> and <big> <math>b</math> </big> are positive integers, such that <big> <span style="font-family:times">''a'' ≥ ''b''</span></big>.
|
|
|
|
|
|
(See the [[#REXX|REXX programming example]] to view one method of expressing the whole number part of an improper fraction.)
|
|
|
|
For improper fractions, the integer part of any improper fraction should be first isolated and shown preceding the Egyptian unit fractions, and be surrounded by square brackets <tt>[''n'']</tt>.
|
|
|
|
|
|
;Task requirements:
|
|
* show the Egyptian fractions for: <math> \tfrac{43}{48} </math> and <math> \tfrac{5}{121} </math> and <math> \tfrac{2014}{59} </math>
|
|
* for all proper fractions, <big> <math>\tfrac{a}{b}</math> </big> where <big> <math>a</math> </big> and <big> <math>b</math> </big> are positive one-or two-digit (decimal) integers, find and show an Egyptian fraction that has:
|
|
::* the largest number of terms,
|
|
::* the largest denominator.
|
|
* for all one-, two-, and three-digit integers, find and show (as above). {extra credit}
|
|
|
|
|
|
;Also see:
|
|
* Wolfram MathWorld™ entry: [http://mathworld.wolfram.com/EgyptianFraction.html Egyptian fraction]
|
|
* Numberphile YouTube video: [https://youtu.be/aVUUbNbQkbQ Egyptian Fractions and the Greedy Algorithm]
|
|
<br><br>
|
|
|