HN Explorer

Challenge HN: Inspired by greplin's third problem

14 points by cperciva ↗ HN
Let P = {2, 3, 5, ... 1009, 1013, 1019, 1021} be the set of 172 prime integers less than 2^10. How many subsets S does P have such that the sum of the least |S|-1 elements of S is equal to the largest element of S?

Please list the language used, number of lines of code, and running time (if measurably greater than zero).

7 comments

[ 3.9 ms ] story [ 29.8 ms ] thread
madars
http://codepad.org/5TyD9Jqy -- C++ solution with running time of ~0.004s. 30 lines not counting empty lines/comments/braces, half of the code is generating P.
letronje
how does it work ?
madars
The solution is by dynamic programming.

Let p_1 = 2, p_2 = 3, ..., p_172 = 1021 be the first 172 primes. We will denote the number of subsets of {p_1, p_2, ..., p_k} that sum to n by D(k, n).

We know that D(0, 0) = 1 and D(0, n) = 0 if n > 0.

Also note that D(k, n) = D(k-1, n) + D(k-1, n-p_k). This comes from the fact that each subset S of {p_1, ..., p_k} can either contain p_k or not. If p_k is in S then S\{p_k} sums to n-p_k and there are D(k-1, n-p_k) such S\{p_k}. If p_k is not in S then S is made entirely of elements from {p_1, ..., p_{k-1}}, obviously there are D(k-1, n) such S.

We can use the base case and this recurrence to fill our dynamic programming table D(k, n). The answer to the original problem is D(0, p_1) + D(1, p_2) + ... + D(171, p_172).

My program implements this approach except that it fills D(k, n) by rows and doesn't keep the whole table in memory.

g0
is 14521794174 the answer by any chance? It took 12 hrs