最大合計を与える数値のサブセットを見つける

Question

サブセットの2つの数値が共通の素因数を共有しない条件で最大合計を与える2から1000までの数値のサブセットを見つける方法（例えば、1000と500は素因数2を共有します）？

上記の質問に対する1つの（おそらくより簡単な）バリエーション：サブセットの中で最大の数字は何ですか？ 997は素数であり、1000と998を除外するのは簡単なので、サブセットで999かどうかが問題になります。

Answer 1

ノードがgcd> 1のときにノード{2、...、1000}とエッジを持つグラフを作成します。この問題の解決方法は、特定の場合を除いてNP-hardのmaximum-weight independent set problemを見つけることと同じです。このグラフのケースは、Wikipediaのページの一覧のようには見えません。またはlistの場合でもそうです。

更新

ジェームズは、このグラフ内のノードの数を削減することができる示唆したように。素数分解p1^k1*...*pn^knを持つ数Nの署名はタプル(p1, ..., pn)です。

大きな値と同じシグネチャを持つノードがある場合、最初の削減はノードを削除することです。これは、グラフを607ノードに減らします。

次に還元は(p1, ..., pn)の分解があるシグネチャを持つノードが存在する場合、署名(p1, ..., pn)とノードNを除去することであり、合計は>= Nあります。これは、グラフを277ノードに減らします。これらのノード73から

は孤立ノード（素数> 500）

Answer 2

私はこの答えを知らない、それは私に非自明なようです。ここにいくつかの考えがあります。

和は被加数の可変数で構成され、Sは _K ... S + + S 言い、ここで、iは、_{だ区間[2 1000]の整数です。今はそれぞれI}は、I =（P ^E1）*（P ^E2）... E _I≥1

プライムパワー因数S を有するよ

「サブセットから任意の二つの数字は、共通の素因数を共有しないこと」という条件は、_私は、互いに素対毎のしていることがよ述べると同等である、すなわちGCD（S _I、 _J S）= 1についてi≠jである。同様に、1つのsummandとiにプライムpが含まれている場合は、他のsummandにはプライムが含まれていないことを意味します。

したがって、どのように素数をsummandsに配置しますか？ 1つの単純なルールがすぐに明らかです。 [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)) 

出力は "戦略1" が優れていることを示す

84972 
81447 

です。

優れていますが、必ずしも最適ではありません。たとえば、1000を含むと良いと思われますが、他のすべての偶数およびすべての被加数を5で除算しなければなりません。1000を残して代わりに998を含むと、素因数分解で5を含む別の被加数を使用します。しかし998を含めて、他の要約を除外しなければならない。合計を最大化することは簡単なことではありません。