Author: jason (Jason Jordan)
Date: 2003-Oct-22 13:50:27

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.


Author: tomc (Tom Carmichael) Date: 2003-Oct-22 20:19:39 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
Author: tomc (Tom Carmichael) Date: 2003-Oct-22 21:08:02 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...
Author: jason (Jason Jordan) Date: 2003-Oct-22 21:48:12 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...
Author: bandsmer (Michael Bandsmer) Date: 2003-Oct-23 00:45:05 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.
Author: jason (Jason Jordan) Date: 2003-Oct-23 02:24:00 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.
Author: tomc (Tom Carmichael) Date: 2003-Oct-23 14:25:36 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
Author: tomc (Tom Carmichael) Date: 2003-Oct-27 11:35:27 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.
Author: lekipas (Kiros Lekarsia) Date: 2003-Oct-27 12:49:46 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 Date: 2003-Oct-27 15:55:22 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 Date: 2003-Oct-27 16:36:19 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)
Author: migo (Mikhael Goikhman) Date: 2003-Oct-27 15:49:49 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. :)
Author: migo (Mikhael Goikhman) Date: 2003-Oct-27 17:55:33 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.
Author: migo (Mikhael Goikhman) Date: 2003-Oct-27 21:34:31 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. :)
Author: jason (Jason Jordan) Date: 2003-Oct-27 23:44:34 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. :)
Author: migo (Mikhael Goikhman) Date: 2003-Oct-28 02:17:18 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. :)
Author: jason (Jason Jordan) Date: 2003-Oct-28 02:46:59 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.
Author: migo (Mikhael Goikhman) Date: 2003-Oct-28 03:07:36 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. ;)
Author: alan (Alan Crowe) Date: 2003-Oct-28 11:00:11 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