// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (12 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 249 Solution

Project Euler 249 Solution

Project Euler 249: Prime Subset Sums


Problem Description

Let S = {2, 3, 5, …, 4999} be the set of prime numbers less than 5000.

Find the number of subsets of S, the sum of whose elements is a prime number.
Enter the rightmost 16 digits as your answer.

Analysis

This problem is easy to conceptualize but difficult to get to run under one minute. I stuck with Python and there is room for optimization but it may still be a challenge. I’ll get back to it someday, which is programmer speak for “It works and I’ve got much better things to do.”

Project Euler 249 Solution

Runs < 77 seconds in Pypy.
from Euler import prime_sieve, is_prime

primes = prime_sieve(5000)
t = [1] + [0] * sum(primes)

sp = 0
for p in primes:
    sp += p
    for j in range(sp, p-1, -1):
        t[j] = (t[j] + t[j-p])

print "Project Euler 249 Solution =", (sum(t[p] for p in range(sp) if is_prime(p)) % 10**16)
download arrowUse this link to get the Project Euler 249 Solution Pypy source.

Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
|9275262564250418|

Afterthoughts

  • Pypy can shave off 40 seconds from the run time. Still too long.

Full answer:

18089131734384088361396707178609119521538648663874965565252
81728260738457913373744890199439933572129728883223063765155
24683070889481179665713632474523500808965429134707479096569
03114415927526256425xxxx

replace the last four x’s with the last four digits of your answer.

Project Euler 249 Solution last updated

Discussion

No comments yet.

Post a comment