We have now reached the bottom of the first page of the Project Euler problems. Problem 50 is all about primes as we are supposed to use primes to generate a new prime. The problem reads

The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

Unless we do something to avoid it we would have a lot of numbers to search through.

## Cumulative sum of Primes

However by building a cumulative sum of primes we avoid having to add up numbers all the time. Just to explain the idea in it simplicity we have a list of primes and the cumulative sum just below

p | 2 | 3 | 5 | 7 | 11 | 13 |

f(p) | 2 | 5 | 10 | 17 | 28 | 41 |

That means we can rather easily calculate say the sum of primes between 5 and 11 which is 5+7+11 = 23. Or we can calculate it as being f(11) – f(3) = 28-5 = 23 by using the cumulative sum.

First step of the algorithm is to generate a list of primes all primes up to 1.000.000 and make a cumulative sum. I am pretty sure that the cumulative sum looks a lot like the ski jump shown to the right, and that the it rises to the sky pretty quickly.

## Searching for the greatest sum

In order to search for the prime with the given property I used two nested loops. The outer loop (i) counted upwards through the cumulative sum, and the inner loop (j) counted downwards starting from the current index of the outer loop. This is still a lot of candidates to go through so I used two things to speed the search up a bit.

First of all a large part of the cumulative sum is greater than 1.000.000 and subtracting something from it might also be also be larger than the limit. By the construction of the loops I know that as soon as f(i) – f(j) > 1.000.000 I can break out of the inner loop.

One further thing is that I mentioned I started with j = i -1, but that isn’t necessary. If we have already found a prime which consists of n consecutive primes we might as well start from j = i-n-1.

## The C# algorithm

With these two tricks we are ready to code it

const int limit = 1000000; long result = 0; int numberOfPrimes = 0; long[] primes = ESieve(1,limit); long[] primeSum = new long[primes.Length+1]; primeSum[0] = 0; for (int i = 0; i < primes.Length; i++) { primeSum[i+1] = primeSum[i] + primes[i]; } for (int i = numberOfPrimes; i < primeSum.Length; i++) { for (int j = i-(numberOfPrimes+1); j >= 0; j--) { if (primeSum[i] - primeSum[j] > limit) break; if (Array.BinarySearch(primes, primeSum[i] - primeSum[j]) >= 0) { numberOfPrimes = i - j; result = primeSum[i] - primeSum[j]; } } }

The code starts out by generating the cumulative sum, and then enters the main loop where it searches for primes.

The code executes as

Largest primes below 1000000 written as consequtive primes is 997651 It consists of 543 primes Solution took 11 ms

I wondered why it took 11ms and considered if I could get a speed up one way or another, so I tried a few different approaches, until I discovered that the 10ms are spent on generating the primes. So spending 1ms for searching through the primes is not something I will try to optimize a whole lot more on.

## Wrapping up

First of all thanks to Roger4336 for sharing his photo under the creative commons license. My alteration of the photo is of course under the same license.

This was the first 50 problems solved. So far we have we have generated a whole lot of useful functions for solving the next many problems. As usual you can find the source code for the whole problem.

If you have questions, comments or another solution approach please let me know. I am curious to see what other people did. Let me ask a questions – How did you solve it?

Congratulations on your 50th Project Euler post!

But I’m too embarrassed to post my solution for this problem.

It’s horrible.

Thank you, only a couple of hundred to go 🙂

I wonder how horrible your solution can possibly be. I would like to hear more about your solution strategy? Was it pure brute force, or did you have some kind of structure?

It was pure brute force… I recalculated the whole sum every time.

This is the only part I’ll post:

I assume that the solution will be found in under 30 seconds. (This might break on a slow computer :D)

But after I read the problem description at the top of this post, the first thing that came into mind was a kind of sliding-sum, which is basically what you did.

But I’m constantly learning new things by doing Project Euler problems, and then reading the forum or stuff on the web, like your blog.

So it’s no surprise to me that some of my old solutions seem obscure to me now.

Great. By using the sieve of atkin, you can probably get it down a bit more. My approach was slightly different, just add up all primes (until adding another one would get me above 1 million), then start subtracting from the beginning on (2, 3, 5). Works as well, but less waterproof probably.

Hi Roelant

Thanks for the comment. I have tried implementing the Sieve of Atkin as you can see in Problem 10. However, I never got it to perform better than my Sieve of Eratosthenes, so I just used this sieve.

/Kristian

Below given is java codes to solve the problem. This take 0ms.

I write this with the help of C# codes by Mr. Kristian.

import java.util.*;

class Example{

public static void main(String args[]){

Date d = new Date();

long t = d.getTime();

MyData md = new MyData();

int count=0, max=0, val=0;

int[] primeList = new int[1];

int limit = 1000000;

for(int i=1;val<=limit;i++){

if(md.isPrime(i)){

val+=i;

primeList = md.ReDimPrserve(primeList);

primeList[primeList.length-1]=val;

}

}

int no=0,maxno=0;

for(int i=0;i=0;j–){

int x = primeList[i]-primeList[j];

no = i-j;

if (x>limit) break;

if(maxmaxno){

max = x;

maxno = no;

}

}

}

t = d.getTime() – t;

System.out.println(max + ” has a sequence of ” + maxno + ” numbers”);

System.out.println(“After ” + t + ” milliseconds”);

}

}

class MyData{

public boolean isPrime(int num){

if (num==1) return false;

if (num==2) return true;

if (num%2==0) return false;

for(int i=3;i<=Math.sqrt(num);i+=2){

if (num%i==0) return false;

}

return true;

}

}

the longest sum below a thousand isn’t 953, its 963 that contains not 21 primes but 24

also the largest sum i got that is below a million is 997661. could you check my work? i used VB

Dim num, x, counter, sum, answer As Integer

sum = 0

For num = 1 to 1000000

counter = 0

For x = 1 to num

If num Mod x = 0 then

counter = counter + 1

End If

Next

If counter = 2 Then

sum = sum + num

If sum > 1000000 Then

Exit For

Else

answer = sum

End If

Next

MessageBox.Show(answer)

To be honest, if the problem description says that the it is 953, I believe it is correct. Also the answer I get is the thing accepted as the answer. So I guess you have a mistake somewhere. And I can’t tell you where it is, you will have to figure that out for yourself.

When that is said, 963 is not a prime, since it is divisible by 3, that might be a hint for your debugging.

Hi Kristian,

Your algorithm will fail in the following case:

Summation of certain number of numbers is a prime number.

Summation of same number of numbers(different set of numbers) is also a prime.

In this case, your algorithm will return the smaller prime.

In order to avoid this, you can start the i-loop from the last of primes length.

Project Euler 50

Results obtained from Microsoft Excel (3):

1) The longest sum of consecutive primes below one-thousand that adds to a prime, contains 14 terms, and is equal to 281.

2) The longest sum of consecutive primes below one-thousand that adds to a composite number, contains 24 terms, and is equal to 963.

3) The longest sum of consecutive primes below one-million that adds to a prime number, contains 542 terms, and is equal to 981959.

4) The longest sum of consecutive primes below one-million that adds to a composite number, contains 546 terms, and is equal to 997661.

______

Sources:

1) Project Euler 50:

Kristian’s algorithm

http://www.mathblog.dk/files/euler/Problem50.cs

2) Microsoft Visual C# 2010 Express

3) Microsoft Office Excel (2007)

Table 1

Primes as the sum of the most consecutive primes.

[Re: Project Euler 50: Which prime, below one-million, can be written as the sum of the most consecutive primes ?]

http://img15.hostingpics.net/pics/471631pe50tab1.jpg

Please take note …

Corrections: (in my 2 previous comments above)

3) The longest sum of consecutive primes below one-million that adds to a prime number, contains 542 terms, and is equal to 981959.

Should be replaced by:

3) The longest sum of consecutive primes below one-million that adds to a prime number, contains 536 terms, and is equal to 958577.

(981959 is a composite number (11 x 89269)).

This is my code in C

My answer when limit=1000000 is

Prime, below one-million, which can be written as the sum of the most consecutive number of primes =

958577I get the last sum as 997661, which is 10 greater than the answer 997561

When limit=1000,

Prime, below one-thousand, which can be written as the sum of the most number of consecutive primes =

281I get the last sum as 963.

So if I use sum=-8 instead of 2, and run the code the answer will be 997651, which is the answer accepted. But it cannot be -8 at the start.

I cannot figure out what’s wrong.

I think the editor ate some of your code. Remember to wrap it correctly in the [ code language=”language”] [ /code] tags

#include

int limit=1000000,i,b,sum=2, prime, max_sum;

main(){

i=3;

while(summax_sum)

max_sum=sum;

}

i++;

}

printf(“\nPrime, below one-million, which can be written as the sum of the most consecutive primes = %d\n”, max_sum);

}

int checkPrime(int num){

prime = 1;

for(b=2; b<num; b++){

if(num%b==0){

prime = 0;

break;

}

}

if(prime)

return 1;

else

return 0;

}

Oops! Sorry… Forgot the tags before

#include

`int limit=1000000,i,b,sum=-8, prime, max_sum;`

`main(){`

i=3;

while(summax_sum)

max_sum=sum;

}

i++;

}

`printf("\nPrime, below one-million, which can be written as the sum of the most consecutive primes = %d\n", max_sum);`

}

`int checkPrime(int num){`

prime = 1;

for(b=2; b<num; b++){

if(num%b==0){

prime = 0;

break;

}

}

if(prime)

return 1;

else

return 0;

}

i found the number 997661 that can be written sum 546 primes!

i dont know what i’m doing wrong.

The number you have found is not a prime number. Using http://www.mathblog.dk/tools/prime-factorization/ shows me that 997661 = 7x359x397, so most likely your prime checker is wrong.

Hi Kristian,

Thanks for your solution with great insights. The techniques you used have made the search quite fast, taking only around 1ms. I dug deeper and found that the solution can be optimized by iterating i from the larger to the smaller, since the final result is expected to be large. This cuts off the iterations for small i’s, say all i<=543 (the length of the most consecutive primes found when ). Another possibility to improve the solution is to loop over the primes to see if each can be represented as the sum of consecutive primes. If it can and the length of the sequence is larger, we update the result. This could save (not sure) some time in binary searching "(primeSum[i]-primeSum[j])" in "primes". I incorporated these techniques in the following Python code for your reference:

def func():

"""Get the prime below one-million that can be

written as the sum of the most consecutive primes.

"""

primes = get_primes(1000000)

sum_of_primes = [0]

temp = 0

# sum_of_primes[i] = primes[0] + … + primes[i-1] (i>0)

for prime in primes:

temp += prime

sum_of_primes.append(temp)

most_consecutive = 0

the_prime = 0

# The targeted prime is expected to be large,

# so we start from the larger primes.

for i in range(len(primes)-1, -1, -1):

prime = primes[i]

# Early termination: this prime cannot be

# represented as a sequence of more than

# "most_consecutive" consecutive primes

if prime <= sum_of_primes[most_consecutive]:

break

j = most_consecutive

k = 0

# summ = primes[k] + primes[k+1] + … + primes[j-1]

summ = sum_of_primes[j] – sum_of_primes[k]

# see if the prime can be represented as the

# sum of consecutive primes

while summ != prime:

if summ < prime:

j += 1

else:

k += 1

if j – k <= most_consecutive:

# cannot be longer than the current longest

break

summ = sum_of_primes[j] – sum_of_primes[k]

# A longer sequence is found

if summ == prime:

most_consecutive = j – k

the_prime = prime

return the_prime

With a loose analysis, the solution above is at most O(N^2), while the one in the post could be O(N^2*log(N)) where log(N) is induced by the binary search.

I want to add to the 253 vs 263 issue (limit = 1000). The statement that consecutive primes whose sum below 1000 contain 21 numbers and sum up to 953 is wrong. It’s 14 numbers and total 281. Tried in Excel as well and I am right. First 24 numbers add up to 963 which is composite. Beyond 14 all are composite.

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89

Want to know if others can limit their sum to 1000, what are you getting? Of course, I digressed little from the 1M problem, but wanted to benchmark my code first.

Yes but if you remove 2,3,5 then we have a series of 21 primes which sum equals 953.

Hi Kristian, thank you for your solution.

I think the performance of your solution can be further improved if a hash set is used to search prime numbers during the nested loop. Since there are nearly 80000 primes under 1000000, it would greatly reduce performance time.

my thought is first find the largest number with sum of longest consecutive primes. I got result: 997661 546,then minus the smallest prime and check if the new sum is a prime, after I cut 2,3,5, I got 997651, the right answer.

can anyone give a code for this solution in c++ using do while loops and function?

Vini Mal:

test 1000 yourself please.

got this answer 281

Uh I don´t quite get it, perhaps a semantic problem (English is not my native language). The problem statement

“Project Euler 50: Which prime, below one-million, can be written as the sum of the most consecutive primes?”

seems to ask for a prime number below one-million which is a sum of primes and said sum has the largest number of terms. Yet your solution seems to find the LARGEST sum, not the sum with the LARGEST NUMBER OF TERMS.

Am I right?

Kirsten

to make my previous comment more precise, as I see the problem the solution should satisfy the following description:

Consider the set S of all sums of consecutive primes that are smaller than one-million.

Consider the subset S1 of S of sums that are smaller than one-million.

Consider the subset S2 of S1 of sums that are prime numbers. Let s(i) denote the i-th element of S2, a prime number < one-million.

For each element in S2 count its number of terms n(i) and make a sequence L of pairs

~~Order L by value n(i) and select the largest n(i). The corresponding s(i) is the required prime number.~~~~This is not an algorithm, just a set of requirements a solution should satisfy.~~Guys, I am not sure if I am a tad bit late. I believe that there are a few of us over here who are on the same boat.

(my code is in php just FYI all)

Firstly, 41 – yes this is the largest prime number that you can get by the sum of consecutive prime numbers 2, 3, 5, 7, 11 & 13. This as per a certain logic means that I would be able to find out answers for any other upper limit!

Seecondly, 281 is the largest prime number as per my program as well, which is the largest prime number that I got – 281 = Sum of 2 3 5 7 11 13 17 19 23 29 31 37 41 43

Third, going upto 1000000 (one million), the answer that I got was 958577 which is the sum of 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997 1009 1013 1019 1021 1031 1033 1039 1049 1051 1061 1063 1069 1087 1091 1093 1097 1103 1109 1117 1123 1129 1151 1153 1163 1171 1181 1187 1193 1201 1213 1217 1223 1229 1231 1237 1249 1259 1277 1279 1283 1289 1291 1297 1301 1303 1307 1319 1321 1327 1361 1367 1373 1381 1399 1409 1423 1427 1429 1433 1439 1447 1451 1453 1459 1471 1481 1483 1487 1489 1493 1499 1511 1523 1531 1543 1549 1553 1559 1567 1571 1579 1583 1597 1601 1607 1609 1613 1619 1621 1627 1637 1657 1663 1667 1669 1693 1697 1699 1709 1721 1723 1733 1741 1747 1753 1759 1777 1783 1787 1789 1801 1811 1823 1831 1847 1861 1867 1871 1873 1877 1879 1889 1901 1907 1913 1931 1933 1949 1951 1973 1979 1987 1993 1997 1999 2003 2011 2017 2027 2029 2039 2053 2063 2069 2081 2083 2087 2089 2099 2111 2113 2129 2131 2137 2141 2143 2153 2161 2179 2203 2207 2213 2221 2237 2239 2243 2251 2267 2269 2273 2281 2287 2293 2297 2309 2311 2333 2339 2341 2347 2351 2357 2371 2377 2381 2383 2389 2393 2399 2411 2417 2423 2437 2441 2447 2459 2467 2473 2477 2503 2521 2531 2539 2543 2549 2551 2557 2579 2591 2593 2609 2617 2621 2633 2647 2657 2659 2663 2671 2677 2683 2687 2689 2693 2699 2707 2711 2713 2719 2729 2731 2741 2749 2753 2767 2777 2789 2791 2797 2801 2803 2819 2833 2837 2843 2851 2857 2861 2879 2887 2897 2903 2909 2917 2927 2939 2953 2957 2963 2969 2971 2999 3001 3011 3019 3023 3037 3041 3049 3061 3067 3079 3083 3089 3109 3119 3121 3137 3163 3167 3169 3181 3187 3191 3203 3209 3217 3221 3229 3251 3253 3257 3259 3271 3299 3301 3307 3313 3319 3323 3329 3331 3343 3347 3359 3361 3371 3373 3389 3391 3407 3413 3433 3449 3457 3461 3463 3467 3469 3491 3499 3511 3517 3527 3529 3533 3539 3541 3547 3557 3559 3571 3581 3583 3593 3607 3613 3617 3623 3631 3637 3643 3659 3671 3673 3677 3691 3697 3701 3709 3719 3727 3733 3739 3761 3767 3769 3779 3793 3797 3803 3821 3823 3833 3847 3851 3853 3863 – all of which are consecutive prime numbers.

I am so sorry but I just dont understand the logic behind this problem 50. Below is my code is PHP.

Please help/comment/just help me out to understand this one!

Kritian – I would like to respectfully point out a comment posted by you on February 7, 2014 at 06:35.

My theory is also that, if I were to follow your principles/guidlines, then the largest prime number that I am getting would be 83 (that is

>100 – 2= 98;

>98 – 3 = 95;

>95 – 5 = 90;

>90 – 7 = 83;

And 83 is a Prime Number and thus proving a fact that 83 is the sum of consecutive prime numbers which are 11 + 13 + 17 + 19 + 23. If I am still wrong, please forgive me, just that I am a newbie in coding and have been doing this only for 2 months or so. Plus I aint some math genius also!)

Thanks and Cheers!

PS:- forget to add that I am stating that 83 then would be the largest prime number below 100 to be the result of the sum of all possible consecutive prime numbers!

=)

DP and depth first , python

def prime():

n=150

i=[0]*n

for j in range(2,len(i)):

if i[j]==0:

for z in range(2*j,len(i),j):

i[z]=i[z]+1

return i

def primearray():

x=prime()

store=[]

for i in range(2,len(x)):

if x[i]==0:

store.append(i)

return store

def real1():

y=prime()

x=primearray()

sum=0

for i in xrange(0,len(x)):

sum=sum+x[i]

if sum+x[i+1]>100:

return sum,i

def real(sun=None,i=None,j=0,d=[0]):

print sun,d[0]

x=primearray()

y=prime()

if sun==None and i==None:

sun,i=real1()

if sund[0]:

d[0]=i-j

return (i-j,sun)

elif sun<1:

return (0,0)

elif i-jmm:

return m,n

else:

return mm,nn

print real()

How to solve the same problem if limit is raised from 1 million to 12 billion

prime number: 43499

sum of all prime numbers from 31 to 954491.

Number of prime numbers between 31 and 954491 inclusive are 75223.

You can test if

`primeSum[i] - primeSum[j]`

is prime without a binary search, using a classic divisibility test. It’s really faster here. You need primes up to approximately 4000, not 1000000.