Английская Википедия:Greedy algorithm for Egyptian fractions

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Short description In mathematics, the greedy algorithm for Egyptian fractions is a greedy algorithm, first described by Fibonacci, for transforming rational numbers into Egyptian fractions. An Egyptian fraction is a representation of an irreducible fraction as a sum of distinct unit fractions, such as Шаблон:Nowrap. As the name indicates, these representations have been used as long ago as ancient Egypt, but the first published systematic method for constructing such expansions was described in 1202 in the Liber Abaci of Leonardo of Pisa (Fibonacci).Шаблон:Sfn It is called a greedy algorithm because at each step the algorithm chooses greedily the largest possible unit fraction that can be used in any representation of the remaining fraction.

Fibonacci actually lists several different methods for constructing Egyptian fraction representations.[1] He includes the greedy method as a last resort for situations when several simpler methods fail; see Egyptian fraction for a more detailed listing of these methods. As Salzer (1948) details, the greedy method, and extensions of it for the approximation of irrational numbers, have been rediscovered several times by modern mathematicians, earliest and most notably by Шаблон:Harvs[2] A closely related expansion method that produces closer approximations at each step by allowing some unit fractions in the sum to be negative dates back to Шаблон:Harvtxt.

The expansion produced by this method for a number <math>x</math> is called the greedy Egyptian expansion, Sylvester expansion, or Fibonacci–Sylvester expansion of <math>x</math>. However, the term Fibonacci expansion usually refers, not to this method, but to representation of integers as sums of Fibonacci numbers.

Algorithm and examples

Fibonacci's algorithm expands the fraction <math>x/y</math> to be represented, by repeatedly performing the replacement <math display=block>\frac{x}{y}=\frac{1}{\left\lceil \frac y x \right\rceil}+\frac{(-y)\bmod x}{y\left\lceil \frac y x \right\rceil}</math> (simplifying the second term in this replacement as necessary). For instance: <math display=block>\frac{7}{15}=\frac{1}{3}+\frac{2}{15}=\frac{1}{3}+\frac{1}{8}+\frac{1}{120}.</math> in this expansion, the denominator 3 of the first unit fraction is the result of rounding Шаблон:Sfrac up to the next larger integer, and the remaining fraction Шаблон:Sfrac is the result of simplifying Шаблон:Sfrac = Шаблон:Sfrac. The denominator of the second unit fraction, 8, is the result of rounding Шаблон:Sfrac up to the next larger integer, and the remaining fraction Шаблон:Sfrac is what is left from Шаблон:Sfrac after subtracting both Шаблон:Sfrac and Шаблон:Sfrac.

As each expansion step reduces the numerator of the remaining fraction to be expanded, this method always terminates with a finite expansion; however, compared to ancient Egyptian expansions or to more modern methods, this method may produce expansions that are quite long, with large denominators. For instance, this method expands <math display=block>\frac{5}{121}=\frac{1}{25}+\frac{1}{757}+\frac{1}{763\,309}+\frac{1}{873\,960\,180\,913}+\frac{1}{1\,527\,612\,795\,642\,093\,418\,846\,225},</math> while other methods lead to the much better expansion <math display=block>\frac{5}{121}=\frac{1}{33}+\frac{1}{121}+\frac{1}{363}.</math> Шаблон:Harvtxt suggests an even more badly-behaved example, Шаблон:Sfrac. The greedy method leads to an expansion with ten terms, the last of which has over 500 digits in its denominator; however, Шаблон:Sfrac has a much shorter non-greedy representation, Шаблон:Nowrap.

Sylvester's sequence and closest approximation

Sylvester's sequence 2, 3, 7, 43, 1807, ... (Шаблон:OEIS2C) can be viewed as generated by an infinite greedy expansion of this type for the number 1, where at each step we choose the denominator Шаблон:Nowrap instead of Шаблон:Nowrap. Truncating this sequence to k terms and forming the corresponding Egyptian fraction, e.g. (for k = 4) <math display=block>\frac12+\frac13+\frac17+\frac1{43}=\frac{1805}{1806}</math> results in the closest possible underestimate of 1 by any k-term Egyptian fraction.[3] That is, for example, any Egyptian fraction for a number in the open interval (Шаблон:Sfrac, 1) requires at least five terms. Шаблон:Harvtxt describes an application of these closest-approximation results in lower-bounding the number of divisors of a perfect number, while Шаблон:Harvtxt describes applications in group theory.

Maximum-length expansions and congruence conditions

Any fraction Шаблон:Sfrac requires at most x terms in its greedy expansion. Шаблон:Harvtxt and Шаблон:Harvtxt examine the conditions under which the greedy method produces an expansion of Шаблон:Sfrac with exactly x terms; these can be described in terms of congruence conditions on y.

More generally the sequence of fractions Шаблон:Sfrac that have x-term greedy expansions and that have the smallest possible denominator y for each x is Шаблон:Bi

Approximation of polynomial roots

Шаблон:Harvtxt and Шаблон:Harvtxt describe a method of finding an accurate approximation for the roots of a polynomial based on the greedy method. Their algorithm computes the greedy expansion of a root; at each step in this expansion it maintains an auxiliary polynomial that has as its root the remaining fraction to be expanded. Consider as an example applying this method to find the greedy expansion of the golden ratio, one of the two solutions of the polynomial equation Шаблон:Nowrap. The algorithm of Stratemeyer and Salzer performs the following sequence of steps:

  1. Since Шаблон:Nowrap for x = 1, and Шаблон:Nowrap for all Шаблон:Nowrap, there must be a root of P0(x) between 1 and 2. That is, the first term of the greedy expansion of the golden ratio is Шаблон:Sfrac. If x1 is the remaining fraction after the first step of the greedy expansion, it satisfies the equation Шаблон:Nowrap, which can be expanded as Шаблон:Nowrap.
  2. Since Шаблон:Nowrap for x = Шаблон:Sfrac, and Шаблон:Nowrap for all Шаблон:Nowrap, the root of P1 lies between Шаблон:Sfrac and 1, and the first term in its greedy expansion (the second term in the greedy expansion for the golden ratio) is Шаблон:Sfrac. If x2 is the remaining fraction after this step of the greedy expansion, it satisfies the equation Шаблон:Nowrap, which can be expanded as Шаблон:Nowrap.
  3. Since Шаблон:Nowrap for x = Шаблон:Sfrac, and Шаблон:Nowrap for all Шаблон:Nowrap, the next term in the greedy expansion is Шаблон:Sfrac. If x3 is the remaining fraction after this step of the greedy expansion, it satisfies the equation Шаблон:Nowrap, which can again be expanded as a polynomial equation with integer coefficients, Шаблон:Nowrap.

Continuing this approximation process eventually produces the greedy expansion for the golden ratio, Шаблон:Bi

Other integer sequences

The length, minimum denominator, and maximum denominator of the greedy expansion for all fractions with small numerators and denominators can be found in the On-Line Encyclopedia of Integer Sequences as sequences Шаблон:OEIS2C, Шаблон:OEIS2C, and Шаблон:OEIS2C, respectively. In addition, the greedy expansion of any irrational number leads to an infinite increasing sequence of integers, and the OEIS contains expansions of several well known constants. Some additional entries in the OEIS, though not labeled as being produced by the greedy algorithm, appear to be of the same type.

Related expansions

In general, if one wants an Egyptian fraction expansion in which the denominators are constrained in some way, it is possible to define a greedy algorithm in which at each step one chooses the expansion <math display=block>\frac{x}{y}=\frac{1}{d}+\frac{xd-y}{yd},</math> where <math>d</math> is chosen, among all possible values satisfying the constraints, as small as possible such that <math>xd > y</math> and such that <math>d</math> is distinct from all previously chosen denominators. Examples of methods defined in this way include Engel expansion, in which each successive denominator must be a multiple of the previous one, and odd greedy expansion, in which all denominators are constrained to be odd numbers.

However, it may be difficult to determine whether an algorithm of this type can always succeed in finding a finite expansion. In particular, it is unknown whether the odd greedy expansion terminates with a finite expansion for all fractions <math>x/y</math> for which <math>y</math> is odd, although it is possible to find finite odd expansions for these fractions by non-greedy methods.

Notes

Шаблон:Reflist

References

Шаблон:Refbegin

Шаблон:Refend

Шаблон:Fibonacci

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Harvnb, chapter II.7
  2. ↑ See for instance Шаблон:Harvtxt and Шаблон:Harvtxt.
  3. ↑ Шаблон:Harvnb; Шаблон:Harvnb
Источник — http://wikihandbk.com/ruwiki/index.php?title=Английская_Википедия:Greedy_algorithm_for_Egyptian_fractions&oldid=15027675