The
oddgreedy algorithm problem
We start with a simple numerical observation:

represents
(which has an
odd
denominator)
as a sum of unit fractions
all
of whose denominators are
even

represents the same
as a sum of unit fractions
all
of whose denominators are
odd
A natural question to ask is this: if
is a fraction with an odd denominator, does it have an egyptian fraction representation with all denominators odd? (It is automatic that a fraction  in reduced form  with an even denominator, could
not
have such a representation.)
It has been proved (R. Breusch; see References) that every
, with
b
odd
, has an egyptian fraction representation in which every denominator is also
odd
.
The first of the above representations of
is clearly obtained by applying the
standard greedy
algorithm, but the second representation is obtained by making the following
oddgreedy
modification. Start by asking if we may represent
by:
with
all
the
odd
and see how far we can get by
attempting
to use the standard greedy algorithm:

and we
attempt
=
is
even
. Now we attempt the
second closest
unit fraction, the one with denominator 5. So we set:
. That leads to
=
which gives
=
, and the thing to note is the
increased
numerator (that
novel
behaviour means we now have a problem on our hands...). However, we have
, and we plough on with the
to see:

and we
attempt
=
is
even
. So we attempt
, the next best denominator. That leads to
=
which gives
=
, and we note there is yet another
increased
numerator. So far
, and we plough on with
to see:

and we
attempt
=
is
even
. So we attempt
, the next best denominator. That leads to
=
which gives
=
=
, is a unit fraction (that's
) with an odd denominator!!
Thus we have ended up with
.
Advice. Do some examples to get the hang of this modification to the standard greedy algorithm.
'Doing'
leads to the representation
. Don't allow that
to put you off.
Do these examples:
and
.
The oddgreedy algorithm (unanswered) question is simply this
:
does the above process always
terminate
?
The
point
of that question should be obvious:

With the regular greedy algorithm there is the (proven)
decrease
in the successive numerators; it's precisely that which gaurantees the termination
HOWEVER

When one attempts the oddgreedy modification, the behaviour of successive denominators can be, and generally is,
quite different
. And while the sequence of successive
r
's is decreasing (but their integral numerators may not be), there is the prospect that that
could
exist some initial fraction
which leads to an
infinite
sequence:
See Stan Wagon's email below.
(An interesting elementary question to investigate is: how many fractions (with odd numerator) can one produce for which the greedy and oddgreedy algorithms produce the same output. For example,
is produced by both.)
I have adapted our earlier ordinary greedy algorithm to put the above
odd greedy
approach into effect. I
could
write a more sophisticated one (one, for example that would reject an input 'R' which didn't have an odd numerator), but I want to keep everything to a minimum.
The thinking behing the lines should be obvious to anyone who has done hand examples.
>
odd_egypt := proc(R)
local r, n, k; r[0] := R:
if ceil(1/r[0]) mod 2 = 1 then n[1] := ceil(1/r[0]);
else n[1] := ceil(1/r[0]) + 1;
fi: r[1] := r[0]  1/n[1];
for k from 2 while r[k1] <> 0 do
if ceil(1/r[k1]) <= n[k1] then n[k] := n[k1] + 2;
elif ceil(1/r[k1]) mod 2 = 1 then n[k] := ceil(1/r[k1]);
else n[k] := ceil(1/r[k1])+1;
fi; r[k] := r[k1]  1/n[k];
od: seq(1/n[j], j=1..k1); end:
>
>
odd_egypt(2/7); # the above initial example
>
odd_egypt(8/9);
>
odd_egypt(14/15);
>
odd_egypt(3/13);
>
Some small numerator examples (producing smallish denominators) are:
>
odd_egypt(2/3);
odd_egypt(2/5);
odd_egypt(2/9);
odd_egypt(3/5);
odd_egypt(3/7);
odd_egypt(3/11);
>
Some small numerator examples that produce large denominators are:
>
odd_egypt(2/11);
odd_egypt(2/19);
odd_egypt(2/23);
odd_egypt(3/17);
odd_egypt(3/23);
>
In October 1996, Stan Wagon announced a
quite extraordinary numerical discovery
: Here are two emails of Wagon's (in the public domain) which capture the excitement of his discovery:
Date: Sat, 12 Oct 1996 17:05:31 0700 (PDT)
From: [email protected]
Subject: Odd Greediness
To: [email protected]

I am busily updating my Egyptian fraction algorithms for a revision of MinA. I was testing your heuristic for the Odd Greedy, when I discovered 3/179. Odd Greedy does not do well on this at all. In fact, I have not completed the representation. So far I am at a term with 55,000 digits. The number of digits is doubleing at each stage. I hesitate to suggest that this might be a counterexample...... stan wagon
Date: Sun, 13 Oct 1996 12:11:32 0700 (PDT)
From: [email protected]
Subject: an amazing Egyptian fraction
To: Klee, Campbell, Guy, Eppstein, Wellin

The number 3/179 has a rather amazing output when the greedy odd Egyptian fraction algorithm is tried out on it. Recall that it is a famous open question whether
ODD GREEDY
always halts. On 3/179 the algorithm produces 19 terms, the last of which has 439492 digits!!! Takes a little under an hour for my computer to get this.
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, when I saw the 3, 4, 5, 6... I thought I was on to something....could this continue forever? Well, I don't think so.

Wagon's 439492 digits may be verified with the program above (obviously I won't save it for placing on web site!!):
>
# odd_egypt(3/179);
>
I have modified the earlier odd_egypt procedure to make it stop after a certain number of steps,
BOUND
(I've simply removed the 'while' line and replaced it with "for k from 2 to
BOUND
do"):
>
stop_odd_egypt := proc(R, BOUND)
local r, n, k; r[0] := R:
if ceil(1/r[0]) mod 2 = 1 then n[1] := ceil(1/r[0]);
else n[1] := ceil(1/r[0]) + 1;
fi: r[1] := r[0]  1/n[1];
for k from 2 to BOUND do
if ceil(1/r[k1]) <= n[k1] then n[k] := n[k1] + 2;
elif ceil(1/r[k1]) mod 2 = 1 then n[k] := ceil(1/r[k1]);
else n[k] := ceil(1/r[k1])+1;
fi; r[k] := r[k1]  1/n[k];
od:
print(seq(1/n[j], j = 1..k1));
lprint(`See the numerators, including the initial one:`);
seq(numer(r[j]), j=0..BOUND); end:
>
stop_odd_egypt(3/179, 5);
`See the numerators, including the initial one:`
>
You may verify the first few by hand:
=
, is even, so go to denominator 61
Then
=
, etc
>
3/179  1/61;
>
4/10919  1/2731;
>
5/29819789  1/5963959;
>
stop_odd_egypt(3/2879, 4);
`See the numerators, including the initial one:`
>
stop_odd_egypt(5/5809, 4);
`See the numerators, including the initial one:`
>