Brilliant Binary Being Batty

Relevant wiki: Linear Recurrence Relations - Problem Solving

The number of sequences of length $k$ that can be put together out the single digit $1$ and the digit pair $10$ is equal to the $(k+1)$ st Fibonacci number $F_{k+1}$ (defined with $F_0=0$ , $F_1 = 1$ , $F_2 =1$ , ...). This is a pretty standard result.

It is clear that $S_2 = 1$ and that $S_3 = 3$ . Suppose now that $k \ge 2$ .

In a Brilliant binary sequence of length $2k$ , the subsequence of the $2$ nd, $4$ th, $6$ th, ..., $(2k)$ th digits cannot contain repeating $0$ s, and the second digit must be $1$ . The number of such subsequences is the the number of sequences of length $k$ that can be put together out of the single digit $1$ and the digit pair $10$ , namely $F_{k+1}$ . Similarly, the subsequence of the $1$ st, $3$ rd, $5$ th, ..., $(2k-1)$ st digits cannot contain repeating $0$ s, and the $(2k-1)$ st digit must be $1$ . There are $F_{k+1}$ such subsequences. Thus we deduce that $S_{2k} = F_{k+1}^2$ .

In a Brilliant sequence of length $2k+1$ , the subsequence of the $1$ st, $3$ rd, $5$ th, ..., $(2k+1)$ st digits cannot contain repeated $0$ s, and is of length $k+1$ . But this is the number of sequences of length $k+2$ that can be put together out of the single digit $1$ and the digit pair $10$ (just add a $1$ to the start to see why), and so there are $F_{k+3}$ such subsequences. Similarly, the subsequence of the $2$ nd, $4$ th, $6$ th, ..., $(2k)$ th digits cannot contain repeating $0$ s, and the second and $(2k)$ th digits must both be $1$ . This is just the collection of sequences of length $k-1$ that can be put together from the single digit $1$ and the digit pair $10$ , with an extra digit $1$ added to the end. Thus there are $F_k$ such sequences. Thus we deduce that $S_{2k+1} = F_{k+3}F_k$ .

Since $S_{2k} \; = \; F_{k+1}^2 \qquad \qquad S_{2k+1} \; = \; F_{k+3}F_k \qquad \qquad k \ge 2 \;,$ it merely remains to find the smallest value of $k$ for which $S_k$ is divisible by $20$ . This happens with $S_{25} = 87840$ , and so the answer is $\boxed{25}$ . The next batty number is $S_{28} = 372100$ .

We could note that $F_k \equiv 0 \pmod 2$ provided that $k \equiv 0 \pmod 3$ , and that $F_k \equiv 0 \pmod 5$ provided that $k \equiv 0 \pmod 5$ . From these observations and the Chinese Remainder Theorem we can deduce that $S_k \equiv 0 \pmod {20}$ provided that $k \ge 2$ and $k \equiv 1\,,\,25\,,\,28 \pmod {30}$ . The batty numbers are those $k \ge 2$ which are congruent to one of $1$ , $25$ or $28$ modulo $30$ .