## egyptian fractions

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

Moderators: phlip, Moderators General, Prelates

phillip1882
Posts: 141
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*56271     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*5627final: 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: 141
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    16881001       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: 141
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 algorthim4143---- 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*56271     1     1       1      1       1        1            1--- + --- + --- +  --- + ----- +------- +--------- +----------- 2     6     15    345   28135  247588   13589205   119585004classic algorithm4143---- 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: 6827
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 * Heartfelt thanks from addams and from me - you really made a difference.

phlip
Restorer of Worlds
Posts: 7569
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: 141
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: 141
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