积和数

若自然数n能同时表示成一组至少两个自然数$\{a_1,\ldots,a_k\}$的积与和，也即： $$n=a_1+\ldots+a_k=a_1\times\ldots\times a_k,$$ 则称n为积和数。例如$6=1+2+3=1\times 2\times 3$是积和数。

给定这一组自然数的数量k，满足上述性质的最小n称为最小k积和数。当k取2到6时，对应的最小k积和数如下：

$k=2$时，$n=4=2+2=2\times 2$。

$k=3$时，$n=6=1+2+3=1\times 2\times 3$。

$k=4$时，$n=8=1+1+2+4=1\times 1\times 2\times 4$。

$k=5$时，$n=8=1+1+2+2+2=1\times 1\times 2\times 2\times 2$。

$k=6$时，$n=12=1+1+1+1+2+6=1\times 1\times 1\times 1 \times 2\times 6$。

因此，对于$2\le k\le6$，所有互异的最小k积和数之和为$4+6+8+12=30$，注意8只被计算了一次。

类似地，对于$2\le k\le12$，所有最小k积和数构成的集合是$\{4, 6, 8, 12, 15, 16\}$，这些数的和是61。

对于$2\le k\le12000$，所有互异的最小k积和数之和是多少？

本题难度:

解答

本题较复杂。首先注意到 $$k\times 2\times\underbrace{1\times\ldots\times1}_{k-2 \text{ 项}}=k+2+\underbrace{1+\ldots+1}_{k-2 \text{ 项}}=2k,$$ 因此最小的k积和数不超过2k。从而我们只需搜索24000以内的每个n，并检验其是否是k积和数。对此只需先找出$n$的所有可能的分解，若 $$n=d_1\times\ldots\times d_j,$$ 是一个分解，则只要$d_1+\ldots+d_j\le n$，就可以通过添加$j'=n-(d_1+\ldots+d_j)$个1来得到一个$j+j'$积和数。用动态规划作上述计算可得结果$7587457$。

import math
 
n=12000

answers=[0]*(n+1)
factorizations=[[],[],[[2]],[[3]],[[2,2],[4]],[[5]],[[2,3],[6]],[[7]]]
for c in range(8,2*n+1):
    factors=[]
    for x in [i for i in range(2,int(math.sqrt(c))+1) if c%i==0]:
        factors+=[sorted([b for b in a]+[x]) for a in factorizations[c/x] if a]
    factorizations.append(factors+[[c]])

for x in range(4,2*n+1):
    factors=factorizations[x]
    for p in factors:
        if len(p)>1 and sum(p)<=x:
            i=len(p)+x-sum(p)
            if i<=n and answers[i]==0:
                answers[i]=x
                    
print sum(set(answers))