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

Ron Hardin rhhardin at att.net
Fri Sep 17 01:45:09 CEST 2010

```
> A surprisingly large number of these are in OEIS
>
> T(n,k) = Number of n-bit  binary strings with no initial substring
> representing a binary number  divisible by  k

recurrences found for k=3..33

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)

```