API

Project Euler 37: Find the sum of all eleven primes that are both truncatable from left to right and right to left

A new type of prime numbers are the focus of Problem 37 of Project Euler. This time the type of prime numbers is truncatable primes. I have never heard of this type of primes before, but the problem description gives a good explanation.

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

Continue reading →

Posted by Kristian in Project Euler, 17 comments

Project Euler 22: What is the total of all the name scores in the file of first names?

Project Euler has a large variety in the sort of problems they pose. Problem 22, as we will solve now, has nothing to do with mathematics and everything to do with computer science and sorting algorithms. The problem reads

Using names.txt (right click and ‘Save Link/Target As…’), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 x 53 = 49714.

What is the total of all the name scores in the file?

The way I want to solve this problem, is to split it into three parts

  1. Read the input file and turn the data into a manageable data structure
  2. Sort the data
  3. Sum up and provide the answer

Continue reading →

Posted by Kristian in Project Euler, 19 comments

Project Euler 19: How many Sundays on the first of a month

Problem 19 of Project Euler is a curious little problem. It states

You are given the following information, but you may prefer to do some research for yourself.

  • 1 Jan 1900 was a Monday.
  • Thirty days has September,
    April, June and November.
    All the rest have thirty-one,
    Saving February alone,
    Which has twenty-eight, rain or shine.
    And on leap years, twenty-nine.
  • A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

I thought a while about this, before I realised that the easiest way to solve this is most likely to exploit the .NET API. Like many other high level languages .NET offers a really good day/time API, which is easy to use for a problem like this.

The solution is two simple loops to reach all the dates we need to check, and then check if that is a Sunday. In C# this can be implemented as

int sundays = 0;

for (int year = 1901; year <= 2000; year++) {
    for (int month = 1; month <= 12; month++) {
        if ((new DateTime(year, month, 1)).DayOfWeek == DayOfWeek.Sunday) {
            sundays++;
        }
    }
}

Pretty simple, and an output as

There are 171 sundays on the first of a month
Solution took 0 ms

I have seen a solution proposed which works for the exact question. Since there are 12 month and 100 years, we have 1200 months with a uniform distribution 1/7th of them is mondays, totalling 171 mondays. This solution works nicely for this period, but not for 1903 – 2002.

Closing remarks

It was a curious little problem to find an answer for, however using the date/time API it was fairly easy to provide a brute force solution. As usual I have uploaded the source code for you.

 

Posted by Kristian in Project Euler, 8 comments

Project Euler 16: The sum of digits in 2^1000

Just like the solution to problem 13 the answer to problem 16 of Project Euler has become trivial with .NET 4.0. And since I am lazy I intend to exploit the tools I am given. The problem description reads

215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 21000?

If there didn’t exist a BigInteger class in .NET, then we would have needed to implement a way of storing the large result, which would need 1000 bits of storage, or around the size of 32 integers. Continue reading →

Posted by Kristian in Project Euler, 20 comments

Project Euler 13: Sum of 50-digit numbers

There is nothing particularly mathematically interesting in Problem 13 of Project Euler.  Since the question is about summing numbers. The tricky part of the question is that the numbers are so big they don’t fit into an ordinary data type. The question goes

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

I have left out the actual numbers, but check the question for them.  I originally solved the question using arrays of integers to store each number in, and then I thought I was very smug and all. But when I sought a bit of inspiration on the internet before writing this blog post, I realised that many other languages has built in support for large integers. Continue reading →

Posted by Kristian in Project Euler, 23 comments

Stopwatch – a timing function in C#

Recently while seeking inspiration, I found a small function in the .net api called StopWatch. It was exactly what I have been looking for. It is placed under System.Diagnostics.Stopwatch

Until now I have made my timed my solution algorithms using multiple timestamp variables, but I have come to realise that the StopWatch is exactly what I needed, and packs all the features I need.
Continue reading →

Posted by Kristian in Programming, 4 comments