Odd greedy expansion
In number theory, the odd greedy expansion problem asks whether a greedy algorithm for finding Egyptian fractions with odd denominators always succeeds. , it remains unsolved. Description. An Egyptian fraction represents a given rational number as a sum of distinct unit fractions. If a rational number formula_1 is a sum of unit fractions with odd denominators, then formula_3 must be odd. Conversely, every fraction formula_1 with formula_3 odd can be represented as a sum of distinct odd unit fractions. One method of finding such a representation replaces formula_1 by formula_7 where formula_8 for a sufficiently large formula_9, and  then expands formula_10 as a sum of distinct divisors of formula_11. However, a simpler greedy algorithm has successfully found Egyptian fractions in which all denominators are odd for all instances formula_1 (with odd formula_3) on which it has been tested: let formula_14 be the least odd number that is greater than or equal to formula_15, include the fraction formula_16 in the expansion, and continue in the same way (avoiding repeated uses of the same unit fraction) with the remaining fraction formula_17. 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 formula_1 with formula_3 odd. , this question remains open. Example. Let formula_1 = 4/23. 23/4 = 5; the next larger odd number is 7. So the first step expands 161/5 = 32; the next larger odd number is 33. So the next step expands 5313/4 = 1328; the next larger odd number is 1329. So the third step expands 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. For instance, formula_21 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, the odd greedy expansion for 3/179 has 19 terms, the largest of which is approximately 1.415×10. Curiously, the numerators of the fractions to be expanded in each step of the algorithm form a sequence of consecutive integers: 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 27-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. 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. On even denominators. The odd greedy algorithm cannot terminate when given a fraction with an even denominator, because these fractions do  not have finite representations with odd denominators. Therefore, in this case, it produces an infinite series expansion of its input. For instance Sylvester's sequence can be viewed as generated by the odd greedy expansion of 1/2.