Egyptian Fractions

Question

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 (2³¹-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

Answer 1

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]

Answer 2

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

Answer 3

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.

Answer 4

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).

Answer 5

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!