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

Question

How to find a subset of numbers from 2 to 1000 that will give you the max sum under the condition that any two numbers from the subset don't share common prime factors (e.g., 1000 and 500 share the prime factor 2)?

One (maybe easier) variation to the above question: what is the largest number in the subset? We know that 997 is a prime number, and it is easy to rule out 1000 and 998, thus the question becomes whether is 999 in the subset?

Answer 1

Create a graph with nodes {2, ..., 1000}, and edges when nodes have gcd > 1. Solution to this problem is same as finding 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.

Update

As James suggested it is possible to reduce number of nodes in this graph. Lets say that signature of a number N with prime decomposition p1^k1*...*pn^kn is a tuple (p1, ..., pn).

First reduction is to remove nodes when there is nodes with larger value and same signature. That reduces graph to 607 nodes.

Next reduction is to remove node N with signature (p1, ..., pn) if there are nodes with signatures that is decomposition of (p1, ..., pn) and there sum is >= N. That reduces graph to 277 nodes.

From these nodes 73 are isolated nodes (primes > 500.)

Answer 2

I don't know the answer to this, it seems non-trivial to me. Here are a few thoughts.

The sum consists of a variable number of summands, say s₀ + s₁ + ... s_k, where s_i is an integer in the interval [2, 1000]. Now each s_i has a prime-power factorization s_i=(p₁^e1)*(p₂^e2) ... where e_i ≥ 1.

The condition that "that any two numbers from the subset don't share common prime factors" is equivalent to stating that s_i are pairwise relatively prime, i.e. gcd(s_i, s_j)=1 for i ≠ j. Also equivalently, whenever one summand s_i contains a prime p that means that no other summand may contain that prime.

So how do you arrange the primes into summands? One simple rule is immediately obvious. All the primes in [500, 1000] can only appear in the sum alone as individual summands. If they are multiplied by anything else, even the smallest prime 2, the product will be too large. So that leaves the task of arranging the smaller primes. And I don't know they best way to do that. For the sake of completeness I'll provide the following short python program that shows one way.

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

Output is

84972
81447

showing that "strategy 1" is superior.

Superior, but not necessarily optimal. For example, including 1000 seems good, but it forces us to exclude every other even summand and every summand divisible by 5. If we leave 1000 out but include 998 instead, we get to use another summand that includes 5 in it's prime factorization. But including 998 forces other summands to be excluded. So maximizing the sum is not trivial.