2
$\begingroup$

Write a program to calculate the total number of strings that are made of exactly N characters. None of the strings can have "13" as a substring. The strings may contain any integer from "0-9", repeated any number of times.

From above question I derived a recursive equation which gives total "13" s as follow:

$$F_{n} = 10F_{n-1} + 10^{n-2} - F_{n-2}$$

I am trying to solve the problem using Fast Fibonacci Transform with O(logn) time complexity as described in this link.

Taking reference to this post I tried to convert the obtained recursive equation into matrix recursive form:

I need to find A such that:

$$\begin{bmatrix} F_n \\\ F_{n-1} \end{bmatrix} = A \begin{bmatrix} F_{n-1} \\\ F_{n-2} \end{bmatrix}$$

But because of the presence of 10n-2 I am not getting the constant.

My $A$ looks like the following:

$$ A = \begin{bmatrix} 10 & -10^{n-2} \\\ 1 & 0 \end{bmatrix}$$

Thus matrix $A$ is not constant.

What should I do in this case? Please shed some light

$\endgroup$
1
  • 1
    $\begingroup$ This is not correct. The first line of the matrix multiplication would give $F_n = 10F_{n-1} - 10^{n-2}F_{n-2}$, which is not your equation. A correct way to write matricially the equation would be :$ \begin{bmatrix} F_n \\\ F_{n-1} \end{bmatrix} = \begin{bmatrix} 10 & -1 \\\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_{n-1} \\\ F_{n-2} \end{bmatrix} + \begin{bmatrix} 10^{n-2} \\\ 0 \end{bmatrix}$. But again, it does not make appear only constant matrices. $\endgroup$
    – TheSilverDoe
    Commented Aug 25, 2020 at 11:06

2 Answers 2

Reset to default
3
$\begingroup$

The removal of the exponential term may be done by finding a particular solution to the recurrence. Letting $F_n=C\times10^n$, one has

$$C\times10^n=(C+0.01-0.01C)10^n$$

$$C=1.01C+0.01$$

$$C=-1$$

and thus we may consider $F_n=G_n-10^n$ to get

$$G_n=10G_{n-1}-G_{n-2}$$

$$\begin{bmatrix}G_n\\G_{n-1}\end{bmatrix}=\begin{bmatrix}10&-1\\1&0\end{bmatrix}\begin{bmatrix}G_{n-1}\\G_{n-2}\end{bmatrix}$$

$$\begin{bmatrix}G_{n+1}\\G_n\end{bmatrix}=\begin{bmatrix}10&-1\\1&0\end{bmatrix}^n\begin{bmatrix}G_1\\G_0\end{bmatrix}$$

and in terms of the original sequence,

$$\begin{bmatrix}F_{n+1}\\F_n\end{bmatrix}=\begin{bmatrix}10&-1\\1&0\end{bmatrix}^n\begin{bmatrix}F_1+10\\F_0+1\end{bmatrix}-10^n\begin{bmatrix}10\\1\end{bmatrix}$$

$\endgroup$
1
  • $\begingroup$ This is much better! $\endgroup$
    – nonuser
    Commented Aug 25, 2020 at 13:15
2
$\begingroup$

One solution is to add a dimension, and write $$ \pmatrix{F_n\\F_{n-1}\\1} = \pmatrix {10 & -1 & 10^{n-2} \\ 1 & 0 & 0 \\ 0 & 0 & 1 }\pmatrix{F_{n-1}\\F_{n-2}\\1} $$ Now at least you have a matrix multiplication. But as you'll surely note, that $10^{n-2}$ term isn't a constant. But you can fix that with $$ \pmatrix{F_n\\F_{n-1}\\10^{n-1}} = \pmatrix {10 & -1 & 10 \\ 1 & 0 & 0 \\ 0 & 0 & 10 }\pmatrix{F_{n-1}\\F_{n-2}\\10^{n-2}} $$

I can't say whether this'll help you or not, but it's at least a way to express the recurrence as a matrix multiplication.

$\endgroup$
6
  • $\begingroup$ Thank you for replying so promptly and sorry for being vague :). What I am trying to achieve is solve $$F_{n} = 10F_{n-1} + 10^{n-2} - F_{n-2}$$ for $n$ using fast Fibonacci transform algorithm with O(logn) time complexity as described here. brilliant.org/wiki/fast-fibonacci-transform. Can it be solved this way? $\endgroup$
    – wrufesh
    Commented Aug 25, 2020 at 12:50
  • $\begingroup$ also I derived the equation $F_{n}$ = $10F_{n-1}$ + $10^{n-2}$ - $F_{n-2}$ from the following question: Write a program to calculate the total number of strings that are made of exactly N characters. None of the strings can have "13" as a substring. The strings may contain any integer from "0-9", repeated any number of times. $\endgroup$
    – wrufesh
    Commented Aug 25, 2020 at 12:55
  • 1
    $\begingroup$ If solving that problem with the fast fibonacci transform (which I know nothing about) is what you want to do, you should ask a question saying "Can I solve this recurrence using the Fast Fibonacci transform?", not "how can I write this recurrence with a matrix product?" I answered the question you asked, which is pretty much all you can expect. $\endgroup$
    – John Hughes
    Commented Aug 25, 2020 at 13:02
  • 1
    $\begingroup$ @wrufesh This context should be included in the original post, not asked in the comments. $\endgroup$
    – Simply Beautiful Art
    Commented Aug 25, 2020 at 13:02
  • 2
    $\begingroup$ I will say that if I were to solve this problem, I'd let $U(n)$ be the number of no-13 sequences that don't start with $3$, and $V(n)$ be the number of no-13 sequences, and then write down a coupled equation for $U$ and $V$ together. Also, it looks to me as if the equation you wrote down might be the wrong one for the problem you're trying to solve (although I haven't thought through it in detail), so spending a lot of time trying to recast it with matrix multiplies might not be a good way to spend your time. $\endgroup$
    – John Hughes
    Commented Aug 25, 2020 at 13:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .