Prime Generation

Project Euler 111: Search for 10-digit primes containing the maximum number of repeated digits.

Project Euler 111: Search for 10-digit primes containing the maximum number of repeated digits.

So in Problem 111 of Project Euler we are back at dealing with prime numbers. And rather large ones of them. But before going into details, here is the problem description

Considering 4-digit primes containing repeated digits it is clear that they cannot all be the same: 1111 is divisible by 11, 2222 is divisible by 22, and so on. But there are nine 4-digit primes containing three ones:

1117, 1151, 1171, 1181, 1511, 1811, 2111, 4111, 8111

We shall say that M(nd) represents the maximum number of repeated digits for an n-digit prime where d is the repeated digit, N(nd) represents the number of such primes, and S(nd) represents the sum of these primes.

So M(4, 1) = 3 is the maximum number of repeated digits for a 4-digit prime where one is the repeated digit, there are N(4, 1) = 9 such primes, and the sum of these primes is S(4, 1) = 22275. It turns out that for d = 0, it is only possible to have M(4, 0) = 2 repeated digits, but there are N(4, 0) = 13 such cases.

In the same way we obtain the following results for 4-digit primes.

Digit, d M(4, d) N(4, d) S(4, d)
0 2 13 67061
1 3 9 22275
2 3 1 2221
3 3 12 46214
4 3 2 8888
5 3 1 5557
6 3 1 6661
7 3 9 57863
8 3 1 8887
9 3 7 48073

For d = 0 to 9, the sum of all S(4, d) is 273700.

Find the sum of all S(10, d).

Continue reading →

Posted by Kristian in Project Euler, 8 comments
Project Euler 58: Investigate the number of primes that lie on the diagonals of the spiral grid

Project Euler 58: Investigate the number of primes that lie on the diagonals of the spiral grid

In Problem 58 of Project Euler we are revisiting the spiral we worked on in Problem 28. I have since then learned that it is called an Ulam spiral after the Polish born American mathematician Stanislaw Ulam. The problem reads:

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13  62%.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

Continue reading →

Posted by Kristian in Project Euler, 9 comments

Project Euler 46: What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

Problem 46 of Project Euler reads

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

9 = 7 + 2×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

Continue reading →

Posted by Kristian in Project Euler, 16 comments

Project Euler 35: How many circular primes are there below one million?

In problem 35 of Project Euler we are back to primes., this time it is circular primes that we are focusing on. Before looking more at circular primes lets look at the problem description which reads:

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

Continue reading →

Posted by Kristian in Project Euler, 8 comments

Sum of all Primes below 2000000 – Problem 10

This blog post is all about the solution to Problem 10 of Project Euler. Just like Problem 7 the problem is all about primes.  And the solution strategy I posted for problem 7 would be valid for this problem as well.

The problem reads

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

There is nothing particular tricky about this question, and since there isn’t a formula for finding all primes, we will have to brute force a solution. However, the brute force solution can be more or less elegant. In the source code I have made available, you can find the solution approach from problem 7, adopted to this problem. I wont spent any more time on that method, but instead introduce you to Sieve of Eratosthenes.

Sieve of Eratosthenes

Sieve of Eratosthenes was as the name implies invented by Eratosthenes who was a Greek Mathematician living around 200 BC.

The algorithm needs to have an upper limit for the primes to find. Lets call this limit N

The algorithm works as follows.

  1. Create a list l of consecutive integers {2,3,…,N}.
  2. Select p as the first prime number in the list, p=2.
  3. Remove all multiples of p from the l.
  4. set p equal to the next integer in l which has not been removed.
  5. Repeat steps 3 and 4 until p2 > N, all the remaining numbers in the list are primes

It is a pretty simple algorithm, and the description of it on Wikipedia has a really nice graphical illustration, which I decided I couldn’t do better my self. So go and have a look at it. The algorithm finds a prime, and then marks all multiples of that primes.  The first new number will always be a prime, since all numbers which are not will have been removed.

It can be pretty straight forward to implement the algorithm, and the challenge is definitely to optimize the implementation both execution and memory wise.

I found an implementation two implementation which are similar over at Stack Overflow and digitalBush which seemed very promising. I have then further optimized it a bit. The optimized code is shown here

public int[] ESieve(int upperLimit) {
    int sieveBound = (int)(upperLimit - 1) / 2;
    int upperSqrt = ((int)Math.Sqrt(upperLimit) - 1) / 2;

    BitArray PrimeBits = new BitArray(sieveBound + 1, true);

    for (int i = 1; i <= upperSqrt; i++) {
        if (PrimeBits.Get(i)) {
            for (int j = i * 2 * (i + 1); j <= sieveBound; j += 2 * i + 1) {
                PrimeBits.Set(j, false);
            }
        }
    }

    List numbers = new List((int)(upperLimit / (Math.Log(upperLimit) - 1.08366)));
    numbers.Add(2);

    for (int i = 1; i <= sieveBound; i++) {
        if (PrimeBits.Get(i)) {
            numbers.Add(2 * i + 1);
        }
    }

    return numbers.ToArray();
}

Once we have a list of all the primes we need the rest of the code is a trivial for loop summing up the array. You can check the source code for that bit. In the following sections I will touch on different aspects of the code.

Data representation

It uses a BitArray to store all the numbers. It is a enumerable type which uses one bit per boolean. Using a BitArray means the algorithm will limit the memory usage by a factor 32 compared to an array of booleans according this discussion. However, it will lower the operational performance. We need an array to hold 2.000.000 numbers, which means a difference of 250kB vs. 8MB.

I played around with it a bit, and didn’t see much of a performance difference for a small set of primes. For a large set of primes I noticed that the BitArray was slightly faster. This is likely due to better cache optimization, since the the BitArray is easier to store in the CPU cache, and thus increasing the performance.

Eliminating even numbers

Over at digitalBush he optimizes his code by skipping the even numbers in the loops. I have chosen a bit of another approach, to avoid allocating memory for it. It just takes a bit of keeping track of my indexes.

Basically I want to  start with three and then for a counter i = {1,2,….,N/2} represent every odd number p = {3,5,7,….,N}. That can be done as p = 2i+1. And that is what I have done in the code. It makes the code a bit more complex, but saves half the memory, and thus it can treat even larger sets.

Furthermore we start our inner loop at p2 = (2i+1)(2i+1) = 4i2 + 4i + 1, which will have the index 2i(i+1), which is where we start the search of the inner loop. By increasing p=2i+1 indexes in every iteration of the inner loop, I am jumping 2p, and thus only taking the odd multiples of p. Since multiplying with an even number will give an even result, and therefore not a prime.

Sieve of Atkin

Another Sieve method to generate primes is the Sieve of Atkin. It should be faster than the Sieve of Eratosthenes. I have made a reference implementation of it, but I can’t wrap my head around how to optimize it, so I have never been able to optimize it to the same degree as the Sieve of Eratosthenes. However, I have included the reference implementation in the source code, so you can play around with it if you like.

Wrapping up

This post took a bit of a different approach. I have worked hard to really optimize the code. Since I believe that the Sieve method for finding primes will be used later. So making a reusable bit of fast code, will make later problems easier to solve.

I took three 3 different approaches and tried to optimize them.  The result of the three are

Prime sum of all primes below 2000000 is 142913828922
Solution took 203,125 ms using Trial Division
Prime sum of all primes below 2000000 is 142913828922
Solution took 31,25 ms using Sieve of Eratosthenes
Prime sum of all primes below 2000000 is 142913828922
Solution took 31,25 ms using Sieve of Atkin

The difference between the two sieve methods are not really noticeable for such small numbers, but if we start calculating all primes below one billion, the differences in execution time will show. And as usual you can download the source code.

If you can come up with further optimizations of the sieve methods, I would appreciate you to leave a comment.  I am always eager to learn more and speeding things up further.

Posted by Kristian in Project Euler, 31 comments

Project Euler – Problem 7

Now we reached Problem 7 of Project Euler which is about prime numbers. The problem reads

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

We could solve this by brute force checking all the numbers, or we could reuse part of the solution to problem 5, where we generated a list of primes using trial division with already found prime numbers. I haven’t found a way to solve this without finding the 10000 primes before finding the answer.

Wikipedia comes with a great article about prime numbers, which also refers to several methods for checking if a number is a prime. We will take a bit of simpler approach though. But dive into the article, it is pretty interesting.

Continue reading →

Posted by Kristian in Project Euler, 8 comments