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,2

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

Links

Table of n, a(n) for n=1..45.

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

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

Example

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.

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}]

Crossrefs

Cf. A000330, A006527, A094414.

Sequence in context: A132072 A009846 A008043 * A049836 A177853 A008016

Adjacent sequences: A088000 A088001 A088002 * A088004 A088005 A088006

Keyword

nonn,easy

Author

Labos Elemer, Oct 14 2003

Extensions

Edited by Bruno Berselli, Dec 01 2010

Status

approved