Page 1 of 1

egyptian fractions

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

Re: egyptian fractions

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

Re: egyptian fractions

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


Re: egyptian fractions

Posted: Wed Dec 05, 2018 12:06 am UTC
by ucim
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
by phlip
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
by phillip1882
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
by phillip1882
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])