Re: A new 6-problem 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 half-diagonals, clock-wise:
3^2, 5^2, 7^2, ...
2^2-1, 4^2-3, 6^2-5, ...
2^2+1, 4^2+1, 6^2+1, ...
3^2-2, 5^2-4, 7^2-6, ...
These add up to
2(2^2 + 3^2 + 4^2 + ... + n^2) - (1 + 2 + 3 + ... + n-1 ) + (n - 1)/2 + 1 or
2(1^2 + 2^2 + 3^2 + 4^2 + ... + n^2) - (1 + 2 + 3 + ... + n-1 ) + (n - 1)/2 - 1
= 2*Sum(n=1,n,n^2) - Sum(n=1,n-1,n) + (n - 1)/2
= 2*Sum(n=1,n,n^2) - T(n-1) + (n -1)/2 where T(n-1) is the nth number,
Since T(n) = n/2*(n+1) then T(n-1) = n*(n-1)/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,n-1,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,n-1,T(n)) = 1/6*(2n + 4)*n/2*(n+1) = 1/6*((n-1)^3 + 3(n-1)^2 + 2(n-1))
Now we the expression we are looking for can be completed:
S = 2*Sum(n=1,n,n^2) - Sum(n=11,n-1,n) + (n - 1)/2 - 1
S = 2*(T(n) + 2*Sum(n=1,n-1,T(n))) - Sum(n=1,n-1,n) + (n - 1)/2 - 1
S = 2*(n/2*(n+1) + 2*1/6*((n-1)^3 + 3(n-1)^2 + 2(n-1))) - n*(n-1)/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.
|