A088003 Take the list t(n,0) = {1,...,n}; denote by t(n,j) this list after rotating to left (or right) by j positions. Calculate inner product of t(n,0) and t(n,j) and denote the value by s(n,j). Compute this inner product for all j = 1..n and choose the smallest. This is a(n).

1, 4, 11, 22, 40, 64, 98, 140, 195, 260, 341, 434, 546, 672, 820, 984, 1173, 1380, 1615, 1870, 2156, 2464, 2806, 3172, 3575, 4004, 4473, 4970, 5510, 6080, 6696, 7344, 8041, 8772, 9555, 10374, 11248, 12160, 13130, 14140, 15211, 16324, 17501, 18722, 20010

Offset: 1

Author

Labos Elemer, Oct 14 2003

Keywords

• nonn
• easy

Comments

If the largest were chosen rather than the smallest, then A000330(n), the square pyramidal numbers, would be obtained. Also, if the inner product of t with 1-rotated-t is calculated, then A006527(n) is produced.

From Jonathan Halabi, Dec 25 2017, on behalf of Maya Nicklas: (Start)

a(n) is the number of squares (of any size) that occur in a skewed n X n chessboard, having n rows of n squares, each offset by one square from the row above. For instance, a(4) is the number of squares in this diagram:

XXXX

.XXXX

..XXXX

...XXXX

which is 22.

(End)

It seems that if we connect the top row of this skewed board with its bottom row (in the same skewed way), i.e., make the board toroidal, and count squares, we will get A128624. - Andrey Zabolotskiy, Dec 25 2017

Examples

			For n=6: t(6,0) = {1,2,3,4,5,6}, t(6,3) = {4,5,6,1,2,3};
compute scalar products for all rotations:
{76,67,64,67,76,91} of which the smallest is 64, so a(6)=64.
		

Links

• Index entries for linear recurrences with constant coefficients, signature (2,1,-4,1,2,-1).

Crossrefs

Cf. A000330, A006527, A094414.

Programs

Mathematica

t0[x_] := Table[w, {w, 1, x}]; jr[x_, j_] := RotateRight[t0[x], j]; Table[Min[Table[Apply[Plus, t0[g]*jr[g, i]], {i, 1, g}]], {g, 1, up}]

Formula

a(n) = Min{y; y=t(n, 0)*t(n, x)=s(n, x); for x=1..n}.

a(n) = n*(2*n*(5*n+12)-3*(-1)^n+11)/48.

G.f.: x*(1+2*x+2*x^2)/((1+x)^2*(1-x)^4). - Bruno Berselli, Dec 01 2010

For n >= 1, a(n) = A000330(n) - A034828(n). - Luce ETIENNE, Aug 11 2014

a(n) = Sum_{i=0..floor(n/2)} (n-i)*(n-2*i). For n=7, a(7) = 7*7 + 6*5 + 5*3 + 4*1 = 98. - Bruno Berselli, Oct 26 2015

Extensions

Edited by Bruno Berselli, Dec 01 2010