An algorithm used to recursively construct a Set of objects from the smallest possible constituent parts.
Given a Set of Integers (, , ..., ) with
, a greedy
algorithm can be used to find a Vector of coefficients (, , ..., ) such that
For example, McNugget Numbers are numbers which are representable using only
. Taking and applying the algorithm iteratively gives the sequence (0, 0, 3), (0, 2, 2), (2, 1, 2), (3,
0, 2), (1, 4, 1), at which point . 62 is therefore a McNugget Number with
If any Integer can be represented with or 1 using a sequence (, , ...), then this sequence is called a Complete Sequence.
A greedy algorithm can also be used to break down arbitrary fractions into Unit Fractions in a finite number
of steps. For a Fraction , find the least Integer such that , i.e.,
Paul Erdös and E. G. Strays have conjectured that the Diophantine Equation
See also Complete Sequence, Integer Relation, Levine-O'Sullivan Greedy Algorithm, McNugget Number, Reverse Greedy Algorithm, Square Number, Sylvester's Sequence, Unit Fraction
© 1996-9 Eric W. Weisstein