All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Egyptian Fraction Expression (Posted on 2022-06-24) Difficulty: 4 of 5
Determine the minimum number of summands for expressing 21/23 as an Egyptian Fraction.

What is the total number of ways of expressing 21/23 for that minimum value?

Note: In the context of the current problem, each of the summands is positive.

See The Solution Submitted by K Sengupta    
Rating: 5.0000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Computer Solution | Comment 1 of 3
Here are the solutions I found, each with 5 fractions.  I am showing each fraction as its reciprocal:
[2, 3, 13, 359, 644046]
[2, 3, 14, 121, 58443]
[2, 3, 15, 77, 17710]
[2, 3, 17, 48, 18768]
[2, 3, 18, 42, 2898]
[2, 3, 23, 28, 1932]
[2, 4, 10, 16, 1840]
[2, 5, 5, 77, 17710]
I cannot prove that this list is complete.

I had little knowledge about Egyptian fractions prior to this problem, but I found a helpful Michael Penn video (link below) which described Fibonacci's algorithm for finding a solution.  Not certain whether or not multiple copies of the same fraction are allowed in the definition (I assume they are), that is how I sought a solution.

I wrote two versions of a function, the first just using the algorithm, and the second allowing one to force certain fractions to be included.  Finally I ran a loop to force the first 3 values and then let the algorithm find the next solution, if any, without using any smaller integers than the 3 it was forced to accept.  The above list is the output of the short "active program" at the very end of this comment.   It is interesting that if I tried to test any integer over 25 as one of the "forced" entries, I got the following Python error in the egyptian() function in the final line of that function where I divided by "mygcd":
"OverflowError: integer division result too large for a float"

=====
import math

def multRecip(aList):
    """  input a list of integers, then 
    add the reciprocals of each integer, then
    show the result as a list of [numerator, denominator]
    """
    aList = [int(i) for i in aList[:]]  # else denom becomes a float
    numer = 0
    denom = 1
    for i,n in enumerate(aList):
        x = aList[:]
        x.pop(i)
        xtemp = 1
        for m in x:
            xtemp *= m
        numer += xtemp
    for n in aList:
        denom *= n
    mygcd = math.gcd(numer,denom)
    numer = int(numer/mygcd)
    denom = int(denom/mygcd)
    return [numer,denom]

def egyptian(x,y):
    """ Use Fibonacci's Algorithm to find Egyptian Fraction sum for x/y
    where x and y are integers
    see Michael Penn's video at  
    https://www.youtube.com/watch?v=vVEcqzjykHU  """
    ans = []
    numer = (-y%x)
    xtemp = x
    ytemp = y
    while xtemp > 0:
        myceil = math.ceil(ytemp/xtemp)
        ans.append(myceil)
        numer = ( (-ytemp) % xtemp)
        denom = ytemp * myceil
        mygcd = math.gcd(numer,denom)
        xtemp = int(numer / mygcd)
        ytemp = int(denom / mygcd)
    return ans

def egyptianForced(x,y, ans=[]):
    """ Produce list of integers the reciprocals of which form an Egyptian
    Fraction equal to x/y   The optional parameter is a list of integers
    which are the first several members of the list.  This algorithm then
    will not include any intgers smaller that the largest member of the 
    elements of the list in the optional input parameter"""
    nTarget=x
    dTarget=y
    if ans == []:
        return egyptian(x,y)
    else:
        largest = max(ans)

    fracSum = multRecip(ans)
    nFrac = fracSum[0]
    dFrac = fracSum[1]
    newN = nTarget * dFrac - dTarget * nFrac
    newD = dTarget * dFrac
    g = math.gcd(newN,newD)
    newN = int( newN / g )
    newD = int( newD / g )
    if newN < 0:
        return []
    elif newN == 0:
        return ans
    
    while newN > 0:
        candidate = int(newD/newN)
        if candidate - largest > 0:
            return ans + egyptian(newN,newD)
        candidate = largest
        fracSum = multRecip(ans + [candidate])
        nFrac = fracSum[0]
        dFrac = fracSum[1]
        newN = nTarget * dFrac - dTarget * nFrac
        newD = dTarget * dFrac
        g = math.gcd(newN,newD)
        newN = int( newN / g )
        newD = int( newD / g )
        if newN > 0:
            ans.append(candidate)
        else:
            fracSum = multRecip(ans)
            nFrac = fracSum[0]
            dFrac = fracSum[1]
            newN = nTarget * dFrac - dTarget * nFrac
            newD = dTarget * dFrac
            g = math.gcd(newN,newD)
            newN = int( newN / g )
            newD = int( newD / g )
            return ans + egyptian(newN,newD)
    return ans

................ active program below
xTest = 21
yTest = 23
big = 25

for i in range(2,big+1):
    for j in range(i,big+1):
        for k in range(j,big+1):
            result = egyptianForced(xTest, yTest, [i,j,k])
            length = len(result)
            if length <= 5 and length > 0:
                print(result)

  Posted by Larry on 2022-06-24 09:22:53
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (7)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information