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
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.
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
KEYWORD
nonn,easy
AUTHOR
William P. Orrick, Jun 24 2015
STATUS
approved