Can the summation of this be evaluated as O(1)

general
1

The question is to evaluate the sum of the digits inside a square of this type.

6 5 4 3 4 5 6
5 4 3 2 3 4 5
4 3 2 1 2 3 4
3 2 1 0 1 2 3
4 3 2 1 2 3 4
5 4 3 2 3 4 5
6 5 4 3 4 5 6

The square size increases as 3x3 5x5 7x7 and so on

Eg :

Sum of first square is 12
Sum of second square is 60

I was able to find a linear solution to this (the sum of a specific square), but is there a constant or anything less than O(n) that can be used to evaluate the required sum.

2

If you can get the sum of a specific square k as polynomial of k, some it up from 1 to n to get the polynomial solution of original problem, thus evaluate it in O(1). This link may help: https://en.wikipedia.org/wiki/Sums_of_powers

3

after some calculation i found that the formula, for sum of nn sqaure is (n(n^2-1))/2.
I can post the solution if you want .

4

Sorry I was a bit busy, that is exactly what I needed, can you also hint me the method you used to get to this.

1 Like