Re: A new 6problem challenge (free42 or 42s) Message #5 Posted by Gerson W. Barbosa on 11 June 2011, 3:22 a.m., in response to message #4 by Gerson W. Barbosa
Some explanation:
43 44 45 46 47 48 49
42 21 22 23 24 25 26
41 20 7 8 9 10 27
40 19 6 1 2 11 28
39 18 5 4 3 12 29
38 17 16 15 14 13 30
37 36 35 34 33 32 31
Pattern of halfdiagonals, clockwise:
3^2, 5^2, 7^2, ...
2^21, 4^23, 6^25, ...
2^2+1, 4^2+1, 6^2+1, ...
3^22, 5^24, 7^26, ...
These add up to
2(2^2 + 3^2 + 4^2 + ... + n^2)  (1 + 2 + 3 + ... + n1 ) + (n  1)/2 + 1 or
2(1^2 + 2^2 + 3^2 + 4^2 + ... + n^2)  (1 + 2 + 3 + ... + n1 ) + (n  1)/2  1
= 2*Sum(n=1,n,n^2)  Sum(n=1,n1,n) + (n  1)/2
= 2*Sum(n=1,n,n^2)  T(n1) + (n 1)/2 where T(n1) is the n_{th} number,
Since T(n) = n/2*(n+1) then T(n1) = n*(n1)/2
Now we need only compute the sum of the squares. Let's do it for n up to 5 first, as an example:
1^2 + 2^2 + 3^2 + 4^2 + 5^2, which we can rewrite as
1 3 6 10 15
_________________

1 + 1 + 1 + 1 + 1 +  10

2 + 2 + 2 + 2 + 1 +  6

3 + 3 + 3 + 2 + 1 +  3

4 + 4 + 3 + 2 + 1 +  1

5 + 4 + 3 + 2 + 1 
When summing the elements diagonally, as indicated, we get
1^2 + 2^2 + 3^2 + 4^2 + 5^2 = 15 + 2*(1 + 3 + 6 + 10) = 5, that is T(5) + 2*Sum(n=1,4,T(n))
Generalizing,
Sum(1,n,n^2) = T(n) + 2*Sum(n=1,n1,T(n))
T(n) = n/2*(n+1), as we know, but an expression for the sum T(n), for n=1 up to n, is still lacking. I won't derive it here (done it once
long ago, don't remember the details), but I'll try to find an expression empirically, given that 1/6 is one factor in the expression (all
I remember). Let's write a small table to help us:
n 1 2 3 4 5 6
T(n) 1 3 6 10 15 21
Sum(T(n)) 1 4 10 20 35 56
6*S(Tn)/T(n) 6 8 10 12 14 16 , that is, 2*n+4
Then we can write
Sum(n=1,n1,T(n)) = 1/6*(2n + 4)*n/2*(n+1) = 1/6*((n1)^3 + 3(n1)^2 + 2(n1))
Now we the expression we are looking for can be completed:
S = 2*Sum(n=1,n,n^2)  Sum(n=11,n1,n) + (n  1)/2  1
S = 2*(T(n) + 2*Sum(n=1,n1,T(n)))  Sum(n=1,n1,n) + (n  1)/2  1
S = 2*(n/2*(n+1) + 2*1/6*((n1)^3 + 3(n1)^2 + 2(n1)))  n*(n1)/2 + (n  1)/2  1
A little algebra yields
S = n*(n + 1) + (n  1)*(2*(n  1)*((n  1)/3 + 1) + (1  n)/2 + 4/3)  1
Further optimization is required, like applying a Horner scheme to take advantage of the RPN stack.
Edited: 11 June 2011, 3:25 a.m.
