Back
A fraction a/b is said to be written in Egyptian form if we have
a/b = 1/n1 + 1/n2 + 1/n3 + ... + 1/nk
for distinct positive integers n1, n2, ... nk for some k > 0. For example,
we can write the fraction 21/23 in several ways in Egyptian form, as
follows:
21/23 = 1/2 + 1/3 + 1/13 + 1/359 + 1/644046
21/23 = 1/2 + 1/3 + 1/13 + 1/598 + 1/897
21/23 = 1/2 + 1/3 + 1/15 + 1/110 + 1/253
21/23 = 1/2 + 1/3 + 1/15 + 1/115 + 1/230
21/23 = 1/2 + 1/3 + 1/23 + 1/46 + 1/69
We can rank these forms according to the sum of the denominators used, with
a smaller sum being better. By this ranking, the first form, obtained by a
greedy algorithm, is the worst. The last one is best, with a minimal
denominator sum of 143.
Write the fraction 19/97 in Egyptian form, with as small a denominator sum
as possible.
Note: Egyptian fractions are almost always required to exclude repeated
terms, so for this problem assume n1 < n2 < ... < nk.
Well, I've got an answer, although I'm far from certain it's 'optimal'.
I had to do a little research in this problem, and from what I've
discovered it doesn't look like this problem is 'solved' yet anyway. (Not
the specific example, but the general case of Egyptian Fractions.)
My solution is 8+16+194+388+1552 = 2158. The way I attacked this problem
is a 2 pass approach:
Pass 1: Find all even powers of 2 'x' such that 1/x is less than our
current sum and x<denominator. Subtract that value from the sum.
Pass 2: Find all even powers of 2 'x' such that 1/(x*Den) is less than the
current sum, and subtract that value.
Using that method, I got 1/8 + 1/16 from the first pass, then 1/194 (97*2),
1/388 (97*4) and 1/1552 (97*16) from the second.
I suspect this is not optimal, since using the same approach on the example
problem gives (2,4,8,46,92,184) or 336 vs the '143' solution given. I'll
keep pondering. :-)
Tom
Yes, I'm replying to my own post. :-)
I modified my code a little bit to try all numbers which have only 2 or 3
as their prime factors, but keeping with the "greedy" selection. I got
interesting results, but still not too useful for optimal solutions.
For the 21/23 problem, I was hoping to get the suggested sequence.
Instead, I got 2,3,16,69,368, totalling 458.
For the 19/97 problem, I got the sequence 6,36,776,6984 for a total of
7802.
Back to the drawing board...
The solution I found is less than 2158, though I'm not certain whether it
is optimal either. All I know is that this was the best answer out of
several entries, and it was discovered by three different people. Your
answer is so far better than all others submitted in that contest, aside
from the first-place answer of course. :)
I'll look through my notes and program later on to see if I can rediscover
how I came up with the answer. I do know that this particular puzzle's
directory contains a paper I found detailing a method of rewriting an
egyptian fraction in order to reduce the denominator sum (where possible),
but I can't recall whether I made use of it.
Happy puzzling...
Interestingly enough, the "greedy" algorithm comes up with the result
1/6 + 1/35 + 1/1567 + 1/31919790,
which is clearly inferior to the results Tom posted. I haven't had time to
try anything else yet.
It turns out that the paper I referred to does NOT detail a method of
rewriting an egyptian fraction in order to reduce the denominator sum.
This makes sense, since there is still no known algorithm to find the
representation with minimal denominator sum for a given fraction.
Instead, this paper describes a method to remove duplication from a sum of
unit fractions without changing the length (number of terms) of the
egyptian fraction representation. Since this puzzle forbids duplication of
denominators in the first place, the ideas in this paper, though
interesting, could not have helped me find a solution.
I do remember writing a program to intelligently search for solutions, but
I can't find the source for it anywhere. It found a solution that was two
away from the best solution calculated by the "puzzle master", and from
there I can't remember if I used the program, or just pen and paper, to
ultimately discover his solution.
As to the optimality, the puzzle master believed his solution to be
optimal, but he was having trouble verifying that claim.
My code is very short, I'd be happy to post it. I was having all sorts of
floating point error problems at first, so my working version does
everything in integers.
This isn't well commented, but it's probably legible enough to
decipher.(2**num = 2^num)
==================================
#!/opt/bin/python
from math import *
num=19
den=97
total=0
lcm=2**num*den
x=num*2**num
y=1 ; done=0
while x and not done:
if (lcm/y)<=x:
print y
total = total + y
x = x - (lcm/y)
y=y*2
if y>den: done=1
y=1
while x:
if (lcm/(y*den))<=x:
print y*den
total = total + y*den
x = x - (lcm/(y*den))
y=y*2
print "Total: ",total
==================================
Output:
8
16
194
388
1552
Total: 2158
Okay, I'm nearing giving up on finding a better solution, I don't see a
good way to tackle the problem. I'll take a hint I suppose, or you can
post the solution if others aren't interested in working on this problem
more.
I know ancient Egyptians used such terms to simplify calculations involving
fractions with great accuracy and even had tables for reference. Does
anyone know if any of the surviving mathematical papyri -- Papyrus of
Moscow, Rhind Papyrus, or Ahmose Papyrus -- shed any light as to how
Egyptians came up with solutions? Unfortunately, I cannot read
Hieroglyphics. However, I came across a book titled "Civilization or
Barbarism" by the late Senegalese Physicist, Sheikh Anta Diop, that has a
chapter on Egyptian contributions to Mathematics often not highlighted or
errorneously attributed to others. I would love to hear what those who have
read the book think about that chapter.
Tacker: jason
Kiros wrote:
> I know ancient Egyptians used such terms to simplify calculations
> involving fractions with great accuracy and even had tables for
> reference. Does anyone know if any of the surviving mathematical papyri
> -- Papyrus of Moscow, Rhind Papyrus, or Ahmose Papyrus -- shed any light
> as to how Egyptians came up with solutions?
Nobody seems to know for sure. I found this page:
http://www-gap.dcs.st-and.ac.uk/~history/HistTopics/Egyptian_papyri.html
which says:
"There is the fascinating question of how these decompositions were found,
and why some decompositions were chosen in preference to others. This is
discussed in [6] and further ideas, adding and correcting information from
[6], is given in [17], [18], [29] and [35]. The favourite rules which many
historians such as Gillings believe guided the scribes in their choice of
decomposition of 2/n into unit fractions are (1) prefer small numbers (2)
the fewer terms the better, and never more than four (3) prefer even to odd
numbers. However other historians such as Bruins argues against such rules.
His argument is essentially that before applying these rules one would need
to work out all unit decompositions of 2/n and there is no evidence that
the Egyptians had any methods to do this."
Tom wrote:
> Okay, I'm nearing giving up on finding a better solution, I don't see a
> good way to tackle the problem. I'll take a hint I suppose, or you can
> post the solution if others aren't interested in working on this problem
> more.
I just counted - I've found 229 unique representations of up to 11 terms
with denominator sum less than 2158 (with 101 unique denominator sums),
using a modified program. Here's a good hint (which I used to speed up
this program by a huge factor - otherwise I would only be able to calculate
out to 6 or 7 terms within a reasonable time): only consider denominators
{6,7,...,95,96} or k*97 for some positive integer k. The reasoning behind
k*97 is that denominators larger than, but not divisible by, 97 will only
cause the denominator sum to skyrocket since 97 is prime, and thus large
denominators will be required to correct for this "mistake". :^) Using
this hint, you should be able to brute-force this answer relatively
quickly. For example, my modified program finds the answer in less than
0.2 seconds, whereas without this heuristic, it took 190 seconds.
For reference, here are all the representations that I found with
denominator sum 2158:
1/8 + 1/16 + 1/194 + 1/388 + 1/1552
1/11 + 1/22 + 1/42 + 1/66 + 1/77 + 1/194 + 1/679 + 1/1067
1/12 + 1/22 + 1/30 + 1/70 + 1/84 + 1/194 + 1/679 + 1/1067
1/12 + 1/22 + 1/32 + 1/56 + 1/96 + 1/194 + 1/679 + 1/1067
1/14 + 1/16 + 1/45 + 1/63 + 1/80 + 1/194 + 1/291 + 1/679 + 1/776
1/14 + 1/16 + 1/48 + 1/56 + 1/84 + 1/194 + 1/291 + 1/679 + 1/776
1/21 + 1/24 + 1/35 + 1/40 + 1/42 + 1/56 + 1/194 + 1/291 + 1/679 + 1/776
Tacker: jason
Is anyone else currently working on this problem? If not, then I'll go
ahead and post a solution by the end of the week.
(or at least one of my several hundred 'jason' personalities listed above
will post it... yeesh. that's what i get for posting from iceland, a
development server)
I just wrote a simple 70 line Perl program (well, it is not very simple) to
solve this kind of problems. :)
I cache all prime numbers, but it is still slow!
Maybe I should cache all reduced fractions too. Currently it reduces,
say, 12345/67890 = 823/4526 every time it encounters a fraction.
But then I need a lot of memory. :)
Or, maybe I don't need to reduce fractions. :)
<remark>
I thought I need to reduce fractions if I want to stay with perl5 integer
arithmetics. I may switch to perl6 or ruby or use special LongNum modules
to manipulate numbers larger than 1e+15, but it does not worth it. :)
But, just tested, perl (at least 5.005 or greater) works with any large
number without losing any precision.
$ perl -e '$f = 1; $f *= $_ for 1..50; print "50! = $f\n"; $f /= $_ for 1..49;
print "50!/49! = $f\n"'
50! = 3.04140932017134e+64
50!/49! = 50
</remark>
Ok, it runs for one hour now and it is still far from solving 21/23 fully.
I limited the program to 6 summands not larger than 2000.
Here is one additional solution:
21/23 = 1/2 + 1/3 + 1/13 + 1/494 + 1/1311 Sum: 1823
I may run the 19/97 tonight, but something tells me it will take days. :)
Ok, it was a stupid idea to reduce fractions and deal with primes. :)
Now it takes several seconds to find:
21/23 = 1/2 + 1/3 + 1/13 + 1/663 + 1/782 (Sum: 1463)
21/23 = 1/2 + 1/3 + 1/14 + 1/161 + 1/483 (Sum: 663)
21/23 = 1/2 + 1/3 + 1/14 + 1/231 + 1/253 (Sum: 503)
21/23 = 1/2 + 1/3 + 1/15 + 1/85 + 1/782 (Sum: 887)
21/23 = 1/2 + 1/3 + 1/15 + 1/92 + 1/460 (Sum: 572)
21/23 = 1/2 + 1/3 + 1/15 + 1/110 + 1/253 (Sum: 383)
21/23 = 1/2 + 1/3 + 1/15 + 1/115 + 1/230 (Sum: 365)
21/23 = 1/2 + 1/3 + 1/16 + 1/69 + 1/368 (Sum: 458)
21/23 = 1/2 + 1/3 + 1/17 + 1/51 + 1/782 (Sum: 855)
21/23 = 1/2 + 1/3 + 1/18 + 1/46 + 1/414 (Sum: 483)
21/23 = 1/2 + 1/3 + 1/22 + 1/33 + 1/253 (Sum: 313)
21/23 = 1/2 + 1/3 + 1/23 + 1/30 + 1/345 (Sum: 403)
21/23 = 1/2 + 1/3 + 1/23 + 1/46 + 1/69 (Sum: 143)
But, it is still not optimized enough for 19/97. :)
19/97 = 1/6 + 1/36 + 1/1164 + 1/1746 (Sum: 2952)
Actually, interesting result, just 4 summans. :)
Will need to wait to see more results.
Jason, thanks for the optimization idea. I enhanced it for non prime
deminators too. So after all I reused my reduceFraction function. :)
I am sure there are more similar optimizations, it may be faster.
My current best result is:
19/97 = 1/7 + 1/22 + 1/194 + 1/679 + 1/1067 (Sum: 1969)
I also have a non-strict switch that gives me much better results:
19/97 = 1/6 + 1/97 + 1/97 + 1/194 + 1/291 (Sum: 685)
19/97 = 1/7 + 1/42 + 1/97 + 1/97 + 1/194 + 1/291 (Sum: 728)
19/97 = 1/8 + 1/24 + 1/97 + 1/97 + 1/194 + 1/291 (Sum: 711)
For comparision:
19/97 = 1/97 + ... + 1/97 (Sum: 1843)
Interesting puzzle. :)
Congratulations Mikhael, you found the best known solution! Nice work.
Just for kicks, what are your best solutions for a fixed number of
fractions n, n = 4, 5, ..., 11? Of course, you've already solved the case
n = 5. :)
Ok. But I didn't wait for these queries to be completed (I don't have
CPU clusters), so at least the last values are surely not the best.
19/97 = 1/6 + 1/54 + 1/97 + 1/2619 (Sum: 2776)
19/97 = 1/7 + 1/22 + 1/194 + 1/679 + 1/1067 (Sum: 1969)
19/97 = 1/7 + 1/24 + 1/194 + 1/291 + 1/679 + 1/776 (Sum: 1971)
19/97 = 1/8 + 1/28 + 1/42 + 1/194 + 1/291 + 1/679 + 1/776 (Sum: 2018)
19/97 = 1/8 + 1/36 + 1/56 + 1/72 + 1/194 + 1/291 + 1/679 + 1/776 (Sum: 2112)
A larger number of summands can't easily fit into your terminal (80 chars),
so I will skip this. Is it a good cause? :-) Besides, it would take me many
many hours. Yes, the task is not trivial.
BTW, my script gets 5 numeric parameters and 3 flags, all are optional.
Unfortunately, I forgot to add --speed-it-up-to-the-light-speed-at-least.
Jason, feel free to post your results. :)
No problem, I was just curious to see how far out your perl script could
calculate, and whether our results would agree. :) Here's what I've
found:
4. 2776 : 1/6 + 1/54 + 1/97 + 1/2619
5. 1969 : 1/7 + 1/22 + 1/194 + 1/679 + 1/1067
6. 1971 : 1/7 + 1/24 + 1/194 + 1/291 + 1/679 + 1/776
7. 2018 : 1/8 + 1/28 + 1/42 + 1/194 + 1/291 + 1/679 + 1/776
8. 2035 : 1/15 + 1/21 + 1/24 + 1/35 + 1/194 + 1/291 + 1/679 + 1/776
9. 2084 : 1/20 + 1/24 + 1/28 + 1/30 + 1/42 + 1/194 + 1/291 + 1/679 + 1/776
10. 2145 : 1/24 + 1/28 + 1/30 + 1/36 + 1/42 + 1/45 + 1/194 + 1/291 + 1/679 + 1/776
11. 2221 : 1/28 + 1/30 + 1/36 + 1/40 + 1/42 + 1/45 + 1/60 + 1/194 + 1/291 + 1/679 + 1/776
and so far, here's the best for n = 12:
12. 2422 : 1/13 + 1/52 + 1/55 + 1/63 + 1/66 + 1/70 + 1/72 + 1/91 + 1/194 + 1/291 + 1/679 + 1/776
I've noticed a similar pattern for other fractions, i.e. the lowest
denominator sum for a given length tends to decrease as n increases, until
you reach the best solution, then begins to increase from then on out. I
suspect there is an underlying reason for this, but I'm not equipped to
deduce it. ;)
Here are the running times for this program, on an Athlon XP 1600+:
4. 0.038s
5. 0.183s
6. 4.252s
7. 1m 9.408s
8. 9m 37.084s
9. 45m 25.504s
10. 138m 50.682s
11. 331m 17.378s
I expect the n = 12 case to wrap up after about 12 hours of total running
time.
Ok, what's next? :)
Maybe we should find the best result that is longest among small
fractions, like;
11/23 = 1/6 + 1/7 + 1/14 + 1/21 + 1/23 + 1/161 (Sum: 232)
Or maybe we should study the behaviour of fractions greater than 1. :)
12/11 = 1/2 + 1/3 + 1/6 + 1/11 (Sum: 22)
13/11 = 1/2 + 1/3 + 1/4 + 1/22 + 1/33 + 1/44 (Sum: 108)
14/11 = 1/2 + 1/3 + 1/4 + 1/6 + 1/44 (Sum: 59)
15/11 = 1/2 + 1/3 + 1/4 + 1/6 + 1/11 + 1/44 (Sum: 70)
16/11 = 1/2 + 1/3 + 1/5 + 1/6 + 1/10 + 1/11 + 1/22 + 1/55 (Sum: 114)
17/11 = 1/2 + 1/3 + 1/4 + 1/5 + 1/10 + 1/11 + 1/33 + 1/44 + 1/55 (Sum: 167)
18/11 = 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/10 + 1/22 + 1/44 + 1/55 (Sum: 151)
19/11 = 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/10 + 1/11 + 1/22 + 1/44 + 1/55 (Sum: 162)
20/11 = ?
I am more a programmer than a mathematican to suggest any theory. ;)
A sufficient condition for an Egyptian fraction representation
is that the numerator is a sum of the divisors of the
denominator. For example
13 9+3+1 1 1 1
-- = ----- = - + - + --
18 18 2 6 18
So I wrote a tester
(defun partitionp(n list)
"make n from numbers on the list, which must be in decreasing order"
(when (consp list)
(if (> (car list) n)
(partitionp n (cdr list))
(if (= (car list) n)
t
(bind sum (reduce #'+ list)
(and (<= n sum)
(if (<= (* 2 n) sum)
(or (partitionp n (cdr list))
(partitionp (- n (car list))
(cdr list)))
(or (partitionp (- n (car list))
(cdr list))
(partitionp n (cdr list))))))))))
So you can work systematically
21/23-1/2, 21/23-1/3, 21/23-1/4, 21/23-1/5
21/23-1/6 = 103/138
The divisors of 138 are 1 2 3 6 23 46 69 138
and 103 = 2+3+6+23+69
Thus 21/23/=1/6+69/138+23/138+6/138+3/138+2/138
=1/6+1/2+1/6+1/46+1/69
which doesn't quite work because we have two 1/6's
but we get away with it because 1/6+1/6=1/3 and we
haven't already use 1/3.
Also 19/97 - 1/16 = 207/1552
207 = 194 + 8 + 4 + 1, all divisors of 1552 giving
19/97 = 1/16 + 1/8 + 1/194 + 1/388 + 1/1552