## Greedy Algorithm

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

 (1)

where is the Dot Product, for some given Integer . This can be accomplished by letting for , ..., and setting
 (2)

Now define the difference between the representation and as
 (3)

If at any step, a representation has been found. Otherwise, decrement the Nonzero term with least , set all for , and build up the remaining terms from
 (4)

for , ..., 1 until or all possibilities have been exhausted.

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

 (5)

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

 (6)

where is the Ceiling Function. Then find the least Integer such that . Iterate until there is no remainder. The Algorithm gives two or fewer terms for and , three or fewer terms for , and four or fewer for .

Paul Erdös and E. G. Strays have conjectured that the Diophantine Equation

 (7)

always can be solved, and W. Sierpinski conjectured that
 (8)

can be solved.

See also Complete Sequence, Integer Relation, Levine-O'Sullivan Greedy Algorithm, McNugget Number, Reverse Greedy Algorithm, Square Number, Sylvester's Sequence, Unit Fraction