Numbers on Spiral Diagonals
C++, Matlab. This is the problem 28 from Project Euler website.
Question: Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:
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.
What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way? Link to question page.
Solution: My approach is to detect the related sequences depending on the dimension. For example;
1 for n=1
3,5,7,9 for n=3
3,5,7,9,13,17,21,25 for n=5
3,5,7,9,13,17,21,25,31,37,43,49 for n=7 and so on…
That shows, for every n, 4 elements are added to the sequence as well. The increment value among elements depends on n level. For example, increment value is 2 for n=3 whereas it is 4 for n=5. The result for 1001 x 1001 matrix is 669171001.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | #include <iostream> /* There are sequences depending on n. For example; 1 for n=1 (default) 3,5,7,9 for n=3 3,5,7,9,13,17,21,25 for n=5 3,5,7,9,13,17,21,25,31,37,43,49 for n=7 and so on... For every n, 4 elements are added to the sequence. The increment value among elements depends on n level. For example, increment value is 2 for n=3 whereas it is 4 for n=5.*/ void sprial_diag_sum(int n); int main() { int dimension = 1001; //input dimension value for nxn matrix sprial_diag_sum(dimension); return 0; } void sprial_diag_sum(int n) { int result = 1; //default value when n=1 int x = 1; //beginning element value when n=1 /*(n - 1) / 2 is the form of 2n + 1. It matches for every odd n. For example, i = 1:1 for n = 3, i = 1 : 2 for n = 5, i = 1 : 3 for n = 7. etc. The increment depends on i, so it is 2 * i. Thus, for the loop below; - (int j = 1; j < 5; ++j) ==> for every n, element values increases 4 times - (x = x + 2 * i;) ==> beginning values in each sequence with increment*/ int boundry = ((n - 1) / 2) + 1; for (int i = 1; i < boundry; ++i) { for (int j = 1; j < 5; ++j) { x += 2 * i; result += x; } } std::cout << "The result is " << result << std::endl; } |
MATLAB version;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | function result = spiral_diag_sum %There are sequences depending on n. For example; %1 for n=1 (default) 3,5,7,9 for n=3 %3,5,7,9,13,17,21,25 for n=5 %3,5,7,9,13,17,21,25,31,37,43,49 for n=7 and so on... %For every n, 4 elements are added to the sequence. %The increment value among elements depends on n level. %For example, increment value is 2 for n=3 whereas it is 4 for n=5. tic n = 1001; %input value format long g result = 1; %default value when n=1 x = 1; %beginning element value when n=1 %(n-1)/2 is the form of 2n+1. It matches for every odd n. %For example, i=1:1 for n=3, i=1:2 for n=5, i=1:3 for n=7. etc. %The increment depends on i, so it is 2*i. for i = 1:(n-1)/2 for j = 1:4 %for every n, element values increases 4 times x = x + 2*i; %beginning values in each sequence with increment result = result + x; end end toc end |