Suppose we want to write the simple fraction 2/3 as a sum of unit fractions with distinct odd denominators. If we apply the "greedy algorithm", which consists of taking the largest qualifying unit fraction at each stage, we would begin with the term 1/3, leaving a remainder of 1/3. Since we require distinct denominators we can't use 1/3 for our second term, so we go on to the next largest odd unit fraction, which is 1/5. This leaves a remainder of 2/15, and the largest odd unit fraction less than 2/15 is 1/9, so that is our third term, leaving a remainder of exactly 1/45. So,the odd greedy expansion of 2/3 terminates after four steps, giving the result 2/3 = 1/3 + 1/5 + 1/9 + 1/45 The non-zero remainders we encountered during this process were 1/3, 2/15, and 1/45, with the numerators 1, 2, 1. There are some interesting unsolved problems related to odd greedy expansions. One open question is whether every fraction is guaranteed to terminate in a finite number of steps. This is not a trivial question, as shown by the odd greedy expansion of 1 (not using 1/1 on the first step). The result is 1 = 1/3 + 1/5 + 1/7 + 1/9 + 1/11 + 1/13 + 1/23 + 1/721 + 1/979007 + 1/661211444787 + ... It isn't known whether this eventually terminates. Incidentally, if we restrict ourselves to prime denominators we have 1 = 1/2 + 1/3 + 1/7 + 1/43 + 1/1811 + 1/654149 + ... Most fractions terminate quickly under the application of the odd greedy algorithm, but some require quite a large number of terms. For example, if the fraction 3/179 is converted into a sum of unit fractions with odd denominators using the greedy algorithm, it takes 19 terms. Also, the numerators of the sequence of remainders is 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 2, 3, 4, 1 Of course, if we don't require the use of the greedy algorithm, then the fraction 3/179 has the 3-term expansion with odd denominators 1/63 + 1/1611 + 1/3759, and conversely if allow both odd and even denominators then the greedy algorithm yields the 2-term expansion 1/60 + 1/10740. It is only the simultaneous imposition of BOTH requirements (odd AND greedy) that leads to the unusually lengthy expansion. Note also that the numerators of successive terms are consecutive integers from 3 to 17. (This raises the question of whether you could "construct" examples by working backwards from a given sequence of remainders.) In general, if we have a fraction N/D we can generate an expansion N 1 1 1 1 --- = ---- + ---- + ---- + ---- + ... D d[0] d[1] d[2] d[3] that is quadratically convergent (i.e., the number of correct digits roughly doubles with each term) using the recurrence (N+k) d[k+1] = (N+k-1) d[k]^2 - (N+k) d[k] + (N+k+1) with the initial value d[0] = 1 + (D+1)/N. We can re-write this recurrence in the form d[k]^2 - 1 d[k+1] = d[k]^2 - d[k] + 1 - ---------- (1) N+k Of course this doesn't guarantee that the values of d[j] are necessarily integers. To make d[0] an integer we must have D=-1 (mod N). Thereafter on the kth step we must have d[k]^2 - 1 divisible by (N+k), which implies that d[k] = +1 or -1 (mod N+k). Taking the fraction 5/179 as an example, we have N=5 and D=179, which gives d[0] = 37 d[1] = 1105 d[2] = 1045489 d[3] = 956415297493 d[4] = 813093530024486866555885 d[5] = 2975044898554565064901765456700565614513893820093/5 This gives a unit fraction expansion up until the denominator d[5], which is not an integer because d[4] = 4 (mod 9), so it's not congruent to +1 or -1 (mod N+k). As a result, the sequence of remainders is 6, 7, 8, 9, 2,... The numerator of N/D - 1/d[0] - 1/d[1] - 1/d[2] - 1/d[3] - 1/d[4] should be 10, but d[4] happens to be divisible by 5, so the reduced numerator is 2. As a result the recurrence stops giving integers, because it's based on the assumption that the remainders increase by 1 at each step. Of course, we can start the recurrence over again with this new value of N/D. For another example, consider again the fraction 3/179. In this case the recurrence formula (1) gives d[0] = 61 d[1] = 2731 d[2] = 5963959 d[3] = 29640666497443 d[4] = 753059237496518829212535343 d[5] = 496210938281483556785833636950652507016084391058576351 and so on Recurrence (1) with the initial value d[0]=61 gives integer values for a long time, up to 19 terms. The factorizations of d[k]-1 are somewhat cumulative, as shown below d[0]-1 = (2)(2)(3) (5) d[1]-1 = (2) (3) (5)(7) (13) d[2]-1 = (2) (3)(3) (7)(11)(13)(331) d[3]-1 = (2) (3) (7) (13)(331) (14909897) d[4]-1 = (2) (3) (11)(13)(331)(7505)(77839)(323759)(14909897) d[5]-1 = (d[4]-1)(3)(3)(5)(5)(big composite) If we let f_N(n) denote one less than the index of the first non-integer value given by the recurrence formula (1) with the initial value d[0]=n, then we saw previously that f_5(37) = 4. I've also found that f_3(51)=2, and evidently f_3(61)=13. Of course, this doesn't completly describe an expansion, because once the integers break down we can start over again with the new N/D, as illustrated by the case 3/179: 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 2, 3, 4, 1 |---------------------------------------------------| |--------| |-| By the way, there may be some connection with a sequence studied by Sylvester, defined in Sloane's Handbook of Integer Sequences (M0865) as a(n+1) = a(n)^2 - a(n) + 1 This is the same as formula (1) except it doesn't have the last term involving N. We might try to estimate, on a naive probabilistic basis, the expected value of f_N(n) for any given N and n, because it seems to depend only on whether each d[k] is or is not congruent to +-1 (mod N+k). If d[k] were equally likely to be in any of the N+k equivalence classes mod N+k, this would give a probability of 2/(N+k) that the kth step will give an integer. Thus we might infer that small numerators N will give the best chance for long strings, and the probability of j consecutive integers would be something like N! ------ 2^j (N+j)! However, if this were correct, the case 3/179 would have a probability of about 1 in 425,675,250. Evidently the assumption of equi-probable equivalence classes is wrong. Here's a short of list of fractions that act somewhat like 3/179 under iterations of x[k-1]^2 - 1 x[k] = x[k-1]^2 - x[k-1] + 1 - ------------ (1) N+k Table of "Persistently Odd & Greedy" Denominators numerators 3 5 7 11 13 17 19 ----- ----- ------ ------ ------ ------ -------- 179 139 12473 1627 50387\ 218483\ 168149 197 1399 18143 14299 84239/ 223651/ 223211 377 2209 20663 17071 129947 366283\ 334931 629 2699 22049 41381 260597 371449/ 827 3649 24023 46331 594047\ 398071 1079 4909 32129 58057 627899/ 589933 1367 5039 40193 77417 674309 1619 5809 43679 99439 1817 5849 45863 1997 7289 46073 2069 8549 2249 For example, the first "stubborn" fraction with numerator 5 is 5/139. The next is 5/1399, and so on. Each of these gives integer values for AT LEAST the initial 9 steps of the recurrence. To go beyond this, we can evaluates the recurrence (mod p) for various primes p, which enables us to determine how long the sequence goes on giving integers (although it won't tell what those integers are). Obviously every one of these stubborn fractions N/D has D=-1 (mod 2N). In addition, it seems that if N = 1 (or 0) (mod 3) then D=-1 (mod 6N). I didn't include N=1 in the above table, but it's interesting to determine the persistent denominators for that case as well. It seems that the most persistent are D = 19, 61, 73, 151, 181, 193, 271, 283, 379, and so on. The first 10 denominators of the odd-greedy expansion for 5/139 = 1/29 + 1/673 + ...etc. are given here. The sequence terminates after 19 steps, and the numerators of the remainders are 5,6,7,8,9,10,11,12,13,14,15,16,17,26,51,2,3,4,1 We would like to efficiently determine an upper limit for the number of consecutive iterations of (1) that could possibly yield integers, beginning with the initial value x[0] = (D+1)/N + 1 for any given fraction N/D. The only simple way of doing this that I can see is by evaluating the iteration (mod p) for various primes p > N+1. If x[p-N-1] is not congruent to +1 or -1 (mod p), then the string must be broken at (or before) the point when N+k reaches p. The limiting primes by which point the string must break down for various fractions are listed below 3/179 17 5/139 17 3/197 17 5/1399 19 3/377 13 5/2209 19 3/629 13 5/2699 17 3/827 13 5/3649 17 3/1079 13 5/4909 17 3/1367 41 5/5039 17 3/1619 17 5/5809 31 3/1817 19 5/5849 17 3/1997 13 5/7289 17 3/2069 29 5/8549 17 3/2249 13 3/2267 13 3/2447 19 3/2699 13 3/2879 23 3/2897 13 3/2969 13 This suggests that 3/1367, 3/2069, 3/2879, and 5/5809 would be good candidate for highly "stubborn" odd greedy expansions, since the sequences of uniformly increasing remainders in these cases don't *necessarily* break down until N+k equals 41, 29, 23, and 31 respectively. Of course, they COULD break down much sooner. The others (the 13's and 17's) definitely won't yield expansions of length greater than 17. Another interesting approach to this problem is to determine the sufficient condition for greediness of a sequence. Clearly if 1/n is a term in the sequence, then the sum of all later terms in the sequence must be less than the difference 1/n - 1/(n+2) = ((n+2)-(n))/(n(n+2)) = 2/(n(n+2)) Now, for all odd n (greater than 1) we have the inequality 2/(n(n+2)) > 1/n^2 + 1/n^4 + 1/n^8 + ... from which it follows that if each denominator is more than the square of the preceeding one, then the sequence is greedy. The question is whether the sum of an infinite greedy sequence can ever be rational. (Of course, I haven't shown that this is a *sufficient condition* for greed, but merely a necessary condition. Thus, there could be greedy sequences that do not satisfy the "quadratic condition".) This question is answered in Irrationality of Quadratic Sums. Also, a method of constructing fractions with arbitrarily long odd greedy expansions with consecutive integer remainder numerators is presented in Odd-Greedy Unit Fraction Expansions.

Return to MathPages Main Menu