Odd greedy expansion

Odd greedy expansion

In number theory, the odd greedy expansion problem concerns a method for forming Egyptian fractions in which all denominators are odd.

If a rational number x/y is a sum of odd unit fractions,

\frac{x}{y} = \sum\frac{1}{2a_i+1},

then y must be odd. Conversely, it is known that whenever y is odd, every fraction x/y has a representation of this type in which all the unit fractions are different from each other. For instance, such a representation can be found by replacing the fraction x/y by Ax/Ay where A is a number of the form 35×3i for a sufficiently large i, and then expanding Ax as a sum of divisors of Ay (Breusch 1954; Stewart 1954).

However, there is a simpler greedy algorithm that has successfully found Egyptian fractions in which all denominators are odd for all instances x/y (with odd y) on which it has been tested: let u be the least odd number that is greater than or equal to y/x, include the fraction 1/u in the expansion, and continue in the same way with the remaining fraction x/y - 1/u. This method is called the odd greedy algorithm and the expansions it creates are called odd greedy expansions.

Stein, Selfridge, Graham, and others have posed the question of whether the odd greedy algorithm terminates with a finite expansion for every x/y with y odd (Guy 1981). As of 2006, this question remains open.

Applying the odd greedy algorithm to a fraction with an even denominator produces an infinite series expansion. For instance Sylvester's sequence can be viewed as generated by the odd greedy expansion of 1/2.

Contents

Example

Let x/y = 4/23.

23/4 = 5 3/4; the next larger odd number is 7. So in the first step, we expand

4/23 = 1/7 + 5/161.

161/5 = 32 1/5; the next larger odd number is 33. So in the next step, we expand

4/23 = 1/7 + 1/33 + 4/5313.

5313/4 = 1328 1/4; the next larger odd number is 1329. So in the third step, we expand

4/23 = 1/7 + 1/33 + 1/1329 + 1/2353659.

Since the final term in this expansion is a unit fraction, the process terminates with this expansion as its result.

Fractions with long expansions

It is possible for the odd greedy algorithm to produce expansions that are shorter than the usual greedy expansion, with smaller denominators (Wagon 1991). For instance,

\frac{8}{77}=\frac{1}{10}+\frac{1}{257}+\frac{1}{197890}=\frac{1}{11}+\frac{1}{77},

where the left expansion is the greedy expansion and the right expansion is the odd greedy expansion. However, the odd greedy expansion is more typically long, with large denominators. For instance, as Wagon discovered (Guy 1998), the odd greedy expansion for 3/179 has 19 terms, the largest of which is approximately 1.415×10439491. Curiously, the numerators of the fractions to be expanded in each step of the algorithm form a sequence of consecutive integers:

3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 1.

A similar phenomenon occurs with other numbers, such as 5/5809 (an example found independently by K. S. Brown and David Bailey) which has a 31-term expansion. Although the denominators of this expansion are difficult to compute due to their enormous size, the numerator sequence may be found relatively efficiently using modular arithmetic. Nowakowski (1999) describes several additional examples of this type found by Broadhurst, and notes that K. S. Brown has described methods for finding fractions with arbitrarily long expansions.

References

  • Guy, Richard K. (1981). Unsolved Problems in Number Theory. Springer-Verlag. p. 88. ISBN 0-387-90593-6. 
  • Klee, Victor; Wagon, Stan (1991). Unsolved Problems in Elementary Geometry and Number Theory. Dolciani Mathematical Expositions, Mathematical Association of America. 
  • Wagon, Stan (1991). Mathematica in Action. W.H. Freeman. pp. 275–277. ISBN 0-7167-2202-X. 

External links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Greedy algorithm for Egyptian fractions — In mathematics, an Egyptian fraction is a representation of an irreducible fraction as a sum of unit fractions, as e.g. 5/6 = 1/2 + 1/3. As the name indicates, these representations have been used as long ago as ancient Egypt, but the first… …   Wikipedia

  • Egyptian fraction — An Egyptian fraction is the sum of distinct unit fractions, such as frac{1}{2}+ frac{1}{3}+ frac{1}{16}. That is, each fraction in the expression has a numerator equal to 1 and a denominator that is a positive integer, and all the denominators… …   Wikipedia

  • Sylvester's sequence — In number theory, Sylvester s sequence is a sequence of integers in which each member of the sequence is the product of the previous members, plus one. The first few terms of the sequence are::2, 3, 7, 43, 1807, 3263443, 10650056950807,… …   Wikipedia

  • List of mathematics articles (O) — NOTOC O O minimal theory O Nan group O(n) Obelus Oberwolfach Prize Object of the mind Object theory Oblate spheroid Oblate spheroidal coordinates Oblique projection Oblique reflection Observability Observability Gramian Observable subgroup… …   Wikipedia

  • ancient Greek civilization — ▪ historical region, Eurasia Introduction       the period following Mycenaean civilization, which ended in about 1200 BC, to the death of Alexander the Great, in 323 BC. It was a period of political, philosophical, artistic, and scientific… …   Universalium

  • List of species in Magic: The Gathering — Magic: the Gathering is a collectible card game set in a richly detailed fictional world. The Multiverse of Dominia in which it takes place is host to a vast number of individual universes known as planes, from the varied classical environments… …   Wikipedia

  • List of .hack characters — Contents 1 Main characters 1.1 The World 1.2 The World R:2 1.3 The World R:X 1.3.1 Schicksal …   Wikipedia

  • Erdős–Straus conjecture — The Erdős–Straus conjecture states that for all integers n ≥ 2, the rational number 4/ n can be expressed as the sum of three unit fractions. That is, there exist positive integers x , y , and z such that :frac4n = frac1x + frac1y + frac1z.The… …   Wikipedia

  • Italy — /it l ee/, n. a republic in S Europe, comprising a peninsula S of the Alps, and Sicily, Sardinia, Elba, and other smaller islands: a kingdom 1870 1946. 57,534,088; 116,294 sq. mi. (301,200 sq. km). Cap.: Rome. Italian, Italia. * * * Italy… …   Universalium

  • List of Star Wars species (K–O) — Contents 1 Kaleesh 2 Kaminoan 3 Kel Dor 4 Keshiri …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”