I was just thinking the other day that I hadn't done any Project Euler problems in a while, and having a look down the list of problems a few jumped out at me as "do-able". Both of these required very little computing - in fact I did the second mentioned here with just a calculator once I had done some thinking.
(as a side note, I've also been working on thing number 62, to find the number of stacked 4-tangles; I've proved a few things which my previous assumptions had relied on, made it more concrete, and am at the point where I need to use a Maple program in order to find things and split things up. Not quite there in my C++ knowledge in order to be able to do that!)
Problem 9
Find the only Pythagorean triplet {a,b,c} such that a + b + c = 1000.
From this we can take a few bits of information:
- a^2 + b^2 = c^2
- a + b + c = 1000
- a < b < c and a, b, c are all positive integers
- ab = 1000(500 - c)
Problem 28
Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows: (looks better on Project Euler site, here)
21 22 23 24 25
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13
I didn't need C++ to solve this. I extended the spiral out to 7 by 7, so I could get a better feel for the numbers in the diagonals. I split them up, and obtained (in the end) three sequences of numbers. From these I arrived at three quadratic relations that you could get the three sequences from, and then by summing the series I got the answer. Simple really - big numbers though!
This takes my total to 19 now, six more to go. I have a list of a few that I might try next. I was originally aiming to get my 25 done by the end of February. I'm now aiming for the end of March, and also hoping to get thing 62 done by then as well (or at least, to have the answer and be writing it out from all of my rough notes).
6 comments:
The thing that jumps at me immediately for 28 is that numbers along the main diagonal increase in subsequent multiples of two:
1-3-7-13-21 etc
The off-diagonal is less obvious... There are two increases of 4, followed by two increases of 8...
Yeah, that first diagonal is fine. With the second one I noticed that if you split it into upper and lower parts then the two individual strands (both starting at 1) and they were both clearly quadratic series.
Just a case of using summation expressions after that!
Ah, yeah, I see that. Very nice! Wish I'd thought to split them into two series
I thought it was quite nice too: and when I saw that the three series were there it seemed really wasteful to mess about with C++ to code something to do the job, when with pencil and paper I could work out the expressions and just plug some numbers into a calculator.
Think that tomorrow morning I will get my 20th problem solved... Was doing some thinking earlier, and think I have enough maths - which basically works out the restrictions on things - so that I can write a quick script in C++ that will do all the hard work for me (which in this case is searching through about two million numbers for those which satisfy certain properties).
So this is what I came up with for 28:
\sum_{n=1}^{1001}(n^2-n+1) + \sum_{n=0}^{500}(2n+1)^2 + \sum_{n=0}^{500}(4n^2+1) - 2
where we subtract 2 at the end because the 1 in the center gets counted in all three sums. This yields 669171001.
When trying to find the first sum, I actually had to break into smaller chunks because it was too big for my calculator to do all at once.
Didn't keep my calculations after I got the answer, but yeah, that looks right to me. I think that my quadratics were slightly different for how I derived the series (starting from 1, going to 501), but I think you've got it.
Post a Comment