*[[Problem 333:http://projecteuler.net/problem=333]] 「特殊分割」 [#bd047677]

あらゆる正の整数は, 各項がいずれも 2&sup{i};x3&sup{j};(i,j≧0)と表されるように分割することができる.

いずれの項も他の任意の項を割り切らないような分割のみを考えよう. ~
例えば, 17 = 2 + 6 + 9 = (2&sup{1};x3&sup{0}; + 2&sup{1};x3&sup{1}; + 2&sup{0};x3&sup{2};) という分割は, 2 が 6 を割り切るので有効でない. 17 = 16 + 1 = (2&sup{4};x3&sup{0}; + 2&sup{0};x3&sup{0};) という分割も, 1 が 16 を割り切るので有効でない. 17 の唯一の有効な分割は 8 + 9 = (2&sup{3};x3&sup{0}; + 2&sup{0};x3&sup{2};) である.

多くの整数は, 1つより多くの有効な分割がある. そのような最初の数である 11 は次の2つの分割がある. ~
11 = 2 + 9 = (2&sup{1};x3&sup{0}; + 2&sup{0};x3&sup{2};)~
11 = 8 + 3 = (2&sup{3};x3&sup{0}; + 2&sup{0};x3&sup{1};)

n の有効な分割の数を P(n) としよう. 例えば, P(11)=2 である.

P(17) のように, 有効な分割が1つのみとなる素数 q だけを考えよう.

P(q)=1 となる素数 q<100 の和は 233 に等しい.

P(q)=1 となる素数 q<1000000 の和を求めよ.


トップ   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS