Wagon Trains and Sticky Wickets

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 unit fractions, it turns out that some of these 
fractions have surprisingly long odd-greedy expansions.  For example, 
the OG 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 OG expansions, and for an explanation of 
the sequence of consecutive remainder numerators, which turns out not 
to be a unique occurrence.  (See Odd, Greedy, and Stubborn.)  
It seems fitting to refer to odd-greedy unit fraction expansions with 
this kind of remainder sequence as "Wagon Trains".  

I suggested looking 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

as well as 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 search 
for lenghty sequences and verified that these two fractions do indeed
give unusually long "Wagon train" sequences.  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 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 commented that it wouldn't be too difficult to construct
fractions with arbitrarily long "Wagon trains", but this final
suggestion apparently wasn't taken up by anyone (judging from
Richard Guy's recent summary of the history of this problem in
Dec 98 issue of The American Mathematical Monthly), so I'll show
here that in fact it IS easy to construct a fraction with Wagon
train 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
OG 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 OG 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 
looks like a breeze - over 96% favorable.

Return to MathPages Main Menu
Сайт управляется системой uCoz