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
• A possible suggestion, to remove abiguity, would be to require the smallest set of unit fractions with the smallest final denominator. For example, 1/2 1/6 1/22 1/66 would be preferable 1/2 1/5 1/37 1/4070 for the input 8/11. – primo Jun 6 '12 at 9:08
• 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

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!

• (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) Show not result in tio... What I have to use for print the result? – RosLuP Oct 29 '17 at 10:06
• (print (z 103/333) ) return one list of 5 numbers but would exist one list of 4 numbers as: 1/4,1/18,1/333,1/1332. So the above function would not return the minimum. – RosLuP Oct 30 '17 at 5:38

Python 2, 169 167 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.

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 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. – Konrad Borowski 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->11,a->115,a->13570,a->46422970} – Dr. belisarius Jun 6 '12 at 22:06

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

C, 94 bytes

n,d,i;main(){scanf("%i%i",&n,&d);for(i=1;n>0&++i>0;){if(n*i>=d)printf("%i ",i),n=n*i-d,d*=i;}}


Try It Online

edit: A shorter version of the code was posted in the comments so I replaced it. Thanks!

• Hello, and welcome to the site! This is a code-golf competition, so the objective is to make your code as short as possible. It looks like there are lots of things you could do to make your code shorter. For example, you could removed all the unnecessary whitespace from your answer. – DJMcMayhem Oct 25 '17 at 23:08
• @DJMcMayhem Thank you sir, understood and done. – うちわ 密か Oct 26 '17 at 6:37
• Hi, welcome to PPCG! Could you perhaps add a TryItOnline-link with test code for the test cases in the challenge? Also, some things you could golf: for(i=2;n>0&&i>0;i++) can be for(i=1;n>0&++i>0;); the brackets of the for-loop can be removed (because it only has the if inside); d=d*i; can be d*=i;; and I'm not entirely sure, but I think #include <stdio.h> can be without spaces: #include<stdio.h>. Oh, and it might be interesting to read Tips for golfing in C and Tips for golfing in <all languages> – Kevin Cruijssen Oct 26 '17 at 7:03
• @KevinCruijssen Thanks for the tips. – うちわ 密か Oct 26 '17 at 20:50
• – Jonathan Frech Oct 26 '17 at 21:04

Stax, 18 bytes

é├WüsOΩ↨÷╬6H╒σw[▐â


Run and debug it

At each step, it tries to minimize the subsequent numerator. It seems to work, but I can't prove it.

Axiom, 392 bytes

f(x,n)==(y:=x;a:List FRAC INT:=[];for i in n..repeat(1/i>y=>1;a:=concat(a,1/i);y:=y-1/i;y=0=>break;numer(y)=1=>(a:=concat(a,y);break);i:=floor(1/y);i>1.e99=>(a:=[];break));a)
h(x:FRAC INT):List FRAC INT==(a:List FRAC INT:=[];x>1=>a;n:=max(2,floor(1/x));m:=999;d:=n+10*m;for i in n..d repeat(b:=f(x,i);c:=maxIndex(b);c~=0 and (c<m or(c=m and m<999 and b.m>a.m))=>(m:=c;a:=b));reverse(sort a))


The idea would be apply the "Greedy Algorithm" with different initial points, and save the list that has minimum length. Ungolfed and test

fracR(x,n)==
y:=x;a:List FRAC INT:=[]
for i in n.. repeat
1/i>y=>1
a:=concat(a,1/i)
y:=y-1/i
y=0       =>break
numer(y)=1=>(a:=concat(a,y);break)
i:=floor(1/y)
i>1.e99   =>(a:=[];break)
a

-- Return one List a=[1/x1,...,1/xn] with xn PI
-- with   x=r/s=reduce(+,a)
Frazione2SommaReciproci(x:FRAC INT):List FRAC INT==
a:List FRAC INT:=[]
x>1=>a
n:=max(2,floor(1/x))
m:=999
d:=n+10*m
for i in n..d repeat
b:=fracR(x,i)
c:=maxIndex(b)
c~=0 and (c<m or (c=m and m<999 and b.m>a.m))=>(m:=c;a:=b)
reverse(sort a)

---------------------------------------------------------------

(5) -> [[i,h(i)] for i in [43/48,8/11,5/121]]

43  1 1  1     8  1 1  1  1     5    1  1    1
(5)  [[--,[-,-,--]],[--,[-,-,--,--]],[---,[--,---,----]]]
48  2 3 16    11  2 6 33 33    121  25 825 9075
Type: List List Any
(6) -> h(124547787/123456789456123456)
(6)
1             1                         1
[---------, ---------------, ---------------------------------,
991247326  140441667310032  613970685539400439432280360548704
1
-------------------------------------------------------------------]
3855153765004125533560441957890277453240310786542602992016409976384
Type: List Fraction Integer