Una respuesta parcial: Este enfoque se basa en la generación de funciones. Deje $S(m)$ denotar los números enteros positivos $\leq m$ que no contienen tres consecutivas $6$. Calculamos $S(m)$ para potencias de $10$ y mostrar la siguiente es válido para $n\geq 0$:
\begin{align*}
S\left(10^n\right)=1+\sum_{j=0}^{n}9^j\sum_{k=0}^{j+1}\binom{j+1}{k}\binom{k}{n-j-k}[[n-j\geq k]]\tag{1}
\end{align*}
Utilizamos Iverson corchetes $[[P]]$ con el fin de filtrar los casos no válidos. Equivalentemente, podemos usar $\min\{j+1,n-j\}$ como límite superior del interior de la suma en lugar de $j+1$. Empezamos con
Smirnov palabras:
Contamos el número de palabras de longitud $n$. Se parte de la consideración de las palabras con que no consecutivos iguales dígitos en todas.
Estas palabras se llaman Smirnov palabras o Carlitz palabras. (Véase el ejemplo III.24 Smirnov palabras de la Analítica de la Combinatoria de Philippe Flajolet y Robert Sedgewick para obtener más información.)
De generación en función del número de Smirnov palabras lo largo de los diez dígitos $\{0,1,2,\ldots,9\}$ está dado por
\begin{align*}
\left(1-\frac{10z}{1+z}\right)^{-1}\tag{1}
\end{align*}
La generación de la función: $A(z)$
Ya no hay restricciones para los dígitos $\{0,1,2\ldots,9\}\setminus\{6\}$, se reemplazan las apariciones de estos dígitos en un Smirnov palabra por cualquier ejecuta con una longitud de $\geq 1$.
\begin{align*}
z&\longrightarrow z+z^2+z^3+\cdots=\frac{z}{1-z}\tag{2}\\
\end{align*}
Ya que nos permite utilizar pistas de $6$ hasta la longitud de la $2$ sustituimos
\begin{align*}
z&\longrightarrow z+z^2\tag{3}\\
\end{align*}
Obtenemos sustituyendo (2) y (3) en (1) de generación de la función de $A(z)=\sum_{n=0}^\infty a_nz^n$
\begin{align*}
A(z)&=\left(1-9\cdot\frac{\frac{z}{1-z}}{1+\frac{z}{1-z}}-\frac{z+z^2}{1+z+z^2}\right)^{-1}\\
&=\frac{1+z+z^2}{1-9z(1+z+z^2)}\tag{4}\\
&=1+10z+100z^2+999z^3+\color{blue}{9\,981}z^4+99\,720z^5\cdots\tag{5}
\end{align*}
con $a_n$ dando el número de todas las palabras de longitud $n$ que consiste en la $10$ dígitos $0-9$ no tener subcadena $666$. El coeficiente de en (5) se calcula con la ayuda de Wolfram Alpha.
Ejemplo: $n=4$:
El número de cadenas de longitud $4$ es dado como $\color{blue}{9\,981}$ que cuenta el $10\,000$ palabras de longitud $4$ menos los siguientes $19$palabras:
\begin{align*}
0666\ 1666\ 2666\ 3666\ 4666\ 5666\ 6666\ 7666\ 8666\ 9666\\
6660\ 6661\ 6662\ 6663\ 6664\ 6665\ \ \qquad 6667\ 6668\ 6669
\end{align*}
No queremos contar palabras con ceros a la izquierda. Denotando con $[z^n]$ el coeficiente de $z^n$ de una serie que nos tiene que restar $[z^{3}]A(z)$.
El número de palabras de longitud $4$es
\begin{align*}
\left([z^4]-[z^{3}]\right)A(z)=9\,981-999=8\,982
\end{align*}
El número de todas las palabras válidas de longitud $\leq 4$ es aún más simple, ya que es
\begin{align*}
&\left([z^4]-[z^{3}]\right)A(z)+\left([z^3]-[z^{2}]\right)A(z)+\left([z^2]-[z^{1}]\right)A(z)\\
&\qquad+\left([z^1]-[z^{0}]\right)A(z)+[z^0]A(z)\\
&\qquad=[z^4]A(z)\\
&\qquad\color{blue}{=9\,981}
\end{align*}
Llegamos a la conclusión de
\begin{align*}
\color{blue}{S(10^4)}=1+S(9999)=1+[z^4]A(z)\color{blue}{=9\,982}\tag{6}
\end{align*}
y un general, tenemos $S(10^n)=1+[z^n]A(z)$ para $n\geq 0$.
Cálculo de $S(10^n)$:
Con el fin de encontrar una fórmula explícita para $S(10^n)$ calculamos el coeficiente de $[z^n]A(z)$ a partir de la representación (4). Obtenemos
\begin{align*}
\color{blue}{[z^n]}&\color{blue}{\frac{1+z+z^2}{1-9z(1+z+z^2)}}\\
&=[z^n]\sum_{j=0}^\infty9^jz^j(1+z+z^2)^{j+1}\tag{7}\\
&=\sum_{j=0}^n9^j[z^{n-j}](1+z(1+z))^{j+1}\tag{8}\\
&=\sum_{j=0}^n9^j[z^{n-j}]\sum_{k=1}^{j+1}\binom{j+1}{k}z^k(1+z)^k\tag{9}\\
&=\sum_{j=0}^n9^j\sum_{k=0}^{j+1}\binom{j+1}{k}[z^{n-j-k}](1+z)^k[[n-j\geq k]]\tag{10}\\
&\,\,\color{blue}{=\sum_{j=0}^n9^j\sum_{k=0}^{j+1}\binom{j+1}{k}\binom{k}{n-j-k}[[n-j\geq k]]}\tag{11}
\end{align*}
Llegamos a la conclusión de
\begin{align*}
S(10^n)=1+\sum_{j=0}^n9^j\sum_{k=0}^{j+1}\binom{j+1}{k}\binom{k}{n-j-k}[[n-j\geq k]]
\end{align*}
y la afirmación (1) de la siguiente manera.
Comentario:
En (7) utilizamos la serie geométrica de expansión.
En (8) aplicamos la regla de $[z^{p-q}]A(z)=[z^p]z^qA(z)$ y restringir el límite superior de la suma con $n$ desde mayores índices de no contribuir a que el coeficiente de $z^n$.
En (9) se expanda el binomio.
En (10) aplicamos la regla, tal como hicimos en (8) y asegurar con la ayuda de la Iverson soportes que el poder $n-j-k$ de $z$ es no negativo.
En (11) que finalmente seleccionar el coeficiente de $z^{n-j-k}$.
Ejemplo de $n=4$ revisited:
Ahora podemos calcular el $S(10^4)$ sin la ayuda de Wolfram Alpha y obtener
\begin{align*}
\color{blue}{[z^4]A(z)}&=\sum_{j=0}^49^j\sum_{j=0}^{j+1}\binom{j+1}{k}\binom{k}{4-j-k}[[4-j\geq k]]\\
&=9^0\sum_{k=0}^1\binom{1}{k}\binom{k}{4-k}+9^1\sum_{k=0}^2\binom{2}{k}\binom{k}{3-k}+9^2\sum_{k=0}^2\binom{3}{k}\binom{k}{2-k}\\
&\qquad+9^3\sum_{k=0}^1\binom{4}{k}\binom{k}{1-k}+9^4\sum_{k=0}^0\binom{5}{k}\binom{k}{0-k}\\
&=9^0\left[\binom{1}{0}\binom{0}{4}+\binom{1}{1}\binom{1}{3}\right]
+9^1\left[\binom{2}{0}\binom{0}{3}+\binom{2}{1}\binom{1}{2}+\binom{2}{2}\binom{2}{1}\right]\\
&\qquad +9^2\left[\binom{3}{0}\binom{0}{2}+\binom{3}{1}\binom{1}{1}+\binom{3}{2}\binom{2}{0}\right]\\
&\qquad+9^3\left[\binom{4}{0}\binom{0}{1}+\binom{4}{1}\binom{1}{0}\right]+9^4\left[\binom{5}{0}\binom{0}{0}\right]\\
&=1[0+0]+9[0+0+2]+81[0+3+3]+729[0+4]+6\,561[1]\\
&\,\,\color{blue}{= 9\,981}
\end{align*}
Obtenemos de acuerdo con (6)
\begin{align*}
\color{blue}{S(10\,000)}&=1+[z^4]A(z)\color{blue}{=9\,982}
\end{align*}
