在我的问题中，我必须编写一个程序来计算所有总和为 1 的唯一单位分数 (1/2 +1/3 + 1/6 = 1)。我目前有 570 个分数，在这种格式中总和为 1，其中数字是分母（这是一个包含 68 个项的示例）：
6,9,11,15,16,20,21,23,30,39,51,55,57,58,60,63,66,75,76,87,93,110,126,144,150,156,180,210,216,220,231,238,240,264,270,275,304,315,330,342,380,403,420,460,462,483,506,513,546,570,575,754,780,783,820,840,861,868,882,975,1127,1274,1332,1368,1406,1482,1519,1534,1947
分母也必须小于 2020。我的方法是使用简单的算法将分数划分到一个列表中，然后先划分分数最少的分数，然后再划分分数较大的分数。我想知道是否有人可以提出任何想法、算法或策略来解决这个问题并制作新的分数。
我使用的方法：
循环遍历起始分数列表 (2,3,6) 并检查它们是否可以分成三个分数，如果不能，则使用 a*(a+b) b*(a+b) 分成两个，其中a 和 b 是与数字相乘的因子。它检查它是否超过限制、已经在列表中或重复。然后我一次又一次地运行它。 我是编码新手，所以我的代码很乱，请给我一些改进的提示。请问我是否要我挑出更小的代码片段作为例子，或者把它剪下来分析。
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)
这实际上是子集和问题（NP复数）的变体。
如果你找到从 2 到 2020 的所有数字的 lcm，你会得到一个分母 (D)，你可以用它来将所有分数表示为正整数。当这些整数的任何子集的和等于 D 时，您将得到相应的分数列表。
例如，如果我们要表示 n 到 10 的所有 1/n 分数，我们首先找到 2,3,4,...10 的 lcm，即 2520。每个 1/n 分数可以是用一个整数表示，您通过将 2520 除以相应的除数来计算：
1/2 = 1260 / 2520
1/3 = 840 / 2520
1/4 = 630 / 2520
1/5 = 504 / 2520
1/6 = 420 / 2520
1/7 = 360 / 2520
1/8 = 315 / 2520
1/9 = 280 / 2520
1/10= 252 / 2520
因此，数字 [1260、840、630、504、420、360、315、280、252] 的任何子集加起来等于 2520 对应于加起来为 1 的相应分数之和。
这里是一个例子（为简单起见使用非常朴素的算法）：
from math import gcd
def lcm(a,b): return a*b//gcd(a,b)
def subSum(A,n):
if not A or n<1: return
if n in A: yield [n]
for i,a in enumerate(A):
yield from ([a]+s for s in subSum(A[i+1:],n-a))
def fracSums(maxDiv):
denom = 1
for f in range(2,maxDiv+1):
denom = lcm(denom,f)
nums = [denom//d for d in range(2,maxDiv+1)]
for ss in subSum(nums,denom):
yield [denom//n for n in ss]
输出：
for sol in fracSums(15):
print("1 ="," + ".join(f"1/{n}" for n in sol))
1 = 1/2 + 1/3 + 1/6
1 = 1/2 + 1/3 + 1/10 + 1/15
1 = 1/2 + 1/4 + 1/6 + 1/12
1 = 1/2 + 1/4 + 1/10 + 1/12 + 1/15
1 = 1/3 + 1/4 + 1/6 + 1/10 + 1/12 + 1/15
您可以使用更好的子集和算法来提高效率，但它仍然是一个具有指数时间分布的复杂问题。
以下是失败的尝试而不是答案。
我已经使用 Z3 求解器 的 Python 包装器z3py 来解决问题。
from z3 import *
maxDenominator = 40
merit_aim = 10
denominators = range(2, maxDenominator + 1)
solver = Solver()
a = [] # array of unit fractions
b = [] # array of inclusion/exclusion Booleans
for d in denominators:
a.append(Q(1, d)) # quotient 1/i
b.append(Bool(f"b{d}"))
# Constraint:
# The sum of included unit fractions must be 1
solver.add(Sum([If(x[0], x[1], 0) for x in zip(b, a)]) == 1)
# Constraint:
# At least merit_aim inclusion variables must be true
solver.add(merit_aim <= Sum([If(x, 1, 0) for x in b]))
if solver.check() == sat:
m = solver.model()
# count the number of inclusion variables set to true
merit = sum([1 if is_true(m[x]) else 0 for x in b])
print(f"fractions: {merit}")
# show the included unit fractions
for d in denominators:
if is_true(m[b[d-2]]):
print(f"+1/{d}")
else:
print(f"No solution with up to {merit_aim} fractions found!")
它在 34 秒内找到以下解决方案：
fractions: 11
+1/4
+1/8
+1/9
+1/10
+1/11
+1/12
+1/15
+1/18
+1/22
+1/24
+1/33
所以，用这个通用的方法来打败题中提到的570分数解是没有希望的。 2018 布尔包含/排除变量导致搜索空间为 2^2018 个条目（约 3 x 10^607）。这是巨大的，除非它可以通过对称破坏或其他一些聪明的方法来修剪。
这篇 paper 2013 年的“总和为 1 的单位分数”预测小于 100 的分母最多有 62 个单位分数。
您似乎正在尝试生成所有总和为分母小于 2020 的唯一单位分数。解决此问题的一种方法是使用递归深度优先搜索算法。
您可以从分数 1/2 开始，递归地建立目标和 1，探索所有可能的路径。在每一步中，您都可以通过添加一个分母较大的单位分数来生成新分数，该单位分数之前未在当前路径中使用过。如果路径之和超过 1，则回溯并尝试不同的单位分数。
这是此方法的示例实现：
def find_unit_fractions(denominators, target_sum):
def dfs(curr_sum, curr_path):
nonlocal unique_fractions
if curr_sum == target_sum:
unique_fractions.add(tuple(sorted(curr_path)))
return
for d in denominators:
if d not in curr_path:
new_sum = curr_sum + Fraction(1, d)
if new_sum > target_sum:
break
dfs(new_sum, curr_path + [d])
unique_fractions = set()
dfs(Fraction(1, 2), [2])
return sorted(unique_fractions)
denominators = range(3, 2020)
target_sum = 1
unique_fractions = find_unit_fractions(denominators, target_sum)
print(len(unique_fractions)) # prints the number of unique unit fractions that sum up to 1
此实现首先初始化一组唯一分数和起点为 1/2，分母为 2。然后，通过添加一个具有较大分母的单位分数，递归搜索所有可能的路径以达到目标总和 1以前没有用过。最后，它返回总和为 1 的唯一分数集。
请注意，这种方法对于大分母可能会占用大量内存，因为它将所有可能的唯一分数存储在一个集合中。您可能需要考虑更高效的数据结构或使用修剪技术来限制探索的路径数量。