PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 103 / 特殊和集合:最適化(1)

大きさ n の集合 A の要素の和を S(A) で表す。空でなく共通要素を持たないいかなる 2 つの部分集合 B と C に対しても以下の性質が真であれば,A を特殊和集合と呼ぼう。

  1. S(B)≠S(C); つまり,部分集合の和はすべて異なる
  2. B が C より多くの要素を含んでいれば S(B) > S(C) となる

ある n に対し S(A) が最小化されていれば,それを最適特殊和集合と呼ぼう。はじめの5つの最適特殊和集合は下に与えられる。

  • n = 1: {1}
  • n = 2: {1, 2}
  • n = 3: {2, 3, 4}
  • n = 4: {3, 5, 6, 7}
  • n = 5: {6, 9, 11, 12, 13}

ある最適特殊和集合 A = {a1, a2, ... , an} に対して次の最適特殊和集合は
B = {b, a1+b, a2+b, ... ,an+b} となりそうである。ここで b は前列の「中央の」要素である。

この「法則」を用いると n = 6 に対する最適特殊和集合は
A = {11, 17, 20, 22, 23, 24} で,S(A) = 117 と予期するだろう。しかし,これは最適特殊和集合ではない。n = 6 に対する最適特殊和集合は
A = {11, 18, 19, 20, 22, 25} で, S(A) = 115 である。
これに対応する集合の文字列は 111819202225 である。

n = 7 に対する最適特殊和集合 A に対応する文字列を求めよ。

Problem 103 - Project Euler


まだ解けていませんが,n=7 の特殊和集合は1つ見つかりました。問題文中の方法で n=6 の例から作れます。
{20, 31, 38, 39, 40, 42, 45}

「最適」を調べる方法としては,これを基準として各項をずらしていく多重ループしか思いつきません。mathematica 的にはかなりダサいような気がしますが,いつか書きます。