10
$\begingroup$

In Project Euler problem $50,$ the goal is to find the longest sum of consecutive primes that add to a prime less than $1,000,000. $

I have an efficient algorithm to generate a set of primes between $0$ and $N.$

My first algorithm to try this was to brute force it, but that was impossible. I tried creating a sliding window, but it took much too long to even begin to cover the problem space.

I got to some primes that were summed by $100$+ consecutive primes, but had only run about $5$-$10$% of the problem space.

I'm self-taught, with very little post-secondary education.

Where can I read about or find about an algorithm for efficiently calculating these consecutive primes?

I'm not looking for an answer, but indeed, more for pointers as to what I should be looking for and learning about in order to solve this myself.

  • 0
    I was able to calculate from 0..600 sliding windows in linear time, about 2 minutes. The real problem was it took nearly 2 minutes to calculate all the primes under 1M. (this is in python).2012-07-31

4 Answers 4

1

I used the mathematica code:

list = {}; Do[  a = Sum[Prime[i], {i, k, j}];  If[900000 < a <= 1000000 && PrimeQ[a],   AppendTo[list, {k, j, a}]],  {k, 1, 1000}, {j, 1, 1000}] 

and then.

Sort[list, #1[[3]] < #2[[3]] &]. 

This seems very inefficient, but it was pretty quick. I found that among the sequences of the first 1000 primes, the greatest prime sum was from 459 to 695, with a value of 999749. This is probably not what you're looking for since I don't really consider mathematica to be programming.

Btw, would it be an interesting to ask how many ways a number can be summed as the sum of consecutive primes?

4

The sum of the first 536 primes is $958577$ which is prime. The sum of the first 547 primes is $1001604$. That leaves a small number of possibilities to check.

  • 0
    @WillieWong, from what I've seen of Project Euler, just looking at a page in OEIS is considered fair game.2012-07-26
4

To flesh out a comment: the key insight for speeding up this problem is that by using $O(n)$ space, the intermediate sums can be calculated in constant time each: $S_{m,n} = S_{1,n}-S_{1,(m-1)}$, so storing partial sums from $1$ to $i$ lets all other partial sums be easily computed. This removes an $O(n)$ factor from the running time and makes the problem much more tractable.

  • 0
    Thanks! This was the one that got me where I needed to be.2012-08-03
3

Small speed up hint: the prime is clearly going to be odd, so you can rule out about half of the potential sums that way.

If you're looking for the largest such sum, checking things like $2+3,5+7+11,\cdots$ is a waste of time. Structure it differently so that you spend all your time dealing with larger sums. You don't need most of the problem space.

Hopefully this isn't too much of an answer for you.

  • 0
    This was super helpful as an optimization - but it was Steven Stadnicki who pointed out the real issue with my algorithm.2012-07-31