找到会给你最大和的数字子集

Question

如何找到从 2 到 1000 的数字子集，在子集中的任何两个数字不共享质因数（例如，1000 和 500 共享质因数）的情况下，该子集将为您提供最大和2)?

上述问题的一个（可能更简单）变体：子集中最大的数是多少？我们知道997是素数，很容易排除1000和998，那么问题就变成了999是否在子集中？

Answer 1

创建一个包含节点 {2, ..., 1000} 和当节点 gcd > 1 时的边的图。此问题的解决方案与查找 maximum-weight independent set problem, which is NP-hard except in some special cases. This graph case doesn't look like a spacial case from list on Wikipedia page or even on this list.

相同

更新

正如 James 所建议的那样，可以减少此图中的节点数量。假设具有素数分解 p1^k1*...*pn^kn 的数字 N 的签名是一个元组 (p1, ..., pn).

第一个归约是当存在具有更大值和相同签名的节点时删除节点。这将图形减少到 607 个节点。

如果有节点的签名是 (p1, ..., pn) 的分解并且总和是 >= N，则下一个缩减是删除节点 N 和签名 (p1, ..., pn)。这将图形减少到 277 个节点。

这些节点中有 73 个是孤立节点（素数 > 500。）

Answer 2

我不知道这个问题的答案，这对我来说似乎很重要。这里有一些想法。

总和由可变数量的被加数组成，比如 s₀ + s₁ + ... s_k，其中s_i为区间[2, 1000]内的整数。现在每个 s_i 都有素数幂分解 s_i=(p₁^e1)*(p₂^e2) ... 其中 e_i ≥ 1.

条件"that any two numbers from the subset don't share common prime factors"等价于说明s_i成对互质，即gcd(s_i , s_j)=1 因为 i ≠ j。同样等价地，每当一个加数 s_i 包含质数 p 时，这意味着没有其他加数可能包含该质数。

那么如何将质数排列成被加数呢？一个简单的规则是显而易见的。 [500, 1000] 中的所有质数只能作为单独的被加数单独出现在总和中。如果将它们乘以任何其他值，即使是最小的素数 2，乘积也会太大。这样就留下了安排较小素数的任务。我不知道他们这样做的最佳方式。为了完整起见，我将提供以下显示一种方法的简短 python 程序。

def sieve_prime_set(n):
    # sieve[i] = set(p1, p2, ...pn) for each prime p_i that divides i.

    sieve = [set() for i in range(n + 1)]
    primes = []
    next_prime = 1
    while True:
        # find the next prime
        for i in range(next_prime + 1, len(sieve)):
            if not sieve[i]:
                next_prime = i
                break
        else:
            break

        primes.append(next_prime)
        # sieve out by this prime
        for kp in range(next_prime, n + 1, next_prime):
            sieve[kp].add(next_prime)

    return sieve, primes

def max_sum_strategy1(sieve):
    last = len(sieve) - 1
    summands = [last]
    max_sum = last
    prime_set = sieve[last]
    while last >= 2:
        last -= 1
        if not sieve[last] & prime_set:
            max_sum += last
            prime_set |= sieve[last]
            summands.append(last)

    return max_sum, summands, prime_set

def max_sum_strategy2(primes, n):
    return sum(p ** int(log(n, p)) for p in primes)



if __name__ == '__main__':
    sieve, primes = sieve_prime_set(1000)
    max_sum, _, _ = max_sum_strategy1(sieve)
    print(max_sum)
    print(max_sum_strategy2(primes, 1000))

输出是

84972
81447

表明 "strategy 1" 更胜一筹。

优秀，但不一定是最佳的。例如，包含 1000 似乎不错，但它迫使我们排除所有其他偶数加数和每个可被 5 整除的加数。如果我们将 1000 排除在外但包含 998，我们将使用另一个包含 5 的素数分解。但是包括 998 会强制排除其他加数。因此，最大化总和并非易事。

Answer 3

这里有一个 Python 脚本来解决这个问题。在我的笔记本电脑上运行需要几分钟。

import math
import networkx as nx

max_number = 1000

G = nx.Graph()

for i in range(2, max_number + 1):
    G.add_node(i, weight=i)

for i in range(2, max_number + 1):
    for j in range(i+1, max_number + 1):
        if math.gcd(i, j) == 1:
            G.add_edge(i, j)

numbers, sum_of_numbers = nx.max_weight_clique(G)

print(sorted(numbers))
print(sum_of_numbers)

返回的号码列表如下所示；总数是 85684。（可能还有其他有效的数字集给出了这个总数。）

[41, 59, 67, 71, 79, 83, 97, 101, 103, 107, 113, 127, 131, 137, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 841, 853, 857, 859, 863, 877, 881, 883, 887, 893, 901, 907, 911, 919, 925, 929, 937, 941, 947, 949, 953, 961, 967, 971, 973, 976, 977, 979, 981, 983, 989, 991, 997]

找到会给你最大和的数字子集

Finding a subset of numbers that will give you the max sum

math

primes

max

combinatorics

subset-sum