Page 1 of 1

### egyptian fractions

Posted: Mon Dec 03, 2018 9:46 pm UTC
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`

### Re: egyptian fractions

Posted: Mon Dec 03, 2018 11:45 pm UTC
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`

### Re: egyptian fractions

Posted: Tue Dec 04, 2018 8:39 pm UTC
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`

### Re: egyptian fractions

Posted: Wed Dec 05, 2018 12:06 am UTC
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

### Re: egyptian fractions

Posted: Wed Dec 05, 2018 2:01 am UTC
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?

### Re: egyptian fractions

Posted: Wed Dec 05, 2018 2:55 pm UTC
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.

### Re: egyptian fractions

Posted: Thu Dec 06, 2018 12:01 am UTC
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])`