【Project Euler】Problem 88: 積和数

• 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題 88.積和数

原文 Problem 88: Product-sum numbers

問題の要約：要素の積と和が一致するような$k$個の自然数の集合で、$k$に対する積和数の最小値をmps(k)としたとき$2 \le k \le 12000$でのmps(k)の合計を求めよ。ただしmps(k)の値が重複するものは数えない

• 例えば$k = 2,3,4,5,6$の時の積和数の最小値は以下のようになり、その合計は重複する8を除いて30となる。

さすがに難易度が今まで最高の40%だけあって、難しいです。ポイントとしては、

• $k$に注目して最小値を求めるのではなく、積の因数を並べて積と和を求め、そこから$k$を出すと考えた方が探索しやすい。
• 例でいえば$2 \times 3$のように因数が決まると、以下のようにkも決まる。
  • $P = 2 \times 3= 6, \ \ S = 2+3 = 5$ なのでsを1つ増やすために1を1つ付けると考える。
  • すると$k |\lbrace 2,3,1 \rbrace| = 3$となる
  • 因数をどんどん発生させてkの最小値を更新していく
• kの値は K = P - S + Fn (Fn は因数の数)で与えられる
  • $P = (2 \times 3 )$の例では $k = (2 /times 3) - (2 + 3) + 2 = 3$
• Pが最大になるのは$P = 2 \times 7$のような場合で$ k= 2 \times 7 - (2 + 7) + 2 = 7$となり、Pの最大値は$2 \times k$

そこで$P < 2 \times kmax$ の範囲内で取り得る因数を列挙してkを求めていくというアルゴリズムを考えます。

例えば$kmax$が$12$の時は以下のような感じです。その上で$P=8$と$10$で$k=5$となるので$k=5$の最小値は$P=8$を取るようにします。

k= 02, P = 04, [2, 2]
k= 05, P = 08, [2, 2, 2, 1, 1]
k= 12, P = 16, [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1]
k= 08, P = 12, [2, 2, 3, 1, 1, 1, 1, 1]
k= 11, P = 16, [2, 2, 4, 1, 1, 1, 1, 1, 1, 1, 1]
k= 03, P = 06, [2, 3, 1]
k= 04, P = 08, [2, 4, 1, 1]
k= 05, P = 10, [2, 5, 1, 1, 1]
：

このような因数の発生を再帰関数で実装します。小さい因数で数を増やしていって$k$が$kmax$を超えたら戻って因数をカウントアップするコードになります。

因数の列挙が出来れば、あとは$k$を計算して$k$の最小値の配列mpsを更新して、最後に重複を除くために、setに変換して合計を取ります。

このコードはなるべく分かりやすさを重視しているので、効率を求めれば改善の余地があります。（PとSは毎回計算している、等）

import itertools
import numpy as np
from copy import copy

def ps(flist, fn): 
  return np.prod(flist[1:fn+1]), sum(flist[1:fn+1])

def prodsum(flist, fn, f0):
  for f in itertools.count(f0):
    flist[fn] = f
    p,s = ps(flist, fn)  
    k = p - s + fn       # product - sum + fact
    if  k > kmax  or (fn==1 and p*f>kmax*2):
      return 
    if fn >= 2:
      print(f"k= {k:02}, P = {p:02}, {list(flist[1:fn+1])+([1]*(p-s))}")
      if p < mps[k]:  mps[k] = p
    prodsum(copy(flist), fn+1, f)
  return 

kmax = 12
flist = np.array([0]* kmax)
mps = [2*kmax] * (kmax+1)
prodsum(flist, 1, 2)   # d: num of digit, m0: next initial digit
print("Answer : ", sum(set(mps[2:])))
# Answer :  61

（開発環境：Google Colab）