Sunday 18 January 2009

Project Euler, Problems 12 and 21

The two problems that I've worked on most recently have both involved divisors of numbers; this meant that I first wrote a few small subroutines to do with divisors, calculating the number of divisors or the sum of the proper divisors of an integer. This wasn't too bad, but I really think that I am approaching the limits of the kinds of problems that I can tackle with my current level of C++ knowledge.

C++ can only handle numbers up to just over 4 billion, and some of the problems that I will probably have to check soon will be much larger than that. I know how to tackle them but for the fact that C++ cannot cope with numbers entered in that natural manner. Been thinking a bit about how to set up a new class of input, where larger numbers could be handled. At the end of the day, we're just thinking about a string of characters, and how to do operations on them. I've seen a couple of things recently that give me some ideas on how I might set up something like that.

On to the problems...

Problem 12
The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. 28 is the first triangle number to have over five divisors. What is the value of the first triangle number to have over five hundred divisors?

Wrote a script that could count the number of divisors of an integer, then started a loop through something generating the triangle numbers, checking the number of divisors. It took a while, but when it found it gave me the output to tell me what the answer was. It took quite a long time!

Problem 21
Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n). If d(a) = b and d(b) = a, where a is not equal to b, then a and b are an amicable pair and each of a and b are called amicable numbers. For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220. Evaluate the sum of all the amicable numbers under 10000.

This was straightforward given the previous routine for calculating the number of divisors of a number; we use the same criteria for evaluating if one number is a divisor of another, and so we summed all of those. Then, we calculate the sum of the proper divisors of a number, a, and then check if the sum of the proper divisors of that number is equal to a. If the sum of the proper divisors of a is different from a itself then we have found a number which is part of an amicable pair.

Looping through the numbers 2 to 10000 and summing all of the positive results that we find gives the answer.

*

Sixteen out of twenty-five. Not bad considering that most of those have been done in the last few weeks. The next small subroutine project I need to do is figure out how to generate a list of prime factors of a number; I'll also have a crack at the large number string stuff that I mentioned at the start of this post. With a bit of luck and work, I think I might have cracked another nine by the end of February!

No comments: