Odd, Greedy, and Stubborn (Unit Fractions)
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 remainders we encountered during this process were 1/3, 2/15,
1/45, and finally 0.
There are some interesting unsolved problems related to odd greedy
expansions. (See the section on Egyptian Fractions in Guy's "Unsolved
Problems In Number Theory".) One open question is whether every
fraction is guaranteed to terminate in a finite number of steps.
In this regard, Stan Wagon has noted that if the fraction 3/179 is
converted into a sum of unit fractions with odd denominators using
the greedy algorithm, it takes an unusually large number of steps
before it terminates, and the sequence of remainders is very
distinctive. Specifically, he notes that
On 3/179 the algorithm produces 19 terms, the last of which has
439492 digits!!! And the sequence of numerators of the remainders is
somewhat amazing:
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.)
It's interesting to partition 1 into distinct unit fractions with odd
denominators using the greedy approach (except not using 1/1 on the
first step). The result seems to be
1 = 1/3 + 1/5 + 1/7 + 1/9 + 1/11 + 1/13 + 1/23 + 1/721 + 1/979007
+ 1/661211444787 + ...
If we restrict ourselves to prime denominators we have
1 = 1/2 + 1/3 + 1/7 + 1/43 + 1/1811 + 1/654149 + ...
These numbers are evidently mentioned in Guy's Unsolved Problems, which
references D.R.Curtiss, "On Kellogg's Diophantine problem" Amer Math
Monthly, 29, (1922), 380-387. They also seem related to Sylvester's
sequence
a(n+1) = a(n)^2 - a(n) + 1
whose values are
2, 3, 7, 43, 1807, 3263443, 10650056950807, ...
but of course 1807 isn't a prime, so I'm not sure if Curtiss's work
is related to this sequence or the sequence of primes. (Guy only
quotes the denominators up to 43.) It may take a trip to the
library to sort this out.
Anyway, returning to the 3/179 phenomenon, it's worth noting that, in
general, if you have a fraction N/D you 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 the fraction suggested by Stan Wagon, 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.
Judging from the remainders quoted by Stan in his email I'd guess that
f_3(61)=13. It would be interesting to tabulate f(n) for each value of n
up to, say 1000. Of course, this doesn't completly describe an expansion,
because once the integers break down you can start over again with the
new N/D, as illustrated by the remainders in Stan's example
3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 2, 3, 4, 1
|---------------------------------------------------| |--------| |-|
Nevertheless, it would be interesting to know the lengths of just the
first unbroken sequence for each initial value, to see if 61 is the
optimum. I wouldn't be surprised if there are arbitrarily large values
of f_3(n). To put it another way, it would be surprising if there was
some finite upper limit to f_3(n). A similar survey could be done for
f_N(n) for other values of N.
By the way, this all may be related to Sylvester's sequence, 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. I tried expanding the number 1 into unit fractions
using the "prime-greedy" algorithm and got the sequence of denominators
2, 3, 7, 43, 1811,...etc. Then I looked up this sequence in Neil Sloane's
Handbook of Integer Sequences and didn't find it...but I did notice the
sequence 2,3,7,43,1807,...etc, which Sloane identifies as "Sylvester's
sequence: a(n+1) = a(n)^2 - a(n) + 1". That didn't mean much to me, but
then later when I derived the recurrence formula (1) from the requirement
that the remainders increase by 1 at each step I noticed that it's very
similar to Sylvester's recurrence. Sloane gives a couple of references,
so I may try to check them out and see what Sylvester was doing.
In any case, I suppose we could estimate the expected value of f_N(n) for
any given N and n, because it seems to just be a matter of whether each
d[k] is or is not congruent to +-1 (mod N+k). Assuming d[k] is equally
likely to be in any of the N+k equivalence classes mod N+k, this gives
a probability of 2/(N+k) that the kth step will give an integer. This
certainly suggests that small numerators N will give the best chance
for long strings. I suppose the probability of j consecutive integers
is something like
N!
------ 2^j
(N+j)!
Hmmm...this suggests that Stan Wagon's example has a probability of
about 1 in 425,675,250. Maybe the assumption of equi-probable
equivalence classes is wrong?
After looking at this a bit more, I've found a few more examples of
fractions like Stan's 3/179 that persist for a long time under the
odd-greedy algorithm. Here's a short of list of fractions that act
somewhat like 3/179 under iterations of
x[k] -> x[k-1]^2 - x[k-1] + 1 - (x^2-1)/(N+k) (1)
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. Stan's example is the first with numerator
3, followed by 3/197, 3/377, and so on. Each of these gives integer values
for AT LEAST the initial 9 steps of the recurrence. That's as far as
UBASIC will go before overflowing. I may try to get access to a program
like Maple or Mathematica that (I think) can handle larger numbers. Failing
that, I may try to write a program that evaluates the recurrence (mod p)
for various primes p, which should enable me to determine how long the
sequence goes on giving integers (although it won't tell me 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.
Incidentally, here are the first 10 denominators of the odd-greedy expansion
for 5/139 = 1/29 + 1/673 + ...etc. The remainders are 5,6,7,8,9,10,11,12,13,
14,15,...? This is as far as UBASIC will go.
Table of denominators for 5/139
Stan Wagon kindly evaluated this fraction in Mathematica and found the
terminating sequence of remainder-numerators
{5,6,7,8,9,10,11,12,13,14,15,16,17,26,51,2,3,4,1}
and the last term has about 362799 digits. I'm a bit surprised by the
remainder 26, since I would have thought it would be a divisor of 18.
The occurrence of 2*13 and then 3*17, followed by the concluding sequence
2,3,4,1 is very interesting, as is the fact that the uniform sequences of
remainders for both 3/179 and 5/139 terminate at 17.
Lacking a mega-precision program I've tried to figure out an upper limit
for the number of consecutive iterations of
x[k-1]^2 - 1
x[k] = x[k-1]^2 - x[k-1] + 1 - ------------
N+k
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 a good candidate for highly "stubborn" odd greedy
expansions is 3/1367, since the sequence of uniformly increasing remainders
doesn't *necessarily* break down until N+k equals 41. Of course, it COULD
break down much sooner. Other interesting candidates would be 3/2069,
3/2879, and 5/5809. But this analysis suggests that most of the others
(the 13's and 17's) are unlikely to give spectacular results.
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, notice that 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
Wagon Trains and Sticky Wickets.
Return to MathPages Main Menu
Сайт управляется системой
uCoz