login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A259363 Number of distinct elements in the Gram matrix of the first M rows of the Kronecker product (Sylvester) Hadamard matrix. 0
0, 1, 2, 3, 2, 4, 4, 3, 2, 4, 5, 6, 4, 5, 4, 3, 2, 4, 5, 6, 5, 8, 7, 6, 4, 5, 6, 7, 4, 5, 4, 3, 2, 4, 5, 6, 5, 8, 7, 6, 5, 8, 9, 10, 7, 8, 7, 6, 4, 5, 6, 7, 6, 9, 8, 7, 4, 5, 6, 7, 4, 5, 4, 3, 2, 4, 5, 6, 5, 8, 7, 6, 5, 8, 9, 10, 7, 8, 7, 6, 5, 8, 9, 10, 9, 12, 11, 10, 7, 8, 9, 10, 7, 8, 7, 6, 4, 5, 6, 7, 6, 9, 8, 7, 6, 9, 10, 11, 8, 9, 8, 7, 4, 5, 6, 7, 6, 9, 8, 7, 4, 5, 6, 7, 4, 5, 4, 3, 2, 4, 5, 6, 5, 8, 7, 6, 5, 8, 9 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Let H(2) = [1, 1; 1, -1]; let H(2^(n+1)) be the Kronecker product of H(2^n) and H(2). For M less than or equal to 2^n, let A(2^n,M) be the submatrix of H(2^n) consisting of its first M rows, and let G(2^n,M)=(A(2^n,M))'A(2^n,M). Then a(M) is the number of distinct elements of G(2^n,M), which depends only on M.

LINKS

Table of n, a(n) for n=0..138.

Math Stackexchange, Relation between number of unique values in Gramian Matrix (G) and the matrices that created it

FORMULA

Recurrence for M>0: let b be the base-2 representation of M. Map b to a word w on the alphabet {1,I,O} by splitting b into runs of 0's and 1's and letting O represent a string of one or more 0's, I a string of two or more 1's, and 1 an isolated 1. Then a(0)=0, a(n)=s(w), where s(1)=1, s(1O1)=4, s(uO)=s(u)+1, s(vI)=s(v1)+2, s(vIO1)=s(v1)+4, s(v1O1)=s(v1)+4, where u is a nonempty word and v is an arbitrary word.

Closed form: s(1)=1, s(1O)=2, s(w)=4[(|w|+1)/2]+a(w)+b(w)+c(w), where |w| is the length of w, [x] is the greatest integer function, and a, b, c are defined by a(w)=0 if w ends in O, -1 if w ends in 1 or I; b(w)=1 if first letter of w is I, 0 if first letter of w is 1; c(w)=-1 if last non-O letter of w is I, -3 if last non-O letter of w is 1.

Equivalently, for n > 1, a(n) = 4*A069010(n) - A000035(n) + A079944(n-2) + 4 - A099545(n-1) + A036987(n-1).

EXAMPLE

H(4)=[1,1,1,1;1,-1,1,-1;1,1,-1,-1;1,-1,-1,1], A(4,3)=[1,1,1,1;1,-1,1,-1;1,1,-1,-1], G(4,3)=[3,1,1,-1;1,3,-1,1;1,-1,3,1;-1,1,1,3]. Since G(4,3) has 3 distinct elements, a(3)=3.

MATHEMATICA

mToWord[m_] := Module[{binary, sbin, lst, j},

  binary = IntegerDigits[m, 2];

  sbin = Split[binary];

  lst = {};

  For[j = 1, j <= Length[sbin], j++,

   If[sbin[[j, 1]] == 1 && Length[sbin[[j]]] > 1, AppendTo[lst, 11]];

   If[sbin[[j]] == {1}, AppendTo[lst, 1]];

   If[sbin[[j, 1]] == 0, AppendTo[lst, 0]]

   ];

  lst

  ]

s[{1}]=1

s[{1, 0}]=2

s[w_] := Module[{b, newW, a, c},

  If[w[[1]] == 11,

   b = 1,

   b = 0

   ];

  If[w[[-1]] != 0,

   newW = Append[w, 0];

   a = -1,

   newW = w;

   a = 0

   ];

  If[newW[[-2]] == 1,

   c = -3,

   If[newW[[-2]] == 11,

    c = -1

    ]

   ];

  a + b + c + 2 Length[newW]

  ]

numberDistinctGramValues[m_]:=If[m==0, 0, s[mToWord[m]]]

CROSSREFS

Cf. A000975, A240908, A240909, A240910.

Sequence in context: A274228 A321476 A214567 * A087437 A304739 A304735

Adjacent sequences:  A259360 A259361 A259362 * A259364 A259365 A259366

KEYWORD

nonn,easy

AUTHOR

William P. Orrick, Jun 24 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 2 07:15 EDT 2020. Contains 334767 sequences. (Running on oeis4.)