散读 | 埃及分数和Graham猜想

埃及分数: 古埃及的分数中, 分子只能为1, 比如, 他们没有 3/4, 若要表达 3/4, 则需要表示成 1/4+1/2

from fractions import Fraction


def greedySearch(frac, rstList):
    if frac.numerator == 1 and frac not in rstList:
        return frac
    else:
        return Fraction(1, int(frac.denominator / frac.numerator)+1)


def greedySum2One(initFrac):
    rstList = [initFrac]
    initFrac = 1 - initFrac
    while initFrac != 0:
        rstList.append(greedySearch(initFrac, rstList))
        initFrac -= rstList[-1]
    return rstList


def greedySum2Any(targetFrac):
    rstList = []
    if targetFrac.numerator == 1:
        return rstList.append(targetFrac)
    else:
        remainFrac = targetFrac
        while remainFrac != 0:
            rstList.append(greedySearch(remainFrac, rstList))
            remainFrac -= rstList[-1]
        return rstList


def printResult(rstList, rst):
    denoList = sorted([frac.denominator for frac in rstList])
    for i in denoList[:-1]:
        print('1/{}'.format(i), end=' + ')
    print('1/{} = {}'.format(denoList[-1], rst))


if __name__ == '__main__':
    initDeno = input('(input an integer greater than one)\nThe initial Fraction is 1/')
    result = greedySum2One(Fraction(1, int(initDeno)))
    printResult(result, 1)
    print()
    targetFrac = input('(input any fraction like `&/&`)\nThe target Fraction is ').split('/')
    targetFrac = Fraction(int(targetFrac[0]), int(targetFrac[1]))
    result = greedySum2Any(targetFrac)
    printResult(result, '{}/{}'.format(targetFrac.numerator, targetFrac.denominator))

"""
sample run:

(input an integer greater than one)
The initial Fraction is 1/3
1/2 + 1/3 + 1/6 = 1

(input any fraction like `&/&`)
The target Fraction is 7/15
1/3 + 1/8 + 1/120 = 7/15
"""