# two successive zeros

I am trying to solve a programming problem, but i dont know how to find number of numbers that dont contain two successive zeros. Please help me. for deeper understanding i included part of the problem in message.

Let’s consider K-based numbers, containing exactly N digits. We define a number to be valid if its K-based notation doesn’t contain two successive zeros. For example:

1010230 is a valid 7-digit number;
1000198 is not a valid number;
0001235 is not a 7-digit number, it is a 4-digit number.


Thank you!

-
From your annotation, it appears you also want no leading zero. Is this correct? – Mario Carneiro Dec 18 '12 at 5:07
yes in case of leading zero it is other number – Arsen Dec 18 '12 at 5:09

Let $L(n)$ be the number of strings with an alphabet of $K$ characters that don't end in $0$ and don't have two successive $0$'s. Let $M(n)$ be the number of strings with an alphabet of $K$ characters that end in $0$ and don't have two successive $0$'s. Then $L(1)=K-1, M(1)=0$(because of no leading zero)$, L(n)=(K-1)(L(n-1)+M(n-1)), M(n)=L(n-1)$ the third because you can add any non-zero character to an acceptable string to get an acceptable string that doesn't end in zero, and you can add a zero to any acceptable string that doesn't end in zero to get an acceptable string that ends in zero. This makes a $2 \times 2$ matrix that takes $(L(n)\ M(n))^T$ to $(L(n+1)\ M(n+1))^T$ so you might find the eigenvalues and eigenvectors of that matrix. To get the final answer, you take $L(n)+M(n)$.

Added: to get a closed form we represent the recursion as $$\begin {pmatrix} L(n) \\ M(n) \end {pmatrix}=\begin {pmatrix} 9 & 9 \\ 1 & 0 \end {pmatrix}\begin {pmatrix} L(n-1) \\ M(n-1) \end {pmatrix}$$

This has eigenvalues $\lambda_{\pm}=\frac 32 (3 \pm \sqrt {13})$ with corresponding eigenvectors $\begin {pmatrix} 9+3\sqrt {13} \\ 1 \end {pmatrix},\begin {pmatrix} 9-3\sqrt {13} \\ 1 \end {pmatrix}$. Starting from $\begin {pmatrix} L(0) \\ M(0) \end {pmatrix}=\begin {pmatrix} K-1 \\ 0 \end {pmatrix}$ we get $$\begin {pmatrix} L(n) \\ M(n) \end {pmatrix}= \frac{K-1}{6\sqrt{13}}\begin {pmatrix} 9+3\sqrt {13} \\ 1 \end {pmatrix}\lambda_+^n-\frac{K-1}{6\sqrt{13}}\begin {pmatrix} 9-3\sqrt {13} \\ 1 \end {pmatrix}\lambda_-^n$$

-
Don't you want $L(1)=K-1$? Since there are $K$ possible strings of length $1$, $L(1)+M(1)=K$. – Mario Carneiro Dec 18 '12 at 5:23
@MarioCarneiro: You are right. OP said leading zeros were not allowed, so I subtracted it, but the correct one is M(1)=0, leaving only $K-1$ strings of length $1$. Will fix. – Ross Millikan Dec 18 '12 at 5:29
But your definition says $M(n)$ is the number of strings that end in zero. Thus $M(n)=1$ and $L(n)=K-1$. I assumed the reason for defining both functions was to assist in the recursion, and then to take $L(n)$ as the answer at the end. BTW, is there a closed-form solution? – Mario Carneiro Dec 18 '12 at 5:35
I have tryed to implement this solution but for example N=5 K=10 output is 79461 but the right answer is 87480. even for N=2, K=10 the output is 81 but must be 90 – Arsen Dec 18 '12 at 5:42
@Arsen: I forgot to say that you need to add together $L(n)$ and $M(n)$ to get the answer, as all the strings in $M$ also count. So for $N=2, K=10, L(2)=81, M(2)=9$ for a total of $90$. For $N=5, K=10,$ I get $L(5)=79461, M(5)=8019$, for a total of $87480$ – Ross Millikan Dec 18 '12 at 14:02

To count the $k$-ary strings (that is, strings on the alphabet $0, 1, 2, \ldots, k-1$) of length $n$ with no two $0$'s in a row that do not start with $0$, first choose the number of nonzero digits we would like to have - call this $m$. Then choose any string on $m$ digits using the digits $1, 2, \ldots, k-1$ (but not $0$). Now choose any subset of size $n-m$ of these digits, and insert a $0$ to the right of each. The result is a string that does not start with $0$ and has no two $0$'s adjacent, and every such string is attained uniquely with this process. This gives the answer

$$\sum_{m=0}^n (k-1)^m {m \choose {n-m}}.$$

-