Anonymous user
Greedy algorithm for Egyptian fractions: Difference between revisions
Greedy algorithm for Egyptian fractions (view source)
Revision as of 23:45, 14 November 2018
, 5 years agore-introduced original whitespace, used bigger font for the formulas.
(Add Factor example) |
m (re-introduced original whitespace, used bigger font for the formulas.) |
||
Line 3:
An [[wp:Egyptian fraction|Egyptian fraction]] 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>
Each fraction in the expression has a numerator equal to <math>1</math> and a denominator that is a positive integer, and all the denominators are distinct (i.e., no repetitions).
Line 9:
Fibonacci's [[wp:Greedy algorithm for Egyptian fractions|Greedy algorithm for Egyptian fractions]] expands the fraction <math> \tfrac{x}{y} </math> 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 <math> \lceil x \rceil </math> is the ''ceiling'' function).
Line 24 ⟶ 25:
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, <math>\tfrac{a}{b}</math> where <math>a</math> and <math>b</math> 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 (extra credit), find and show (as above).
;Also see:
* Wolfram MathWorld™ entry: [http://mathworld.wolfram.com/EgyptianFraction.html Egyptian fraction]
<br><br>
| |||