Today is the first day of the year 2011. 2011 is a prime number. Not only that, but according to numerous math bloggers and twitterers on the internet, 2011 is the sum of 11 consecutive primes — that is, 2011 = 157 + 163 + 167 + 173 + 179 + 181 + 191 + 193 + 197 + 199 + 211. Furthermore (as I already said), 2011 is prime.

Naturally I wonder, how rare are these numbers — numbers that are prime but also a sum of a bunch of consecutive primes? This seems like a problem easily solved with some programming.

Let us write *P(n,k)* as the number of primes less than or equal to n that can be written as a sum of at least k consecutive primes. How big is *P(2011,k)* compared to , the number of primes less than or equal 2011?

My method for computing *P(n,k)* is pretty simple. First we start with a list of prime numbers, then write the cumulative sums for the prime numbers (these images were taken with my laptop camera off a whiteboard):

Next take every pair from the bottom list, and find their differences:

Because of the way I arranged the numbers, we can see that the bottom diagonal are all the numbers that can be written as a sum of 1 prime (obviously, the prime numbers), then the next row are all numbers that can be written as a sum of 2 primes, and so on. If we want to compute *P(n,k)* we simply list enough prime numbers to complete this table, take everything above a diagonal, and filter out all the duplicates.

Here’s my hopefully correct implementation:

import java.util.*; import java.lang.*; class Main { public static void main (String[] args) throws java.lang.Exception { int LIM = 2011; int NCONSEC = 3; boolean[] sieve = new boolean[LIM+1]; Arrays.fill(sieve, true); for(int i=2; i<=LIM; i++){ if(!sieve[i]) continue; for(int j=2; j*i<=LIM; j++) sieve[i*j] = false; } List<Integer> primes = new ArrayList<Integer>(); for(int i=2; i<=LIM; i++) if(sieve[i]) primes.add(i); List<Integer> cuml = new ArrayList<Integer>(); cuml.add(0); int cum = 0; for(int p : primes){ cum += p; cuml.add(cum); } Set<Integer> consums = new TreeSet<Integer>(); for(int i=1; i<cuml.size(); i++){ for(int j=0; j<=i-NCONSEC; j++) consums.add(cuml.get(i) - cuml.get(j)); } int p = 0; for(int i : consums){ if(i > LIM) break; if(!sieve[i]) continue; //System.out.println(i); p++; } System.out.println(p); } }

It turns out that P(2011,3) = 147 and since there are 305 primes less or equal to 2011, roughly half of all primes under 2011 can be written as a sum of at least 3 consecutive primes. Hardly a special number at all! Even if we insist on a list of 11 consecutive primes, there are still 56 primes less than or equal to 2011 that can be written as a sum of 11 consecutive primes, about 1 in every 5 primes.

Happy New Year!

Hey, Lucky…Your sieve can be faster…

for(int i=2; i<=LIM; i++){

if(!sieve[i]) continue;

for(int j=i*i; j<=LIM; j+=i)

sieve[j] = false;

}

Which avoid Multiplication….

//assuming u took care of factors of 2

for(int i=3; i<=LIM; i+=2){

if(!sieve[i]) continue;

for(int j=i*i; j<=LIM; j+=2*i) //'evens' already taken care of.

sieve[j] = false;

}

LikeLike

good one!

LikeLike