“Odd greedy expansion”的意思、由来-开放百科全书

词条

Odd greedy expansion

释义

Example
Fractions with long expansions
Notes
References
External links

{{unsolved|mathematics|Does every rational number with an odd denominator have an 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,

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×3ⁱ for a sufficiently large i, and then expanding Ax as a sum of divisors of Ay.^[1]

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.{{sfnp|Guy|1981}} {{As of|2016}}, 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.

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.{{sfnp|Wagon|1991}} For instance,

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,{{sfnp|Guy|1998}} 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:

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. {{harvtxt|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.

Notes

1. ^{{harvtxt|Breusch|1954}}; {{harvtxt|Stewart|1954}}.

References

{{citation

| last = Breusch | first = R. | authorlink = Robert Breusch
| title = A special case of Egyptian fractions, solution to advanced problem 4512
| journal = American Mathematical Monthly
| volume = 61
| year = 1954
| pages = 200–201
| doi = 10.2307/2307234}}

{{citation

| last = Guy | first = Richard K. | authorlink = Richard K. Guy
| title = Unsolved Problems in Number Theory
| year = 1981
| publisher = Springer-Verlag
| isbn = 0-387-90593-6
| page = 88}}

{{citation

| last = Guy | first = Richard K. | authorlink = Richard K. Guy
| title = Nothing's new in number theory?
| journal = American Mathematical Monthly
| year = 1998
| volume = 105
| issue = 10
| pages = 951–954
| doi = 10.2307/2589289
| jstor = 2589289}}

{{citation

| last1 = Klee | first1 = Victor | author1-link = Victor Klee
| last2 = Wagon | first2 = Stan | author2-link = Stan Wagon
| publisher = Mathematical Association of America
| series = Dolciani Mathematical Expositions
| title = Unsolved Problems in Elementary Geometry and Number Theory
| year = 1991}}

{{citation

| last = Nowakowski | first = Richard
| doi = 10.2307/2589753
| issue = 10
| journal = American Mathematical Monthly
| jstor = 2589753
| pages = 959–962
| title = Unsolved problems, 1969–1999
| volume = 106
| year = 1999}}

{{citation

| last = Stewart | first = B. M. | authorlink = Bonnie Stewart
| doi = 10.2307/2372651
| issue = 4
| journal = American Journal of Mathematics
| jstor = 2372651
| mr = 0064800
| pages = 779–785
| title = Sums of distinct divisors
| volume = 76
| year = 1954}}

{{citation

| last = Wagon | first = Stan | author-link = Stan Wagon
| isbn = 0-7167-2202-X
| pages = 275–277
| publisher = W.H. Freeman
| title = Mathematica in Action
| year = 1991}}

External links

MathPages - Odd-Greedy Unit Fraction Expansions, K. S. Brown

2 : Egyptian fractions|Unsolved problems in mathematics

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。