egyptian fractions

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

Moderators: phlip, Moderators General, Prelates

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

egyptian fractions

Postby phillip1882 » 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*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

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

Re: egyptian fractions

Postby phillip1882 » 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    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

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

Re: egyptian fractions

Postby phillip1882 » Tue Dec 04, 2018 8:39 pm UTC

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

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

Re: egyptian fractions

Postby ucim » 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
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.

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

Re: egyptian fractions

Postby phlip » 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?

Code: Select all

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

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

Re: egyptian fractions

Postby phillip1882 » 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.
good luck have fun

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

Re: egyptian fractions

Postby phillip1882 » 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])
good luck have fun


Return to “Coding”

Who is online

Users browsing this forum: Yahoo [Bot] and 10 guests