8
$\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 have a Sieve implementation to generate a list of primes. It's the finding the consecutive sums that is causing me problems.2012-07-26
  • 0
    Are you familiar with the concept of *dynamic programming*?2012-07-26
  • 0
    The concepts, yes. I have done very little other than some experimentation with Erlang a few years ago.2012-07-26
  • 0
    @A.Schulz How would dynamic programming help you here?2012-07-26
  • 0
    @Cocopuffs: Fill out a Table that contains at entry $i,j$ the sum from prime nr. $i$ to prime nr. $j$. Use recursion, then check the entries.2012-07-26
  • 2
    I'm surprised to hear it expressed that a 'sliding window' takes much too long to even begin to cover the problem space. Generating the primes less than $10^6$ should be nearly-instantaneous, finding the partial-sums for a sliding window likewise so, and from there - well, since you have a bound on your total sum, you have an easy upper bound on the length of such a sequence; and a quick exploration, as in Robert Israel's answer, will give a lower bound. From there the search should be easy.2012-07-26
  • 0
    It could be because I was trying to cover the whole space - IE: sliding windows of size 1..N where N = size of the list of primes < 1M2012-07-26
  • 0
    @Kylar How were you computing the sums within your sliding windows? That's almost certainly the key optimization that it sounds like you might be missing - with the 'fast' method the problem is literally an order of magnitude faster.2012-07-26
  • 0
    Hmm. Good point. That gives me something to optimize. Will return later tonight after work.2012-07-26
  • 0
    Haven't forgotten about you guys, just had a crazy work weekend :(. I think I'll have time to test this out tonight.2012-07-30
  • 2
    Steven: Your comment gave me the key to figure out where I was being the most inefficient. I was able to move to a linear time calculation, where I was previously re-calculating the entire window each time, by keeping a previous 0..N I was able to 'slide' much faster. If you post an answer, I'll accept it.2012-07-31
  • 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
    That's great - but how did you get those? If I don't understand the methods for the calculating, I can't build on them later.2012-07-26
  • 0
    @Kylar Please clarify: are you having trouble confirming these two facts, or are you looking to understand how those are useful?2012-07-26
  • 0
    No, I understand how they are useful - I can look at the sum of the first N primes where 536 < N < 547 and find the one closest but less than 1M. And I have no doubt they are correct - but I want to find an efficient way to calculate them. If I just take them and solve the problem without understanding the answer, I'll be back in the same place when I go to solve later problems.2012-07-26
  • 2
    The sum of the first $n$ primes should be on the order of $n^2 \log(n)/2$, which gives you an idea of how many primes to take. In Maple, add(ithprime(i),i=1..547) takes less than .02 seconds.2012-07-26
  • 0
    Hum, I wonder if Maple is an allowed computer language for Project Euler...2012-07-26
  • 0
    Also note that the answer is not necessarily the *first* N consecutive primes.2012-07-26
  • 0
    @Kylar: I was just going to say that. But you don't want me to solve the whole problem, do you?2012-07-26
  • 0
    I'm not actually looking for an answer. I'm looking to learn enough so that I can get the answers myself.2012-07-26
  • 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
    Ok, I get that. If the list contains 2 (first N primes), the list needs to be an even number. Otherwise, it must be odd. That gets rid of 1/2 the problem space. And since I have a good idea of the amount of primes, I can make a set of sliding windows that do the calculations. I can probably answer the question, but I still think there's more learning that I need.2012-07-26
  • 2
    I solved it essentially with brute force, but with a *reduced* brute force along these lines. Ruling out large amounts of the problem space so that you end up with far less that you need to check, though ultimately you are just running through the remaining options. "Brute force" done like this can actually be fairly fast.2012-07-26
  • 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