Egyptian Fractions

Overview:

From Wikipedia: An Egyptian fraction is the sum of distinct unit fractions. That is, each fraction in the expression has a numerator equal to 1 and a denominator that is a positive integer, and all the denominators differ from each other. The value of an expression of this type is a positive rational number a/b. Every positive rational number can be represented by an Egyptian fraction.

Challenge:

Write the shortest function that will return the values of all the denominators for the smallest set of unit fractions that add up to a given fraction.

Rules/Constraints:

• Input will be two positive integer values.
• This can be on `STDIN`, `argv`, comma separated, space delimited, or any other method you prefer.
• The first input value shall be the numerator and the second input value the denominator.
• The first input value shall be less than the second.
• The output may include a value(s) that exceeds the memory limitations of your system/language (RAM, MAX_INT, or whatever other code/system constraints exist). If this happens, simply truncate the result at the highest possible value and note that somehow (i.e. `...`).
• The output should be able to handle a denominator value up to at least 2,147,483,647 (231-1, signed 32-bit `int`).
• A higher value (`long`, etc.) is perfectly acceptable.
• The output shall be a listing of all values of denominators of the smallest set of unit fractions found (or the fractions themselves, i.e. `1/2`).
• The output shall be ordered ascending according to the value of the denominator (descending by the value of the fraction).
• The output can be delimited any way you wish, but there must be some character between so as to differentiate one value from the next.
• This is code golf, so the shortest solution wins.

Exmaples:

• Input 1:

`43, 48`

• Output 1:

`2, 3, 16`

• Input 2:

`8/11`

• Output 2:

`1/2 1/6 1/22 1/66`

• Input 3:

`5 121`

• Output 3:

`33 121 363`

-
Input/Output 2 should be `8, 11` and `2, 6, 22, 66` right? – mellamokb Jun 5 '12 at 21:42
Either/Or; they are equivalent. I'd like to leave the formatting up to the creator of the solution. – Gaffi Jun 5 '12 at 22:45
Is any minimum length fraction OK? For instance, 8/11 is also 1/2+1/5+1/37+1/4070. – Keith Randall Jun 6 '12 at 0:45
I suggest adding `5/121 = 1/33+1/121+1/363` to the test cases. All greedy programs (including mine) give 5 fractions for it. Example taken from Wikipedia. – ugoren Jun 6 '12 at 11:25
@primo I think that if there are multiple minimums, then whichever can be found would be acceptable. If one algorithm can be written with fewer characters as a result, I would not want to hinder that solution. – Gaffi Jun 6 '12 at 11:54

Python, 169167 chars

``````x,y=input()
def R(n,a,b):
if n<2:return[b/a][b%a:]
for m in range((b+a-1)/a,b*n/a):
L=R(n-1,a*m-b,m*b)
if L:return[m]+L
n=L=0
while not L:n+=1;L=R(n,x,y)
print L
``````

Takes comma-separated args on stdin and prints a python list on stdout.

``````\$ echo 8,11 | ./egypt.py
[2, 5, 37, 4070]
``````
-
 1. I think you can save two chars by using tab on the second indentation level. 2. The script doesn't indicate truncation due to exceeding system memory limitations. – breadbox Jun 6 '12 at 17:50

PHP 82 bytes

``````<?for(fscanf(STDIN,"%d%d",\$a,\$b);\$a;)++\$i<\$b/\$a||printf("\$i ",\$a=\$a*\$i-\$b,\$b*=\$i);
``````

This could be made shorter, but the current numerator and denominator need to be keep as whole numbers to avoid floating point rounding error (instead of keeping the current fraction).

Sample usage:

``````\$ echo 43 48 | php egyptian-fraction.php
2 3 16
\$ echo 8 11 | php egyptian-fraction.php
2 5 37 4070
``````
-
Comma operator emulated as useless arguments to printf? I should save this trick somewhere. – GlitchMr Jun 6 '12 at 9:04
I'm pretty sure this is a Greedy Algorithm‌​, so it won't always give the smallest set of fractions. If you run it with input like `5 121` or `31 311`, it will give the wrong answer (after a very long time). – grc Jun 6 '12 at 9:16
@grc 31/311 -> {a[1]->11,a[2]->115,a[3]->13570,a[4]->46422970} – belisarius Jun 6 '12 at 22:06

C, 163 177 chars

6/6: At last, the program now correctly handles truncation in all cases. It took a lot more chars than I was hoping for, but it was worth it. The program should 100% adhere to the problem requirements now.

``````d[99],c,z;
r(p,q,n,i){for(c=n+q%p<2,i=q/p;c?d[c++]=i,0:++i<n*q/p;)q>~0U/2/i?c=2:r(i*p-q,i*q,n-1);}
main(a,b){for(scanf("%d%d",&a,&b);!c;r(a,b,++z));while(--c)printf("%d\n",d[c]);}
``````

The program takes the numerator and denominator on standard input. The denominators are printed to standard output, one per line. Truncated output is indicated by printing a zero denominator at the end of the list:

``````\$ ./a.out
2020 2064
2
3
7
402
242004

\$ ./a.out
6745 7604
2
3
19
937
1007747
0
``````

The denominators in the second example sum to 95485142815 / 107645519046, which differs from 6745 / 7604 by roughly 1e-14.

-
 Again, I think this is a greedy algorithm. – grc Jun 6 '12 at 9:48 The outermost loop explores all possible answers of N denominators before it begins testing answers of N+1 denominators. You can call it greedy, I suppose, but I believe it fulfills the stated problem. – breadbox Jun 6 '12 at 11:57 Sorry, I take that back. It doesn't follow the greedy solution, but I have found that it isn't completely accurate for some input (`31 311` for example). – grc Jun 6 '12 at 12:22 `31 311` overflows, but the program fails to flag it. – breadbox Jun 6 '12 at 12:23

Python, 61 chars

Input from STDIN, comma separated.
Output to STDOUT, newline separated.
Doesn't always return the shortest representation (e.g. for 5/121).

``````a,b=input()
while a:
i=(b+a-1)/a
print"1/%d"%i
a,b=a*i-b,i*b
``````

Characters counted without unneeded newlines (i.e. joining all lines within the `while` using `;`).
The fraction is `a/b`.
`i` is `b/a` rounded up, so I know `1/i <= a/b`.
After printing `1/i`, I replace `a/b` with `a/b - 1/i`, which is `(a*i-b)/(i*b)`.

-
I want to vote this up, since it is so small, but it's just missing that one piece! – Gaffi Jun 6 '12 at 14:35
I want to fix this one piece, but then it won't be so small... I have a feeling I'll just reinvent Keith Randall's solution. – ugoren Jun 6 '12 at 20:14

Common Lisp, 137 chars

``````(defun z(n)(labels((i(n s r)(cond((= n 0)r)((< n(/ 1 s))(i n(ceiling(/ 1 n))r))(t(i(- n(/ 1 s))(1+ s)(cons s r))))))(reverse(i n 2'()))))
``````

(z 43/48) -> (2 3 16)

(z 8/11) -> (2 5 37 4070)

(z 5/121) -> (25 757 763309 873960180913 1527612795642093418846225)

No need to worry about huge numbers, or handling fractional notation!

-