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 descriptionWe shall say that M(n, d) represents the maximum number of repeated digits for an n-digit prime where d is the repeated digit, N(n, d) represents the number of such primes, and S(n, d) represents the sum of these primes.Find the sum of all S(10, d).I rather quickly realized that there must be two solution approaches to this problem. Either we generate all the primes in the range and start finding the right ones. Or we can generate numbers with repeated digits and check if they are primes.I started out with the first approach, by trying to generate primes up to 10.000.000.000, but I ran into problems with my sieve as we have to index more than can be stored in an integer. So either I could rewrite the sieve or I could look into the other approach.

Continue reading...Saturday, August 27, 2011

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:What is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?In problem 28 we sought and found a closed form solution to finding the sum of the diagonals. In this problem we need to investigate each corner of the spiral. So we need to generate each corner an check it. I have found no other way than brute force to create the corners and check them. I found no pattern in the primes except that they never occurs in the lower right diagonal. The numbers there are always perfect squares due to the nature of the spiral.

Continue reading...Saturday, June 4, 2011

Problem 46 of Project Euler readsWhat is the smallest odd composite that cannot be written as the sum of a prime and twice a square? I haven't found ways to solve this except for brute force, but I have found three slightly different approaches brute forcing the problem.

Continue reading...Saturday, April 9, 2011

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 How many circular primes are there below one million? At first I thought circular primes were any permutation of the prime, but then 791 would be in the example as well, so I realised that it is primes that you can rotate such that any rotation is also a prime. I must admit that I don't think I have found a very nice solution, but it runs fast enough to satisfy me. It is a brute force algorithm where we search every prime below 1.000.000 to see if it can be rotated.

Continue reading...Sunday, November 21, 2010

Problem 10 is all about primes, just like probem 7. The problem is Find the sum of all the primes below two million.I take three different approaches to the solution, and focus on Sieve of Eratosthenes, which I will present the source code for an optimized version of.

Continue reading...Wednesday, November 3, 2010

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.

Continue reading...
Saturday, August 25, 2012

7 Comments