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.
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 |