Spooky Numbers (Late Halloween Special)

Let us count the complement. Let $a_n$ be the number of non-spooky numbers that end in $1$ or $3$ . Let $b_n$ be the number of non-spooky numbers that do not end in $1$ or $3$ . Then we have the following recurrences:

$a_{n+1} = a_n+2b_n$

$b_{n+1} = 8(a_n +b_n )$

Since $a_1 = 2$ and $b_1=8$ , we can obtain that $a_4=1746$ and $b_4=7696$ . Thus, our desired answer is $10^4-(1746+7696) = 558$ .