プロジェクトオイラー 問８８

プロジェクトオイラーの問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。

問８８「積和数」
少なくとも2つの自然数 {a1, a2, ... , ak} の集合の和かつ積として表せる自然数Nを積和数と呼ぶ：N = a1 + a2 + ... + ak = a1 × a2 × ... × ak.
例えば, 6 = 1 + 2 + 3 = 1 × 2 × 3.

ある集合の大きさ k に対して,この性質を持つ最小の N を最小積和数と呼ぼう. 
集合の大きさ k = 2, 3, 4, 5, 6 に対する最小積和数は次のとおりである.
k=2: 4 = 2 × 2 = 2 + 2
k=3: 6 = 1 × 2 × 3 = 1 + 2 + 3
k=4: 8 = 1 × 1 × 2 × 4 = 1 + 1 + 2 + 4
k=5: 8 = 1 × 1 × 2 × 2 × 2 = 1 + 1 + 2 + 2 + 2
k=6: 12 = 1 × 1 × 1 × 1 × 2 × 6 = 1 + 1 + 1 + 1 + 2 + 6

したがって 2≦k≦6 に対して,全ての最小積和数の和は 4+6+8+12 = 30 である. 
8 は和に一度だけカウントされていることに気をつけよう.

実際, 2≦k≦12 に対する最小積和数の完全な集合は {4, 6, 8, 12, 15, 16} なので,その和は 61 である.

2≦k≦12000 に対する全ての最小積和数の和は何か?





注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。






私の回答例は以下の通りです。

def f(N):
	L, M, maxn = [0]*(N+1), [2], int(1+(N-1)**(0.5))
	while M[0]<=maxn:
		n = reduce(lambda x,y:x*y, M)
		k = n-sum(M)+len(M)
		if 1<k<=N and not(0<L[k]<n): L[k]=n
		if k<=N: M.append(M[-1])
		else: M = M[:-2]+[M[-2]+1]
		
	L = set(L)
	return L, sum(L)
	
n = 12000
L, s = f(n)
print s

まず、例を手計算してもう少し進めてみました。
項目数k、最小積和数n、項目のリストMとして以下の通りです。
 k   n  M
 2:  4: 2,2
 3:  6: 1,2,3
 4:  8: 1,1,2,4
 5:  8: 1,1,2,2,2
 6: 12: 1,1,1,1,2,6
 7: 12: 1,1,1,1,1,3,4
 8: 12: 1,1,1,1,1,2,2,3
 9: 15: 1,1,1,1,1,1,1,3,5
10: 16: 1,1,1,1,1,1,1,1,4,4
11: 16: 1,1,1,1,1,1,1,1,2,2,4
12: 16: 1,1,1,1,1,1,1,1,2,2,2,2

和と積が同じとのことで項目に1がたくさんあるのは明らかです。
そこで、1と1以外に分けて、1以外の要素だけに注目します。
積和数は（1以外の要素積）です。
項目数は（1の要素数）＋（1以外の要素数）です。
ここで、1の要素数は（積和数）－（1以外の要素和）なので、
項目数は（1以外の要素積）－（1以外の要素和）＋（1以外の要素数）です。

次に、1以外の要素リストを昇順に並べてみます。
 k  M
 2: 2,2
 5: 2,2,2
12: 2,2,2,2
 8: 2,2,3
11: 2,2,4
 3: 2,3
 4: 2,4
 6: 2,6
 7: 3,4
 9: 3,5
10: 4,4
以上より、以下のルールで要素リスト候補を作り出します。
・項目数が項目数上限以内ならば、末尾の要素を新要素として追加する。
・項目数が項目数上限を超過したら、末尾要素を削除しておき、新末尾値を＋１する。
　または最後から2個目の値を＋１してここまでのリストにします。

上記の要素リスト候補に対して採用可否を判定することにします。

さらに問題文では要素数kの範囲が指定されますが、
要素リストをどこまで作成するかの限界を決めるために
項目数kのときの最小積和数の上限を求めておきます。
上限のとき、[1, 1, ..., 1, p, p]になります。1の個数は(k-2)個です。
このときの積和数は積＝和なので、
p*p = k-2+p+p
p2 - 2p - (k-2) = 0
pの二次方程式として解いて、正の値をとると以下のとおりです。
p = 1+√(k-1)



１．関数f(N)
・項目数が2以上N以下の最小積和数の重複削除したリストとその和を求めます。

・L, M, maxn = [0]*(N+1), [2], int(1+(N-1)**(0.5))
　L:項目数ごとの最小積和数リスト
　M:1以外の項目リスト候補(要素は昇順)
　maxn:項目値の上限
　です。
　リストLは0クリアしておき最小積和数を設定していきます。
　
・while M[0]<=maxn:
　項目リスト候補Mの最初の値が項目値上限以内なら処理を続けます。

・n = reduce(lambda x,y:x*y, M)
　積和数nは、リストMの要素の積です。
　lambda関数で引数x,yを受け取り、その積x*yを返す無名関数を作り、
　reduce関数でリストMの要素を1つずつ累積的に上記関数に掛けていくことでリストMのすべての要素の積を求めます。

・k = n-sum(M)+len(M)
　項目数kは、（1以外の要素積－1以外の要素和=1の要素数）＋1以外の要素数　です。

・if 1<k<=N and not(0<L[k]<n): L[k]=n
　採用可否の判定です。
　要素数が2以上N以下で、積和数リストLに新規設定または現値より小さければ設定します。

・if k<=N: M.append(M[-1])
　else: M = M[:-2]+[M[-2]+1]
　次の候補を作成します。
　項目数＜項目数上限の場合、末尾の要素を追加します。
　項目数≧項目数上限値なら、末尾要素を削除しておき、新末尾値を＋１する。
　つまり、最後から2個目の値を＋１してここまでのリストとします。

・L = set(L)
　set関数でリストLの値をユニークにします。


解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
7587457