Achieving level two on the Project Euler web site

This is the second of the series on achieving different levels on the Project Euler web site. The web site provides 300+ interesting math/computer programming problems and any problem should be solved by a program within one minute. We have talked about achieving level one before, now you just need to solve another 25 problems to upgrade to level two. :)

Still at this level, it doesn't require much mathematical sophistication. Most problems can still be solved with brute force with some simple optimization, such as pruning the obvious impossibles.

You may also come to realize that the running time of within one minute is quite generous and this allows you to try very different languages. If you follow the forum which allows you to see the discussions on a certain problem only after you have solved it, you can find that people even use assembly language and some other less-known but interesting languages including the J programming language and and the K programming language which seem to be very suitable for solving many of the problems.

Now you also don't necessarily need to solve the problems in the order by the most number of people having solved them. In fact, depending on your background, some problems that come later may actually be easier. You can do "problem shopping" and may be able to work on some problems that have been solved by less than ten thousand people. However, don't venture too far yet. :) At least I myself am more interested in achieving level two faster than trying to solve harder problems at this time.

For certain problems, you may know how to solve them. However, it may be quite hard to describe the solution programmatically. In that case, you may be able to get the answer faster by doing it manually with pen and paper. The good thing is that once you know the answer you can check how other people solve it. Some very good code is there for you to explore.

I think if you can spend 2-3 hours during weekday and 5-6 hours during weekend, 7-10 days should be enough to achieve level two, assuming that you still have life other than solving problems at the Project Euler web site. :)

Following are some problems from the second 25 ones that I find are more interesting.

• Problem 30: Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

• Problem 24: What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

  It is actually easier to get the number manually once you know the way.

• Problem 29: How many distinct terms are in the sequence generated by a powered to b where a, b are between 2 and 100?

• Problem 36: Find the sum of all numbers less than one million, which are palindromic in base 10 and base 2.

  If you use Perl, you can use the following function to convert a decimal number to a binary one:

  sub dec2bin {
     my $str = unpack("B32", pack("N", shift));
     $str =~ s/^0+(?=\d)//; # otherwise you'll get leading zeros
     return $str;
}

• Problem 34: Find the sum of all numbers which are equal to the sum of the factorial of their digits.

  Don't even bother with backtracking. Even brute-force approach can get the results done within one minute.

• Problem 23: Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

  Don't forget to use a linear algorithm to find whether there exists two numbers in an ordered array whose sum are equal to a given number.

• Problem 35: How many circular primes are there below one million?

• Problem 27: Find the product of the coefficients, a and b, for the quadratic expression (n*n+a*n+b) that produces the maximum number of primes for consecutive values of n, starting with n = 0.

  If you don't know the theory, you may have to use a compiled language to do a brute-force search. Otherwise you can get the number by hand.

• Problem 45: After 40755, what is the next triangle number that is also pentagonal and hexagonal?

• Problem 26: Find the value of d < 1000 for which 1/d contains the longest recurring cycle.

  A good algorithm implemented in a scripting language (like Perl) can get the value in less than one second. You would only need very simple mod operation.

• Problem 37: Find the sum of all eleven primes that are both truncatable from left to right and right to left.

  There are more primes than you might have thought that are less than 100.

• Problem 39: If p is the perimeter of a right angle triangle, {a, b, c}, which value, for p <= 1000, has the most solutions?

  Use some simple optimization with brute-force you can get it done in less than 30 seconds with a scripting language.

• Problem 41: What is the largest n-digit pandigital prime that exists?

  Use simple pruning and greedy algorithm.

• Problem 32: Find the sum of all numbers that can be written as pandigital products.

  Use brute-force while pruning the impossibles.

• Problem 63: How many n-digit positive integers exist which are also an nth power?

  Some numbers can be big.

• Problem 92: How many starting numbers below ten million will arrive at 89 by continuously adding the square of the digits?

  Not all brute-force methods are the same.

Back to articles on development