A natural number, N, that can be written as the sum and product of a given set of at least two natural numbers, {a1, a2, … , ak} is called a product-sum number: N = a1 + a2 + … + ak = a1 × a2 × … × ak.
For example, 6 = 1 + 2 + 3 = 1 × 2 × 3.
For a given set of size, k, we shall call the smallest N with this property a minimal product-sum number. The minimal product-sum numbers for sets of size, k = 2, 3, 4, 5, and 6 are as follows.
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
Hence for 2≤k≤6, the sum of all the minimal product-sum numbers is 4+6+8+12 = 30; note that 8 is only counted once in the sum.
In fact, as the complete set of minimal product-sum numbers for 2≤k≤12 is {4, 6, 8, 12, 15, 16}, the sum is 61.
What is the sum of all the minimal product-sum numbers for 2≤k≤12000?
若自然数N能够同时表示成一组至少两个自然数{a1, a2, … , ak}的积和和，也即N = a1 + a2 + … + ak = a1 × a2 × … × ak，则N被称为积和数。
例如，6是积和数，因为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，所有最小积和数的和是多少？
解题
k个数的和 == k个数的积
求对应k时候最小的这个数
题目要求2≤k≤12000，时候的最小积数和的和
参考题解中的程序，详解程序注释
Java
package Level3; import java.util.Set; import java.util.TreeSet; public class PE088{ static void run(){ int Kmin = 2; int Kmax = 12000; int sum = 0; Set<Integer> set = new TreeSet<Integer>(); for(int k=Kmin;k<=Kmax;k++){ int minN = getMin(k); if(set.add(minN)) sum+=minN; } System.out.println(sum); } // 找出k对于最小的n static int getMin(int k){ for(int n=k+1;;n++){ if(check(n,n,k)) return n; } } // 一个数拆成成k个数的和或者k个数的积 // prod 乘 // sum 和 // 开始的时候这两个数是相等的 都是 prod 或者sum 拆分成k份 // 这里用到的是递归的方法，当 prod2 = prod1 * a ;sum2 = sum1- a // 下面就可以检测下一轮了 check(prod2,sum2,k-1) // 这里用递归也是因为可能出 8 = 2*2*2*1*1 = 2+2+2+1+1 的形式，乘子中有数相同 的情况 // 结束情况： 乘子是1的时候 sum == k k个1的和就是sum了 // k=1的时候 说明结束了 return prod == sum // 下次递归可进行需要：d<= prod k-1<= sum-d 下面程序很显然的 static boolean check(int prod,int sum,int k){ if(sum <k) return false; if(prod == 1) return sum==k; if(k==1) return prod ==sum; for(int d =2;d<= prod && sum-d>=k-1;d++){ if(prod%d==0){ if(check(prod/d,sum-d,k-1)) return true; } } return false; } // 7587457 // running time=1s577ms public static void main(String[] args){ long t0 = System.currentTimeMillis(); run(); long t1 = System.currentTimeMillis(); long t = t1 - t0; System.out.println("running time="+t/1000+"s"+t%1000+"ms"); } }
n[k]表示minimal product-sum numbers for size=k
n[k]的上界为2*k，因为2*k总是能分解成2*k，然后2*k=k+2+(1)*(k-2)
显然n[k]的下界为k
对于一个数num 因式分解后因子个数为product 这些因子的和为sump
则需要添加的1的个数为num-sump，所以size k=num-sump+product
===============================================
上面说的很好理解
在对于因式分解中
n[k] 是 一个数分解成k个数的和 、k个数的积的最小值
我上面链接中的程序的理解是通过因式分解，不断的缩小n[k]处的值，最终的值就是最小的，但是程序后面的递归理解不透。。。
# coding=gbk import time as time def run2(): kMax = 12000 n = [2*kMax for i in range(kMax)] def getpsn(num,sump,product,start): k = num - sump + product if k < kMax: if num<n[k]: n[k] = num for i in range(start,kMax//num *2): getpsn(num*i,sump+i,product + 1,i) getpsn(1,1,1,2) ans = sum(set(n[2:])) print ans # 7587457 # running time= 0.266000032425 s def run(): kMin = 2 kMax = 12000 res=[] for k in range(kMin,kMax+1): minN = getMinN(k) if minN not in res: res.append(minN) print sum(minN) def getMinN(k): n = k + 1 while(True): if check(n,n,k): return n n +=1 def check(prod,sum,k): if sum<k : return False if prod == 1:return sum==k if k==1 :return prod ==sum for d in range(2,prod): if sum-d>=k-1 and prod%d ==0: if check(prod/d,sum-d,k-1): return True return False t0 = time.time() run2() t1 = time.time() print "running time=",(t1-t0),"s"