Any ratio of integers m/n can be expressed as a finite sum of unit fractions, i.e., fractions with unit numerators. One method of expanding a given fraction into a sum of unit fractions is via the "greedy algorithm", according to which at each stage we select the largest possible unit fraction (i.e., with the least denominator) less than or equal to the current remainder. It's easy to show that this necessarily terminates in a finite number of steps with a complete unit fraction expansion. However, if we allow only odd denominators it's not known whether the greedy algorithm applied to a rational number necessarily terminates in a finite number of steps. Of course, we can easily define real numbers that have infinite odd-greedy expansions - just take any infinite sequence of odd unit fractions such that the kth denominator d[k] is greater than (1/2)d[k-1]^2 - d[k-1] - but we don't know if any such number is rational. (For a more detailed discussion of the possible rationality of infinite odd greedy expansions, see Irrationality of Quadratic Sums.) Anyway, although most ratios of small numbers can be expressed as a sum of just a few odd unit fractions, it turns out that some of these fractions have surprisingly long odd-greedy expansions. For example, the odd-greedy expansion of 3/179 has 19 terms. Moreover, the sequence of numerators of the remainders is striking: 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 2, 3, 4, 1 This was noted by Stan Wagon, who asked via email if there were fractions with even longer odd-greedy expansions, and for an explanation of the sequence of consecutive remainder numerators, which turns out not to be a unique occurrence. (See The Greedy Algorithm for Unit Fractions.) I suggested to Stan that he look at the fraction 5/139, which also runs to 19 terms, with the sequence of remainder numerators 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 26, 51, 2, 3, 4, 1 I also directed his attention to a handful of other possibilities that were likely to yield long sequences, with emphasis on 3/2879 and 5/5809 as being strong candidates. Subsequently David Bailey performed an exhaustive computer search for lenghty sequences and re-discovered the fact that these two fractions give unusually long odd-greedy expansions. The fraction 5/5809 is a particularly nice example because the sequence of remainder numerators increases by 1 at each step, all the way to the end: 5,6,7,...,29,30,1. I also mentioned to Stan (and to David Eppstein) that although the denominators in these sequences can run into the billions of digits, they could be evaluated using modulo arithmetic with a suitable modulus, since the denominators involve only small prime factors. David subsequently applied this approach with the modulus 6(31!)(10!)(6!)(4!)^2 to compute the remainders of the 5/5809 sequence. I also told Stan and David that it wouldn't be too difficult to construct fractions with arbitrarily long odd-greedy expansions, but this apparently was overlooked (judging from Richard Guy's subsequent account of the history of this problem in the Dec 98 issue of The American Mathematical Monthly). So I'll show here how to construct a fraction with odd-greedy expansion of length k for any positive integer k. The key to understanding these expansions is to note that if we begin with any fraction of the form n/(2m-1) where m is divisble by n, the Odd-Greedy algorithm will give the first unit fraction term 1/(2[m/n]+1) with the remainder n+1 -------------------- 2[(m/n)(2m+n-1)] - 1 so this becomes the new fraction to be expanded. In effect the values of n and m have been transformed according to n -> n+1 m -> (m/n)(2m+n-1) Now, if our new value of m is divisible by the new value of n, we can repeat the process, and this continues to give the odd greedy terms and remainders until we reach a stage where m is not divisible by n. Notice that the sequence of numerators consists of consecutive integers, and at each stage m is being divided by n and multiplied by the factor (2m+n-1). Therefore, if our initial value of m is something like 100!, it's clear that we can continue this process for numerators up to AT LEAST 100, at which point we will have exhausted the divisibility that we built in to our initial value of m. However, during those 100 steps we have been multiplying m by many large and generally composite numbers, so there's a fair chance that m will have acquired more useful factors by that point. In any case, we can answer one of our questions by noting that the odd-greedy expansion of 3/(N!-1) must have at least N-2 terms, and the remainders for those terms are 3,4,5,..,N. Of course, our initial m need not be a factorial, but it must be divisible by the first numerator, and it helps if it has some common factors with some subsequent numerators. To illustrate how this works, consider the case of 3/179, where the initial value of m is 90, which only covers the numerators 3 and 5, with a spare power of 3 and 2. On the very first step we divide m by 3 but multiply by (2m+3-1)=182, which fortuitously gives us another power of 2 to cover the numerator 4 (just in time!), and also gives us 7 and 13, which we will use shortly. Then on the next step we divide by 4 but multiply by 10923, which gives us 11 as well as another factor of 3 (not to mention a factor of 331, which doesn't do us much good directly). As we continue we acquire the factors of 2 and 3 we need to cover the numerators 6, 8, and 9, as well as another factor of 5 to cover 10. This shows how the process tends to feed on itself once it gets started, because the more steps we take, the more factors we apply to m, often providing the factors needed to enable further steps with consecutive remainder numerators. This is the reason long sequences of unit-increasing remainders are so common, even for fairly small fractions. It's interesting to consider the odd greedy expansion of a fraction such as 3/(500! - 1). We know this will contain at least 500 terms (and since the number of digits in the denominators roughly doubles on each term, the 500th term would have over 2^500 digits), and the numerators of the remainders will be 4,5,6,...,500, but what will happen then? After cumulatively multiplying into m numbers of the form (2m+n-1) nearly 500 times, we will likely have accumulated a huge number of factors in m, so it wouldn't be too surprising if the sequence continued past the point when the initial m had been exhausted (especially since the terms (2m+n-1) grow exponentially). Recall how 3/179 essentially "lived off the land" for most of its run. The interesting question is whether there might be some "break- even point", so that a fraction like 3/(500!-1) might have enough initial divisibility to boost it into a sequence where, at least probabilistically, we would expect it to be able to continue generating the factors it needs indefinitely. I did some checking, and found that for fractions of the form 3/(2m-1) with m=500! we are able to cover 32 of the 64 primes between 500 and 1000. Similarly, with m=100! we are able to cover 10 of the 20 primes between 100 and 200, and with m=50! we can cover 6 of the 10 primes between 50 and 100. I'm not sure off hand why we seem to be able to cover exactly half the primes. Just for fun, I checked to see how many residues for the initial m value (mod p) are "favorable" for covering p, meaning that by the time we reach a numerator of p we can continue the odd-greedy expansion. Obviously a residue of 0 (mod p) for the initial m guarantees that we can cover p, but I was curious to know how many other residues are favorable for each prime. Here's a little table showing the number of favorable m residues (mod p) for numerators from 1 to 10. Table: Number of Favorable Initial m Residues (mod p) Numerator (initial n) p 1 2 3 4 5 6 7 8 9 10 -- -- -- -- -- -- -- -- -- -- -- 5 3 3 2 0 0 0 0 0 0 0 7 5 4 4 4 2 0 0 0 0 0 11 5 7 8 9 9 6 4 2 2 0 13 5 5 6 5 4 4 6 6 3 2 17 5 5 7 6 5 3 2 3 4 4 19 1 6 5 4 4 2 7 5 8 8 23 9 6 6 6 6 7 8 9 7 6 29 21 19 21 17 16 16 14 11 8 13 31 27 24 19 18 15 14 15 15 14 12 37 21 18 15 14 13 16 15 18 22 22 41 17 22 20 18 19 19 21 20 22 22 43 17 19 22 24 25 30 33 34 33 33 47 33 33 31 30 33 36 36 32 37 32 53 47 49 47 49 49 45 45 43 47 43 59 31 37 37 35 34 31 27 33 28 17 61 39 33 34 34 28 32 26 29 28 31 67 25 28 29 35 32 26 25 24 32 40 71 19 24 20 24 26 28 28 32 30 22 73 21 18 20 19 17 19 18 28 26 28 79 47 52 47 55 50 47 45 53 53 57 83 41 42 51 58 63 59 59 55 55 53 89 43 29 29 34 39 30 38 46 45 51 97 81 71 71 71 76 71 75 73 77 73 101 21 16 18 24 24 30 23 23 32 35 103 21 22 21 22 16 16 12 9 10 12 107 63 58 50 46 42 44 45 55 54 49 109 7 4 2 4 6 4 4 4 9 12 113 81 85 85 87 85 91 97 93 88 89 127 93 100 91 95 91 91 97 91 91 88 131 31 33 33 34 29 33 34 36 40 40 137 63 64 68 64 66 69 71 71 66 66 139 73 79 85 90 94 100 94 91 93 103 149 105 103 103 96 93 95 92 92 89 87 151 17 20 19 17 14 14 10 10 8 15 157 29 24 25 28 34 36 46 47 46 48 163 47 40 40 39 35 34 30 30 24 24 167 25 22 20 23 20 18 17 16 14 14 173 97 95 92 97 94 88 76 77 75 80 179 151 153 155 155 155 151 149 148 145 144 181 173 175 175 177 177 177 179 179 179 175 191 109 104 96 84 85 77 81 82 84 82 193 47 44 40 48 45 59 59 55 54 44 197 93 100 89 88 86 78 79 83 80 87 199 161 163 159 148 143 148 148 141 133 128 The average ratio of favorable residues to total number of residues seems to be close to 1/2. Also, notice that 109 is evidently a "sticky wicket", especially for fractions with numerator 3, because the only way past is to either make the initial m value a multiple of 109 or make it congruent to -1 (mod 109). In contrast p=181 has over 96% favorable.

Return to MathPages Main Menu