## egyptian fractions

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

phillip1882
Posts: 117
Joined: Fri Jun 14, 2013 9:11 pm UTC
Location: geogia
Contact:

### egyptian fractions

Here's my vain attempt to solve.

step 1 If the numerator is larger than the denominator, go to step 4, else go to step 2.
step 2 Divide the denominator by the numerator and round up.
step 3 Multiply the numerator by the value you get from step 2, and place the multiplier in the denominator.
step 4 Subtract the largest denominator value from the numerator, and then place addition of the amount you subtracted in the numerator.
step 5 Distribute the denominator over the two numerator values.
step 6 Remove the common value of the denominator and numerator.
go back to step 2 except only divide against the denominator closest to the numerator, and larger than it.
edit: fixed the miscalculations
exe:

Code: Select all

4131    2*4131      8262          2635 +5627      1      2635       1     3*2635      1     7905
----- =>-------- => -------- =>  ------------- => --- +  ------ => --- +--------- => --- +------ =>
5627    2*5627      2*5627        2*5627           2     2*5627     2     6*5627      2   6*5627

1      2278+5627      1     1    2278       1     1     6834       1    1    1207+5627    1    1    1      1207
--- + ------------- =>--- + --- +------- => --- + --- +  ------  =>--- + --- +------- => --- + --- +--- + --------- =>
2      6* 5627        2     6   6*5627     2     6    18*5627      2    6     18*5627   2     6     18    18*5627

1     1    1      6035          1     1   1    408 +5627    1     1    1     1      408
--- + --- +--- + --------- =>  --- + --- +--- + --------- => --- + --- +--- + ---- + -------- =>
2     6   18    90*5627       2     6    18    90*5627      2     6    18   90    90*5627

1     1    1     1       5713      1     1    1     1       85+5627     1     1    1    1     1       85
--- + --- +--- + ---- + -------- => --- + --- +--- + ---- + --------  =>--- + --- +---  --- + ---- + --------
2     6    18    90  1260*5627    2     6    18    90      1260*5627    2     6   18    90   1260   1260*5627

1     1    1     1     1      1275            1     1    1     1     1        15+1260
--- + --- +--- + ---- +--- + -----------  => --- + --- +--- + ---- +--- + ------------- =>
2     6   18    90   1260   1260*5627         2     6    18    90  1260    15*1260*5627

final:
1     1    1     1     1      1      1
--- + --- +--- + ---- +--- + ----- + ------
2     6    18    90  1260    84405   7090020
Last edited by phillip1882 on Wed Dec 05, 2018 2:44 pm UTC, edited 1 time in total.
good luck have fun

phillip1882
Posts: 117
Joined: Fri Jun 14, 2013 9:11 pm UTC
Location: geogia
Contact:

### Re: egyptian fractions

here's the classic algorithm so you can see the differance.
until you only have 1 in the numerator, subtract the largest fraction with a numerator equal to 1 smaller than the current numerator/denominator

Code: Select all

4131      1      2635       1     1    1921     1     1     1      1360
----- => ---- + ------  => --- + --- + ---- => --- + --- + --- +  ----- =>
5627       2     11254      2     5    56270    2     5     30    1688100

1       1     1    1       1020          1     1     1      1      1
--- + --- + ---- + ---  +  -----     => --- + --- + ---  + ---  + -------
2     5     30   1242   2096620200      2     5     30    1242   2055510
good luck have fun

phillip1882
Posts: 117
Joined: Fri Jun 14, 2013 9:11 pm UTC
Location: geogia
Contact:

### Re: egyptian fractions

here's a second example, only removing common factors after each cycle.

Code: Select all

my algorthim
4143
----
5627

1    2659
--- + -----
2    2*5627

1     1     1175
--- + --- + ------
2     6     3*5627

1     1     1     248
--- + --- + --- + ------
2     6    15    15*5627

1     1     1      1      77
--- + --- + --- + --- + -------
2     6     15   345   345*5627

1     1     1       1      1      8
--- + --- + --- +  --- + ----- +-------
2     6     15    345   28135  345*5627

1     1     1       1      1       1        7
--- + --- + --- +  --- + ----- +------- +---------
2     6     15    345   28135  247588   44*345*5627

1     1     1       1      1       1        1            1
--- + --- + --- +  --- + ----- +------- +--------- +-----------
2     6     15    345   28135  247588   13589205   119585004

classic algorithm

4143
----
5627

1    2659
--- + ----
2    11254

1     1    2041
--- + --- + ----
2     5    56270

1     1     1      439
--- + --- + --- + -------
2     5     28   787780

1     1     1    1       9
--- + --- + --- + ---- + -------
2     5     28   1795   56562604

1     1     1    1        1           1
--- + --- + --- + ---- + ------- +-------------
2     5     28   1795   6284734  177740460243668

good luck have fun

ucim
Posts: 6680
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

### Re: egyptian fractions

An algorithm will give you [b]one[/i] expression. But Egyptian fractions are not unique representations, so a different algorithm may well give you a different expression for the same rational number. That's not a bug.

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Please help addams if you can. She needs all of us.

phlip
Restorer of Worlds
Posts: 7562
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

### Re: egyptian fractions

There is a slight problem that:
1/2 + 1/6 + 1/18 + 1/126 + 1/1008 + 1/39389 + 1/1142281 + 1/164488464 = 12343/16881 ≠ 4131/5627

You should probably double-check your numbers... there's two arithmetic errors in your first line alone.

What is the purpose here? Are you just doing this for fun, or do you have some goal in mind? What proof do you have that your algorithm (a) always eventually finishes, and (b) always gives a correct result? How do the results compare to the standard algorithm... when would you want to use one over the other?

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

phillip1882
Posts: 117
Joined: Fri Jun 14, 2013 9:11 pm UTC
Location: geogia
Contact:

### Re: egyptian fractions

my goal is to have an algorithm that doesn't explode the denominator.

i'm not sure how to prove that it always finishes.

generally you use it when you want a smaller denominator in exchange for more fractions.
good luck have fun

phillip1882
Posts: 117
Joined: Fri Jun 14, 2013 9:11 pm UTC
Location: geogia
Contact:

### Re: egyptian fractions

here's some python code so you can try different values.
edit: slighty modified my version to handle some edge cases. edit: fixed small bug.

Code: Select all

def myegypt(top,bottom,num,denom):
egypt = []
while top > 0:
i = 0
while denom[i] < top:
i+=1
if denom[i]%top == 0:
denom[i] =denom[i]//top
val = 1
for j in range(0,len(denom)):
val*=denom[j]
egypt += [val]
break
factor = denom[i]//top +1
top = factor*top
top = top-denom[i]
val = 1
if i == 0:
denom = [factor]+denom
for j in range(0, len(denom)):
if j ==i+1:
pass
else:
val *= denom[j]
else:
denom[i-1] *= factor
for j in range(0,len(denom)):
if i == j:
pass
else:
val *= denom[j]
egypt += [val]
print(egypt)

def classicegypt(top,bottom,num,denom):
i = 0
while top > 1:
remain = denom[i]%top
if remain == 0:
denom = [denom[i]//top]+denom
denom.pop(-1)
break
else:
factor = denom[i]//top +1
top = factor*top -denom[i]
i += 1
denom = [factor] +denom
denom[i] *= factor
print(denom)

classicegypt(4131,5627,[4131],[5627])
myegypt(4131,5627,[4131],[5627])
good luck have fun

Return to “Coding”

### Who is online

Users browsing this forum: No registered users and 10 guests