0
$\begingroup$

The problem is: Find the number of binary strings (strings composed of just $1$s and $0$s) of length $n$ such that the substrings "$111$" and "$101$" are not contained within them.

In this question, $n$ can be up to $10^{18}$, and the code must finish in two seconds (C++, around $4 \cdot 10^8$ computations).

I found a way to use recurrences that can do up to around $n = 10^7$, but clearly this was not enough.

$\endgroup$
9
  • 2
    $\begingroup$ Can you share your recursion? If you can write it in the form $\vec{x}_{k+1} = A\vec{x}_k$ where $\vec{x}_k$ is a vector and $A$ is a fixed matrix, then you can compute $\vec{x}_n = A^n\vec{x}_0$ by using "binary exponentiation" to quickly compute $A^n$. $\endgroup$
    – JimmyK4542
    Jan 16 at 1:49
  • $\begingroup$ The Recursion is $a_n = a_{n-1} + c_{n-1}, b_n = a_{n-1}, c_n = b_{n-1} + d_{n-1}, d_n = b_{n-1}$. So the matrix would be 1010,1000,0101,0100.. $\endgroup$ Jan 16 at 2:02
  • 2
    $\begingroup$ It's A006498 so you can write it as $4$-th order linear recurrence, then you can use the suggested approach. $\endgroup$
    – Sil
    Jan 16 at 2:04
  • 3
    $\begingroup$ Are you sure you are supposed to calculate the exact numbers? For $n=10^{18}$, the answer would have around $10^{17}$ digits $\endgroup$
    – anankElpis
    Jan 16 at 2:15
  • 1
    $\begingroup$ If you solve the recurrence and have an arbitrary precision tool like Alpha or Mathematica the fact that the answer has $10^{17}$ digits is just time and memory. Whether it fits in the age and volume of the universe is left as an exercise. $\endgroup$ Jan 16 at 3:29

1 Answer 1

2
$\begingroup$

Let's look at this as "How many binary strings do not contain two $1$s with exactly one space separating them".

The amount of new strings added with each additional $n+1$ is proportional to the $(0/1)$ ratio of the number $n-1$ (considering all valid strings of length $n$) and is in turn the proportion of $(0/1)$ at $n+1$ itself effecting the strings added at $n+3$.
In other words$$ n+1 = (n) (1+ {0_{n-1}\over n}) $$ where $0_{n-1}$ just means the number of strings of length $n$ with an $0$ at the $n-1$ spot.
For $n=3,4$ we double only the strings that have a $0$ in the first or second spot respectively so we multiply by $3 \over 2$ . For $n=5,6$ we double ${2 \over 3}$ of our strings so we multiply by $5 \over 3$.

i.e. for $n=11$ we have $${2 \over 1} \cdot {2 \over 1}\cdot {3 \over 2} \cdot {3\over 2} \cdot {5 \over 3} \cdot {5 \over 3} \cdot {8 \over5 } \cdot {8\over 5} \cdot {13 \over 8} \cdot {13 \over 8} \cdot {21 \over 13}= 273$$

The Fibonacci sequence. Since everything cancels out except the final two terms the solution is simply the product of the final two numerators.

$\implies $ When $n$ is even the solution is the square of the ${n \over2}+2$ term of the Fibonacci sequence $$(F_{{n \over 2}+2})^2$$

$\implies$When $n$ is odd the solution is the product $$F_{{n+1\over 2}+2} \cdot F_{{n-1\over 2}+2} $$

EDIT
What if we simplify the question and just ask how many binary strings of length $n$ do not contain the substring $11$?
Now to calculate $n+1$ we use the (0/1) ratio of $n$ itself. $$n+1 = (n)(1+{0_n\over n})$$ which gives us $${2 \over 1} \cdot {3 \over 2} \cdot {5 \over 3} \cdot {8 \over5 } \cdot {13 \over 8} \cdot {21 \over 13}...$$ so our final solution will just be $$F_{{n}+2}$$ Which seems a nice way of getting the fibonacci sequence while avoiding the moral dilemmas of experimenting on rabbits.

Please feel free to edit this...

$\endgroup$
6
  • $\begingroup$ I don't understand how you are producing longer strings from shorter ones. Usually we extend at the end based on what came just before so we multiply by small whole numbers depending on how the current string ends. Here I would make four coupled recurrences based on the last two digits of the current string. $\endgroup$ Jan 16 at 14:55
  • $\begingroup$ To add one new digit, if the current string ends 00 we can add either digit. If it ends 01 we can add either digit. If it ends 10 we have to add 0. If it ends 11 we have to add 0. Compute the number of good strings of each length and type based on the numbers for one shorter. You can then often combine them into one grand recurrence. These have the look that the Fibonacci numbers might be right, but I haven't done it. $\endgroup$ Jan 16 at 15:01
  • $\begingroup$ I don't understand how you are producing strings of length $n+1$ from strings of length $n$. Are you doubling one of the existing $0$s? That is suggested to me by the fact that you say it depends on the proportions of 1s and 0s in the current string. I think the strings of length n will vary in how many 1s and 0s there are. A string of all 0s is certainly good. $\endgroup$ Jan 16 at 15:07
  • $\begingroup$ @RossMillikan To reword it. My idea here Basically is when we add $n+1$ we can always look at the number $2$ less than the one we are adding and see what the ratio of $(0/1)$ is for that number taken over all possible valid strings of length $n$. This works since we double any string that has a $0$ at $n-1$ but we do not double any string that has a $1$ at $n-1$. $\endgroup$ Jan 16 at 15:09
  • $\begingroup$ @RossMillikan For example if we are going from $n=6$ to $n=6+1$ since the ratio of $n=6-1$ is $5\over 3$ which means two $1$s for every three $0$s we need to multiply by $8 \over 5$ since we can only double the zero strings. $\endgroup$ Jan 16 at 15:16

You must log in to answer this question.

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