Greedy algorithm for Egyptian fractions: Difference between revisions

Content added Content deleted
m (→‎{{header|zkl}}: fiddle about)
(Restored visibility of task description formulae - lost to most browsers in under-tested cosmetic edits of 02:50, 16 August 2016)
Line 1: Line 1:
{{draft task}}
{{draft task}}


An   [[wp:Egyptian fraction|Egyptian fraction]]   is the sum of distinct unit fractions such as:
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></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 &nbsp; <big> '''1''' </big> &nbsp; (unity) &nbsp; and a denominator that is a positive integer, and all the denominators are distinct &nbsp; (i.e., no repetitions).
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).


Fibonacci's &nbsp; [[wp:Greedy algorithm for Egyptian fractions|Greedy algorithm for Egyptian fractions]] &nbsp; expands the fraction &nbsp; <big><big><math> \tfrac{x}{y} </math></big></big> &nbsp; to be represented by repeatedly performing the replacement
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><big><math> \frac{x}{y} = \frac{1}{\lceil y/x\rceil} + \frac{(-y)\!\!\!\!\mod x}{y\lceil y/x\rceil} </math></big></big>
: <math> \frac{x}{y} = \frac{1}{\lceil y/x\rceil} + \frac{(-y)\!\!\!\!\mod x}{y\lceil y/x\rceil} </math>

⚫
(simplifying the 2<sup>nd</sup> term in this replacement as necessary, and where &nbsp; <big><math> \lceil x \rceil </math></big> &nbsp; is the ''ceiling'' function).


⚫
(simplifying the 2<sup>nd</sup> term in this replacement as necessary, and where <math> \lceil x \rceil </math> 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. &nbsp; Having all the programming examples use the Fibonacci greedy algorithm will make for easier comparison and compatible results.
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. &nbsp; Having all the programming examples use the Fibonacci greedy algorithm will make for easier comparison and compatible results.
-->
-->


[[wp:Fraction (mathematics)#Simple.2C_common.2C_or_vulgar_fractions|Proper and improper fractions]] &nbsp; must be able to be expressed.
[[wp:Fraction (mathematics)#Simple.2C_common.2C_or_vulgar_fractions|Proper and improper fractions]] must be able to be expressed.


Proper fractions &nbsp; are of the form &nbsp; <big><big><math>\tfrac{a}{b}</math></big></big> &nbsp; where &nbsp; <big><big><math> a </math></big></big> &nbsp; and &nbsp; <big><big><math> b </math></big></big> &nbsp; are positive integers, such that &nbsp; <big><big><math> a < b, </math></big></big> &nbsp; and
Proper fractions &nbsp; are of the form <math>\tfrac{a}{b}</math> where <math>a</math> and <math>b</math> are positive integers, such that <math>a < b</math>, and
<br>improper fractions are of the form &nbsp; <big><big><math> \tfrac{a}{b} </math></big></big> &nbsp; where &nbsp; <big><big><math> a </math></big></big> &nbsp; and &nbsp; <big><big><math> b </math></big></big> &nbsp; are positive integers, such that &nbsp; <big> <span style="font-family:times">''a'' ≥ ''b''</span></big>.
<br>improper fractions are of the form <math>\tfrac{a}{b}</math> where <math>a</math> and <math>b</math> are positive integers, such that <span style="font-family:times">''a'' ≥ ''b''</span>.


(See the &nbsp; [[#REXX|REXX programming example]] &nbsp; to view one method of expressing the whole number part of an improper fraction.)
(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 &nbsp; <big><big><tt> [''n''].</tt></big></big>
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:
;Task requirements:
* &nbsp; show the Egyptian fractions for: &nbsp; <big><math> \tfrac{43}{48} </math></big> &nbsp; and &nbsp; <big><math> \tfrac{5}{121} </math></big> &nbsp; and &nbsp; <big><math> \tfrac{2014}{59} </math></big>
* show the Egyptian fractions for: <math> \tfrac{43}{48} </math> and <math> \tfrac{5}{121} </math> and <math> \tfrac{2014}{59} </math>
* &nbsp; for all proper fractions, &nbsp; <big><math> \tfrac{a}{b} </math></big> &nbsp; where &nbsp; <big><math> a </math></big> &nbsp; and &nbsp; <big><math> b </math></big> &nbsp; are positive one-or two-digit (decimal) integers, find and show an Egyptian fraction that has:
* 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:
::* &nbsp; the largest number of terms,
:* the largest number of terms,
::* &nbsp; the largest denominator.
:* the largest denominator.
* &nbsp; for all one-, two-, and three-digit integers (extra credit), find and show (as above).
* for all one-, two-, and three-digit integers (extra credit), find and show (as above).



;Also see:
;Also see:
* &nbsp; Wolfram MathWorld&trade; entry: [http://mathworld.wolfram.com/EgyptianFraction.html Egyptian fraction]
* Wolfram MathWorld&trade; entry: [http://mathworld.wolfram.com/EgyptianFraction.html Egyptian fraction]
<br><br>
<br><br>


Retrieved from "https://rosettacode.org/wiki/Greedy_algorithm_for_Egyptian_fractions"