Is 2011 a special number?

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 \pi(2011) = 305, 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!

2 thoughts on “Is 2011 a special number?

  1. 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;
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s