Thursday 25 September 2008

Project Euler

So I've made a good start so far on thing number 82, solving 25 problems on Project Euler. From the site:

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

I've solved six of the problems so far, and while I'm not going to go into huge detail on how I did them, I thought I would list the ones I've solved and say a few words on how I did it.

(you know, so you know I'm not just cheating or anything)

Problem 1: Add all the natural numbers below one thousand that are multiples of 3 or 5.
This was quite straight forward, there are simple formulas for adding sums of numbers. We simply take add the formulas for sums of multiples of 3 or 5 and subtract the sum of numbers which are multiples of 15.

Problem 2: Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.
I did this with a simple program I wrote. It's easy to write out the steps by hand, the problem here is in the number of steps involved. A simple C++ program solved it.

Problem 5: What is the smallest number divisible by each of the numbers 1 to 20?
This just took a little bit of thought, no computing involved.

Problem 6: What is the difference between the sum of the squares and the square of the sums, for the numbers from 1 to 100?
Again, there are formulas for these, I just had to look them up.

Problem 8: Discover the largest product of five consecutive digits in the 1000-digit number.
For this one the site gives you a 1000 digit number; I did think about trying to test the basic C++ skills I have to read through it and find the requisite place, but in the end it was easier to do it by observation than mess around with C++. (note: this is not a good idea in general, the "by inspection" approach does not scale well!)

Problem 20: Find the sum of digits in 100!
This was simple, although I will talk about how I would do it differently now that I've thought about it. I found a website which would calculate 1 times 2 times 3 times...times 100, and then just summed the digits.

Now, C++ only allows operations on integers up to a certain amount (around four billion). 100! has a lot more digits than that; I've thought about it since, and figured out how I can create a "big number calculator" for C++. I'm sure someone else must have done it before, and I only have it in principle in my head so far, but I'm reasonably confident that I can create it soon.

Six down, nineteen to go!

6 comments:

noisms said...

2: So you just wrote a program to do it for you?

6: So you just looked up the answers?

20: So you found a website to do it for you?

Cheat! I hereby declare the whole thing invalid.

NathanRyder said...

@noisms:
2. The whole point is using maths and mathematical computing!

6. I looked up standard formulas and applied them!

20. I found a website to perform the initial calculation, and then worked on the results myself!

So there! I refute your claims that I am a cheat.

Anonymous said...

Regarding 5:

Is it (20!)/(10!)? This is just looking at it for a few moments, so there could be something much smaller.

Regarding 6:

Looked up formulas?! You could have just derived them yourself. Some mathematician =P

noisms said...

Frankly, I'm having doubts about his entire PhD thesis. He probably just looked it all up on a website.

NathanRyder said...

@matt: First principles is alright for somethings... In this instance I thought it was simpler just to apply established theory.

I think (20!)/(10!) is a bit big.

@noisms: Is that how you're getting yours?

kimz said...

ugh... my brain hurts