Saturday, 28 February 2009

Project Euler, Problems 34 and 39

Two more problems solved!

Problem 34
145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145. Find the sum of all numbers which are equal to the sum of the factorial of their digits.

This was pretty straightforward. When we consider that 9! = 362880 we only have to do a few sums to get an upper bound on the numbers that we must consider. Then it is a simple case of putting together a loop which gets the digits of a number, sums the factorials of the digits and compares it with the number. There is a similar problem which I hope to have coded a routine for by the end of the weekend involving fifth powers of digits.

Problem 39
If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120 - {20,48,52}, {24,45,51}, {30,40,50}. For which value of p ≤ 1000, is the number of solutions maximised?

I solved a similar problem to this a few days ago; this was a bigger problem because of searching through a large set of perimeters. However, with a bit more maths it wasn't difficult to get conditions to impose and then search through - for example, we can deduce with only a little work that p/3 < c < p/2 and that p must be a divisor of 2ab. The program took no time at all to find the p which had the most solutions (incidentally, the perimeter value found had 8 solutions!).

So that leaves... Four problems to solve? Really? Am I actually that close to finishing another one of my 101 things?!


Matt_Evans said...

go go go!

zero_zero_one said...

I've done one more this afternoon, had a go at another one - but which didn't work, so will have to have a think about how I approach it... Have two more lined up which I think I have the maths and skills to solve. One more which I know how to solve - except the numbers are too big for the regular integer class to handle!

Will blog about the one I've done when I have one more to talk about. Hoping to have completed my personal goal of 25 within 10 days at most... Aiming for by the end of this week! :)

Rudy Meijer said...

I looked at your solution for problem 39 and I is asked myself: Why is p/3 < c? Can you explain that?


Rudy Meijer

zero_zero_one said...

Hi Rudy,

Thanks for your question: it really made me think as I don't know where my notes are from when I did that! :)

But here it is, proof by contradiction.

For Pythagorean triple, we have a < b 2p/3. But that means that at least one of a,b is greater than p/3. So either a > c or b > c. But from our earlier starting point, a < b <c. So contradiction, and p/3 < c.

Hope that helps! Actually, I'm struggling to remember why c < p/2, although I know there is a really good reason it is escaping me at the moment.