[seqfan] Re: Initial Substrings of n-bit Binary Numbers Not Divisible by k

[Ron Hardin]

> >  T(n,k) = Number of n-bit  binary strings with no initial substring
> >  representing a binary number  divisible by  k
> 

Column recurrences around k=8 16 32 and 64 have a pattern  (a(n)===T(n,k))

06 a(n)=a(n-1)+2*a(n-2)-a(n-3)
07 a(n)=a(n-1)+a(n-2)+a(n-3)
08 a(n)=a(n-1)+a(n-2)+a(n-3)
09 a(n)=2*a(n-1)-a(n-3)+a(n-4)
10 a(n)=2*a(n-1)-a(n-2)+2*a(n-3)-a(n-4)

14 a(n)=a(n-1)+a(n-2)+2*a(n-3)-a(n-4)
15 a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)
16 a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)
17 a(n)=2*a(n-1)-a(n-4)+a(n-5)
18 a(n)=2*a(n-1)-a(n-3)+2*a(n-4)-a(n-5)

30 a(n)=a(n-1)+a(n-2)+a(n-3)+2*a(n-4)-a(n-5)
31 a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)
32 a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)
33 a(n)=2*a(n-1)-a(n-5)+a(n-6)
34 a(n)=2*a(n-1)-a(n-4)+2*a(n-5)-a(n-6)

62 a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+2*a(n-5)-a(n-6)
63 a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)+a(n-6)
64 a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)+a(n-6)
65 a(n)=2*a(n-1)-a(n-6)+a(n-7)
66 a(n)=2*a(n-1)-a(n-5)+2*a(n-6)-a(n-7)

complete list

02 a(n)=a(n-1)
03 a(n)=a(n-1)+a(n-2)
04 a(n)=a(n-1)+a(n-2)
05 a(n)=2*a(n-1)-a(n-2)+a(n-3)
06 a(n)=a(n-1)+2*a(n-2)-a(n-3)
07 a(n)=a(n-1)+a(n-2)+a(n-3)
08 a(n)=a(n-1)+a(n-2)+a(n-3)
09 a(n)=2*a(n-1)-a(n-3)+a(n-4)
10 a(n)=2*a(n-1)-a(n-2)+2*a(n-3)-a(n-4)
11 a(n)=2*a(n-1)-a(n-4)+a(n-6)
12 a(n)=a(n-1)+2*a(n-2)-a(n-4)
13 a(n)=2*a(n-1)-a(n-4)+a(n-5)-a(n-6)+a(n-7)
14 a(n)=a(n-1)+a(n-2)+2*a(n-3)-a(n-4)
15 a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)
16 a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)
17 a(n)=2*a(n-1)-a(n-4)+a(n-5)
18 a(n)=2*a(n-1)-a(n-3)+2*a(n-4)-a(n-5)
19 a(n)=2*a(n-1)-a(n-5)+a(n-7)-a(n-8)+a(n-10)
20 a(n)=2*a(n-1)-a(n-2)+2*a(n-3)-a(n-5)
21 a(n)=2*a(n-1)-a(n-2)+2*a(n-3)-a(n-4)+a(n-5)
22 a(n)=2*a(n-1)-2*a(n-5)+3*a(n-6)-a(n-7)
23 a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-6)+a(n-9)+a(n-10)+a(n-11)
24 a(n)=a(n-1)+2*a(n-2)-a(n-5)
25 a(n)=2*a(n-1)-a(n-5)+a(n-6)-a(n-7)+a(n-8)-a(n-10)+a(n-11)
26 a(n)=2*a(n-1)-a(n-5)+2*a(n-7)-a(n-8)
27 a(n)=2*a(n-1)-a(n-5)+a(n-6)-a(n-8)+a(n-10)
28 a(n)=a(n-1)+a(n-2)+2*a(n-3)-a(n-5)
29 a(n)=2*a(n-1)-a(n-5)+a(n-6)-a(n-9)+a(n-11)-a(n-12)+a(n-13)-a(n-14)+a(n-15)
30 a(n)=a(n-1)+a(n-2)+a(n-3)+2*a(n-4)-a(n-5)
31 a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)
32 a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)
33 a(n)=2*a(n-1)-a(n-5)+a(n-6)
34 a(n)=2*a(n-1)-a(n-4)+2*a(n-5)-a(n-6)
35 a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)+a(n-9)+a(n-11)+a(n-12)
36 a(n)=2*a(n-1)-a(n-3)+2*a(n-4)-a(n-6)
37 
a(n)=2*a(n-1)-a(n-6)+a(n-8)-a(n-9)+a(n-12)-a(n-13)+a(n-14)-a(n-15)+a(n-17)-a(n-18)+a(n-19)

38 a(n)=2*a(n-1)-a(n-6)+a(n-8)-2*a(n-9)+3*a(n-10)-a(n-11)
39 a(n)=2*a(n-1)-a(n-4)+2*a(n-5)-a(n-6)+a(n-9)
40 a(n)=2*a(n-1)-a(n-2)+2*a(n-3)-a(n-6)
41 a(n)=2*a(n-1)-a(n-6)+a(n-8)-a(n-10)+a(n-11)
42 a(n)=2*a(n-1)-a(n-2)+2*a(n-3)-a(n-4)+2*a(n-5)-a(n-6)
43 a(n)=2*a(n-1)-a(n-6)+a(n-8)
44 a(n)=2*a(n-1)-a(n-5)+a(n-6)+a(n-7)-a(n-8)
45 a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)+a(n-7)+a(n-10)+a(n-12)
46 a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)+a(n-7)+a(n-10)+2*a(n-11)-a(n-12)
47 
a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)+a(n-7)+a(n-9)+a(n-13)+a(n-14)+a(n-16)+a(n-17)+a(n-20)+a(n-21)+a(n-22)+a(n-23)

48 a(n)=a(n-1)+2*a(n-2)-a(n-6)
49 
a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)+a(n-7)+a(n-9)+a(n-10)+a(n-14)+a(n-15)+a(n-17)+a(n-21)

50 a(n)=2*a(n-1)-a(n-6)+a(n-7)-a(n-8)+a(n-9)-a(n-10)+2*a(n-11)-a(n-12)
51 a(n)=a(n-1)+2*a(n-2)-a(n-4)+a(n-5)+a(n-6)
52 a(n)=2*a(n-1)-2*a(n-6)+3*a(n-7)-a(n-9)
53 
a(n)=2*a(n-1)-a(n-6)+a(n-7)-a(n-9)+a(n-11)-a(n-12)+a(n-13)-a(n-14)+a(n-15)-a(n-17)+a(n-18)-a(n-22)+a(n-25)-a(n-26)+a(n-27)

54 a(n)=2*a(n-1)-a(n-6)+a(n-7)-2*a(n-9)+3*a(n-10)-a(n-11)
55 
a(n)=2*a(n-1)-a(n-4)+2*a(n-5)-a(n-6)+a(n-7)-a(n-8)+a(n-9)+a(n-13)-a(n-14)+a(n-17)

56 a(n)=a(n-1)+a(n-2)+2*a(n-3)-a(n-6)
57 a(n)=2*a(n-1)-a(n-6)+a(n-7)-a(n-9)+a(n-10)
58 a(n)=2*a(n-1)-a(n-6)+a(n-7)-a(n-10)+a(n-12)-a(n-13)+2*a(n-15)-a(n-16)
59 
a(n)=2*a(n-1)-a(n-6)+a(n-7)-a(n-10)+a(n-11)-a(n-12)+a(n-13)-a(n-14)+a(n-16)-a(n-17)+a(n-19)-a(n-22)+a(n-26)-a(n-28)+a(n-30)

60 a(n)=a(n-1)+a(n-2)+a(n-3)+2*a(n-4)-a(n-6)
61 
a(n)=2*a(n-1)-a(n-6)+a(n-7)-a(n-11)+a(n-13)-a(n-15)+a(n-16)-a(n-18)+a(n-19)-a(n-20)+a(n-23)-a(n-26)+a(n-27)-a(n-28)+a(n-29)-a(n-30)+a(n-31)

62 a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+2*a(n-5)-a(n-6)
63 a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)+a(n-6)
64 a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)+a(n-6)
65 a(n)=2*a(n-1)-a(n-6)+a(n-7)
66 a(n)=2*a(n-1)-a(n-5)+2*a(n-6)-a(n-7)
67 
a(n)=2*a(n-1)-a(n-7)+a(n-11)-a(n-12)+a(n-13)-a(n-15)+a(n-16)-a(n-19)+a(n-20)-a(n-22)+a(n-24)-a(n-27)+a(n-29)-a(n-30)+a(n-31)-a(n-32)+a(n-34)

68 a(n)=2*a(n-1)-a(n-4)+2*a(n-5)-a(n-7)
69 
a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)+a(n-6)+a(n-10)+a(n-13)+a(n-15)+a(n-19)+a(n-20)+a(n-22)

70 a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)+a(n-6)+a(n-10)+2*a(n-12)-a(n-13)
71 
a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)+a(n-6)+a(n-10)+a(n-11)+a(n-14)+a(n-17)+a(n-18)+a(n-19)+a(n-20)+a(n-22)+a(n-24)+a(n-27)+a(n-29)+a(n-30)+a(n-31)+a(n-33)+a(n-34)+a(n-35)

72 a(n)=2*a(n-1)-a(n-3)+2*a(n-4)-a(n-7)
73 a(n)=2*a(n-1)-a(n-3)+2*a(n-4)-a(n-6)+a(n-7)
74 
a(n)=2*a(n-1)-a(n-7)+a(n-9)-a(n-10)+a(n-13)-a(n-14)+a(n-15)-a(n-16)+2*a(n-19)-a(n-20)

75 
a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)+a(n-6)+a(n-9)+a(n-12)+a(n-14)+a(n-15)+a(n-19)+a(n-20)

76 a(n)=2*a(n-1)-a(n-7)+a(n-10)+a(n-11)-a(n-12)
77 
a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)+a(n-6)+a(n-9)+a(n-11)+a(n-13)+a(n-14)+a(n-17)+a(n-18)+a(n-19)+a(n-23)+a(n-28)+a(n-30)

78 a(n)=2*a(n-1)-a(n-4)+2*a(n-5)-a(n-7)-a(n-8)+3*a(n-9)-a(n-10)
79 
a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)+a(n-6)+a(n-9)+a(n-10)+a(n-15)+a(n-18)+a(n-19)+a(n-21)+a(n-22)+a(n-23)+a(n-27)+a(n-29)+a(n-30)+a(n-32)+a(n-34)+a(n-36)+a(n-37)+a(n-38)+a(n-39)

80 a(n)=2*a(n-1)-a(n-2)+2*a(n-3)-a(n-7)
81 
a(n)=2*a(n-1)-a(n-7)+a(n-9)-a(n-11)+a(n-12)-a(n-13)+a(n-14)-a(n-16)+a(n-17)-a(n-20)+a(n-21)-a(n-22)+a(n-24)-a(n-27)+a(n-28)

82 a(n)=2*a(n-1)-a(n-7)+a(n-9)-a(n-10)+2*a(n-11)-a(n-12)
83 
a(n)=2*a(n-1)-a(n-7)+a(n-9)-a(n-12)+a(n-13)-a(n-14)+a(n-15)-a(n-16)+a(n-18)-a(n-20)+a(n-21)-a(n-22)+a(n-25)-a(n-27)+a(n-28)-a(n-32)+a(n-36)-a(n-37)+a(n-39)-a(n-40)+a(n-42)

84 a(n)=2*a(n-1)-a(n-2)+2*a(n-3)-a(n-4)+2*a(n-5)-a(n-7)
85 a(n)=2*a(n-1)-a(n-2)+2*a(n-3)-a(n-4)+2*a(n-5)-a(n-6)+a(n-7)
86 a(n)=2*a(n-1)-2*a(n-7)+3*a(n-8)-a(n-9)
87 
a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)+a(n-6)+a(n-8)+a(n-13)+a(n-14)+a(n-15)+a(n-17)+a(n-19)+a(n-20)+a(n-22)+a(n-23)+a(n-26)+a(n-27)+a(n-28)

88 a(n)=2*a(n-1)-a(n-5)+2*a(n-6)-a(n-7)+a(n-8)-a(n-9)
89 a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)+a(n-6)+a(n-8)+a(n-11)
90 a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)+a(n-6)+a(n-8)+a(n-11)+a(n-12)-a(n-13)
91 a(n)=a(n-1)+2*a(n-2)+a(n-3)-2*a(n-4)-a(n-5)+a(n-6)+a(n-7)
92 a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)+a(n-6)+a(n-8)+2*a(n-11)-a(n-13)
93 a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)+a(n-6)+a(n-8)+a(n-10)
94 
a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)+a(n-6)+a(n-8)+a(n-10)+a(n-14)+a(n-15)+a(n-17)+a(n-18)+a(n-21)+a(n-22)+2*a(n-23)-a(n-24)

95 
a(n)=2*a(n-1)-a(n-2)+2*a(n-3)-a(n-4)+2*a(n-5)-a(n-6)+a(n-7)+a(n-10)-a(n-11)+a(n-12)+a(n-14)+a(n-19)-a(n-20)+a(n-21)+a(n-24)+a(n-27)+a(n-29)-a(n-30)+a(n-31)+a(n-33)+a(n-35)

96 a(n)=a(n-1)+2*a(n-2)-a(n-7)
97 
a(n)=2*a(n-1)-a(n-7)+a(n-8)-a(n-9)+a(n-10)-a(n-11)+a(n-12)-a(n-15)+a(n-18)-a(n-19)+a(n-20)-a(n-24)+a(n-25)

98 
a(n)=a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-5)+a(n-6)+a(n-8)+a(n-10)+a(n-11)+a(n-15)+a(n-16)+a(n-18)+a(n-21)-a(n-22)

99 a(n)=2*a(n-1)-a(n-7)+a(n-8)-a(n-9)+a(n-10)-a(n-12)+a(n-13)-a(n-14)+a(n-16)