Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:
What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?
The solution (in ruby)
The problem initially looks complex and makes us want to use matrices. For a small input such as the one given, it will be easier to solve. But when the size of the matrix increases, it is almost impossible to do a proper traversal and find the edge values. This problem can be attacked easily if we are able to decipher the pattern. If you could notice the given matrix carefully, you may find that at each square corners, we have a square number on the right top corner, leave the first value (1), we can sum it later.
For the first level, the corner value is 9 = 32
For the second level, corner value is 25 = 52
This keeps going. Our job is to find a forumla at each covering square. The forumla that I arrived at each level in terms of n is [4 * (n2 - (n-1)*3/2)]. If you apply the above formula for level 3 we will get 24, for level 5, its 76. If you add these two you will get 100. Now add that with 1, you will get the desired answer as 101. Finding that formula is left to the reader as an excercise (it can be found using finite differences)
Now the source code in ruby,
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
It can be verified that the sum of the numbers on the diagonals is 101.20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13
What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?
The solution (in ruby)
The problem initially looks complex and makes us want to use matrices. For a small input such as the one given, it will be easier to solve. But when the size of the matrix increases, it is almost impossible to do a proper traversal and find the edge values. This problem can be attacked easily if we are able to decipher the pattern. If you could notice the given matrix carefully, you may find that at each square corners, we have a square number on the right top corner, leave the first value (1), we can sum it later.
For the first level, the corner value is 9 = 32
For the second level, corner value is 25 = 52
This keeps going. Our job is to find a forumla at each covering square. The forumla that I arrived at each level in terms of n is [4 * (n2 - (n-1)*3/2)]. If you apply the above formula for level 3 we will get 24, for level 5, its 76. If you add these two you will get 100. Now add that with 1, you will get the desired answer as 101. Finding that formula is left to the reader as an excercise (it can be found using finite differences)
Now the source code in ruby,
result = 1
(3..1001).step(2) do |n|
val += (n*n - 3 * (n-1)/2)*4
end
puts "Result is #{result}"
HOVER HERE TO SEE THE ANSWER
Cheers!!
Bragaadeesh.
No comments:
Post a Comment