如何生成和为1、分母<2023的最大数量唯一单位分数

我需要编写程序计算所有和为1的唯一单位分数组合（示例：1/2 + 1/3 + 1/6 = 1），要求分母小于2023。目前通过初始列表[2,3,6]循环处理，尝试将分数拆分为3个；若不可行则用公式a*(a+b)、b*(a+b)拆分为2个（其中a*b等于原分母），同时检查新分母是否超限、重复或已存在。但发现仅用拆分2个的算法得到的分数数量更多，想知道原因，同时寻求优化思路、算法及代码改进建议。

现有Python代码如下：

list = [2,3,6]
import random
lastlist = []
foul = 1
global authsuc
global possfracts
global factors

def factorise(x):
    factors1 = []
    for i in range(1, x + 1):
        if x % i == 0:
            factors1.append(i)


def make1d(x):
    global factors

    checks1 = True
    checks2 = True
    checks3 = True
    checks4 = True
    factors = []
    success = False
    for i in range(1, x + 1):
        if x % i == 0:
            factors.append(i)


    if len(factors) > 2:
        x3 = slice(3)
        factors = (factors[x3])

        xx1 = factors[0]

        xx2 = factors[1]

        xx3 = factors[2]

        total = (xx1 + xx2 + xx3)
        sum1 = (total * (x / xx1))
        sum2 = (total * (x / xx2))
        sum3 = (total * (x / xx3))

        possfracts.append(int(sum1))
        possfracts.append(int(sum2))
        possfracts.append(int(sum3))
        possfracts.remove(x)
        for i in possfracts:
            if i in lastlist:
                make1(i)


    else:
        make2(x)

def make1(x):
    global factors

    checks1 = True
    checks2 = True
    checks3 = True
    checks4 = True
    factors = []
    success = False
    for i in range(1, x + 1):
        if x % i == 0:
            factors.append(i)


    if len(factors) > 2:
        x3 = slice(3)
        factors = (factors[x3])

        xx1 = factors[0]

        xx2 = factors[1]

        xx3 = factors[2]

        total = (xx1 + xx2 + xx3)
        sum1 = (total * (x / xx1))
        sum2 = (total * (x / xx2))
        sum3 = (total * (x / xx3))

        possfracts.append(int(sum1))
        possfracts.append(int(sum2))
        possfracts.append(int(sum3))
        possfracts.remove(x)
        for i in possfracts:
            if i in lastlist or i in list:
                make1d(i)


    else:
        make2(x)

def makefracts1(x):

    global factors

    checks1 = True
    checks2 = True
    checks3 = True
    checks4 = True
    factors = []
    success = False
    for i in range(1, x + 1):
        if x % i == 0:
            factors.append(i)



    if len(factors) > 2:

        x3 = slice(3)
        factors = (factors[x3])

        xx1 = factors[0]

        xx2 = factors[1]

        xx3 = factors[2]

        total = (xx1 + xx2 + xx3)
        sum1 = (total * (x / xx1))
        sum2 = (total * (x / xx2))
        sum3 = (total * (x / xx3))

        possfracts.append(int(sum1))
        possfracts.append(int(sum2))
        possfracts.append(int(sum3))
        for i in possfracts:
            if i in lastlist or i in list:
                make1(i)

        auth(x)
    else:
        makefracts2(x)


def make2(x):
    switch = True
    while switch == True:
        f1 = random.randint(1, x)
        f2 = random.randint(1, x)
        fra1 = (f1 * (f1 + f2))
        fra2 = (f2 * (f1 + f2))
        if fra1 not in lastlist or fra2 not in lastlist or fra1 not in list or fra2 not in list: #should I remove the list checker?
            if f1 * f2 == x:

                possfracts.append(fra1)
                possfracts.append(fra2)
                possfracts.remove(x)


                switch = False
def checkdup():
    for i in possfracts:
        if possfracts.count(i) ==2:
            make1(i)
def makefracts2(x):
    switch = True

    while switch == True:
        global fra11
        global fra22
        global fra1
        global fra2

        f1 = random.randint(1,x)
        f2 = random.randint(1,x)
        if f1 * f2 == x:
            fra1 = (f1 * (f1 + f2))
            fra2 = (f2 * (f1 + f2))
            possfracts.append(fra1)
            possfracts.append(fra2)

            switch = False
    for i in possfracts:
        if i in lastlist or i in list:
            make1(i)
    auth2(x)

def auth(k):
    global possfracts
    global authsuc
    authsuc = False
    too_big = False
    alreadythere = False
    at2 = False
    at3 = False
    if len(set(possfracts)) != (len(possfracts)):
        alreadythere = True
    for i in possfracts:
        if i > 2023:
            too_big = True
    for i in possfracts:
        if i in lastlist:
            at2 = True
    for i in possfracts:
        if i in list:
            at3 = True
    if too_big == True or alreadythere == True or at2 == True or at3 == True:
        possfracts = []
        makefracts2(k)
    else:
        for i in possfracts:
            authsuc = True
            lastlist.append(i)
        print(possfracts)
        list.remove(k)
def auth2(k):
    global authsuc
    authsuc = False
    too_big = False
    alreadythere = False
    at2 = False
    at3 = False
    global foul
    foul = []
    if len(set(possfracts)) != (len(possfracts)):
        alreadythere = True
    for i in possfracts:
        if i > 2023:
            too_big = True

    for i in possfracts:
        if i in lastlist:

            at2 = True



    for i in possfracts:
        if i in list:
            at3 = True



    if alreadythere == True or too_big == True or at3 == True or at2 == True:

        lastlist.append(k)
        list.remove(k)
    else:
        for i in possfracts:

            authsuc = True
            lastlist.append(i)
        print(possfracts)
        list.remove(k)

def facts2(y):
    for i in range(1, y + 1):
        if y % i == 0:
            factors1.append(i)
def proof(x):
    x[:] = [1/i for i in x]
    print(sum(x))
def findsmall():
    for i in list:
        factors1 = []
        for x in range(1, i + 1):
            if i % x == 0:
                factors1.append(i)
        if len(factors1) < 3:
            makefracts2(i)
switch = True
while switch == True:

    factors1 = []
    possfracts = []

    if len(list) == 0:

        prooflist = []
        for i in lastlist:
            prooflist.append(i)

        print(list)
        print(len(lastlist))
        print(lastlist)
        proof(prooflist)
        count = 0
        for i in range(2024):
            amount = lastlist.count(i)

            if amount > 1:
                count = count + 1
                print(i)

        print(count)
        proof(prooflist)
        list = lastlist
        lastlist = []
        findsmall()
    pos = int(list[0])
    facts2(pos)

    if len(factors1) < 3:
        makefracts2(pos)
    else:

        makefracts1(pos)

print(len(lastlist))
print(lastlist)

count = 0
for i in range(2000):
    amount = lastlist.count(i)

    if amount > 1:
        count = count + 1
        print (i)

print(count)
proof(lastlist)

一、为什么拆分2个的算法得到更多分数？ #

1. 三分拆分逻辑过于局限：你的三分拆分代码只取了分母的前3个因子来计算新分母，这种固定方式只覆盖了极少部分可行的三分拆分组合，绝大多数可能的拆分路径被直接忽略。
2. 二分拆分的成功率更高：二分拆分的因子对数量远多于你实现的三分拆分的固定组合，且每次拆分稳定将一个分数拆为两个，直接增加分数数量；而三分拆分由于逻辑死板，经常无法生成符合条件的新分母，最终退化为二分拆分。
3. 校验逻辑的影响：三分拆分失败后会尝试二分拆分，但如果二分也失败，会将原分母直接存入lastlist不再处理；而二分拆分本身可选的因子对更多，成功拆分的概率更高，能持续生成新分母。

二、优化思路与算法改进 #

1. 拆分逻辑优化 #

• 通用拆分公式：二分拆分用经典公式1/n = 1/(n+1) + 1/(n(n+1))即可，三分拆分可通过嵌套二分实现（先拆一个分数为两个，再拆其中一个为两个），避免复杂的三分公式。
• 枚举因子而非随机选择：随机找因子会产生大量无效循环，直接枚举分母的所有因子对(a,b)（满足a*b=n），能高效遍历所有可能的拆分方式。
• 去重与剪枝：用集合存储已使用的分母，快速检查重复；若拆分出的分母超过2023，直接跳过该分支。

2. 搜索策略优化 #

• 广度/深度优先搜索：从初始解出发，用队列（BFS）或递归（DFS）递归拆分每个分数，遍历所有可能的拆分路径，记录所有符合条件的组合。
• 避免重复解：用不可变集合（frozenset）存储每个解，避免不同拆分路径生成相同组合的重复统计。

3. 数据结构优化 #

• 用集合替代列表存储已使用的分母，in操作的时间复杂度从O(n)降到O(1)，大幅提升重复检查效率。
• 避免使用全局变量，改用参数传递或类封装状态，减少逻辑混乱。

三、代码改进建议 #

1. 高效生成因子对 #

替换随机找因子的逻辑，直接生成所有符合条件的因子对：

def get_factor_pairs(n):
    pairs = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            pairs.append((i, n // i))
    return pairs

2. 重构拆分函数 #

写一个通用的二分拆分递归函数，支持遍历所有可能的拆分路径：

from fractions import Fraction

def split_fraction(current_set, max_denominator=2023):
    for den in current_set:
        for a, b in get_factor_pairs(den):
            new_den1 = a * (a + b)
            new_den2 = b * (a + b)
            if new_den1 > max_denominator or new_den2 > max_denominator:
                continue
            if new_den1 in current_set or new_den2 in current_set:
                continue
            # 生成新组合
            new_set = current_set.copy()
            new_set.remove(den)
            new_set.add(new_den1)
            new_set.add(new_den2)
            yield new_set
            # 递归拆分新分母
            yield from split_fraction(new_set, max_denominator)

3. 遍历所有可能的解 #

从初始集合开始，用BFS遍历所有拆分结果并去重：

initial_set = {2, 3, 6}
max_den = 2023
all_solutions = set()
all_solutions.add(frozenset(initial_set))

from collections import deque
queue = deque([initial_set])

while queue:
    current = queue.popleft()
    for new_set in split_fraction(current, max_den):
        frozen_new = frozenset(new_set)
        if frozen_new not in all_solutions:
            all_solutions.add(frozen_new)
            queue.append(new_set)

# 验证解的正确性
def verify_solution(sol):
    total = sum(Fraction(1, d) for d in sol)
    return total == Fraction(1, 1)

# 输出指定大小的解（比如570个分母的解）
for sol in all_solutions:
    if len(sol) == 570 and verify_solution(sol):
        print(sol)

4. 替换浮点验证为精确分数运算 #

使用fractions.Fraction类进行分数运算，完全避免浮点精度误差，确保验证结果准确。

四、其他注意事项 #

• 内存优化：如果需要处理大量解，可按需存储，避免一次性存储所有解导致内存溢出。
• 并行处理：拆分过程可以并行化，利用多线程或多进程加速遍历。

内容的提问来源于stack exchange，提问作者Denlolsauce