Esto sin duda está lejos de ser una respuesta completa, pero espero que sea útil. Voy a tratar de describir mi proceso de pensamiento, de modo que no parece que este salió de la nada.
La experimentación
Me fijo $p=3$ y en un principio se trató de examinar $a=0$ y $a=1$, aprovechando el corolario de Lucas Teorema de la cuestión que enlaza. Utilizar el color negro para "raro" y blanco para, incluso, llegué a tablas como la siguiente para los pequeños $n$. $n=0$ es la parte superior izquierda de la tabla, $n=3$ es la parte superior derecha, $n=31$ es la parte inferior derecha. Dentro de una tabla, cada fila es un valor de $k$ (a partir de $0$) y cada columna tiene un valor de $x$:
($a=0$)
($a=1$)
Tenemos una linda patrones cuando $n$ es uno menos que una potencia de 2$$, especialmente en la parte superior izquierda de las tablas (cuando $x+k\le$ n) y para $a=0$, donde se ve sobre todo como el triángulo de Sierpinski o el Walsh de la matriz. De hecho, tras la inspección, la expresión es un poco raro para $x+k>n$ desde entonces $n-x$ descienda por debajo de $k$, pero $k-t$ sube a $k$. A partir de ahora me centraré sólo en $a=0$ para $x+k\le$ n.
Por ejemplo, la rotación de la imagen para $n=31$ nos da
Esto se ve bonito y sugerente, pero quizás sea un poco amplia. Podemos utilizar hexagonal llena los círculos para ver esto un poco mejor:
Ahora, con el fin de ver un patrón, se puede tratar de relacionar este tema con el $n=15$ caso, que es precisamente la cuarta parte superior de la imagen entera.
Pensé que centrarse en los siete aislados 1s (con puntos marrones) que apareció en $n=31$ "en" la gran diferencia de $n=15$. El uso de diferentes colores y algunos de la capa de trabajo en Gimp.
Esta foto es un poco difícil de analizar, pero, básicamente, al alinear las cosas así, el aislado 1s que aparecen de la nada están en los centros de $\pastilla$s con 0 en los vértices de $n=15$. De hecho, los centros de todos los $\pastilla$s (no sólo verticales) parecen seguir una regla simple: se trata de un $1$ si hay cero o dos $\pastilla$-vértices que son $1$ y y $0$ lo contrario. Los pequeños puntos que se encuentran bajo un gran punto a punto (de modo que ellos no son los centros de un $\pastilla de$) comparten el mismo valor.
Por desgracia, esta $\pastilla de$-en-toda-la dirección de la idea es un poco difícil de trabajar, y deja a un problema de recursividad en la parte inferior del triángulo. Si nos alineamos las cosas un poco más natural, obtenemos esto:
Que dejó claro que cada segunda fila de $n=31$ es una fila de $n=16$ pero con cada entrada se duplicó: (1,0,1) se convirtió en (1,1,0,0,1,1), etc.
La recurrencia
Poner estas ideas junto con un poco de ensayo y error me llevó a una recurrencia con la potencia de 2 en $n$ como un parámetro. Pero desde $n=15$ es la parte superior de $n=31$, etc. $n$ es en realidad no se necesita cuando está restringida a ser uno menos que una potencia de 2$$. Si la fila del triángulo de $r$ comienza en $1$, y la columna $c$ va desde $1$ $r$ inclusive, a la paridad de $b_{r,c}$ está dado por la siguiente (me confirmó el patrón de hasta $n=2^8-1$, pero esto es en última instancia una conjetura):
Para hacer la recurrencia de trabajo, establecer $b_{r,c}=0$ para $r<1$ o $c<1$ o $c>r$. A continuación, vamos a $R=\lceil r/2\rceil$ y $C=\lceil c/2\rceil$ Tenemos $b_{1,c}=1$ si $c=1$ y $0$ lo contrario. Entonces, para $r>1$, $b_{r,c}=b_{R,C}$ cuando $r$ es aún y cuando $r$ y $c$ son ambos impares. En el caso restante de $r>1$ donde $r$ es impar y $c$ es par, tenemos $b_{r,c}=f\left(b_{R-1,C} b_{R,C} b_{R,C+1},b_{R+1,C+1}\right)$ donde $f$ es una función que genera $1$ cuando dos o de cuatro de sus argumentos son $0$ y salidas $0$ lo contrario. (Por desgracia, algunos experimentos sugieren que cualquier natural recurrencia dependiendo en la mayoría de los tres términos anteriores no funciona).
Para conectar de nuevo el problema original, $c=x+1$ (por lo que $x=c-1$) y $r=x+k+1$ (por lo que $k=r-c$). Admito que no sé cómo empezar a resolver esta recurrencia, y OEIS no parece arrojar alguna luz sobre esto (aunque me presentó a la apariencia similar Walsh de la matriz). Asimismo, no se han comprobado que esto funciona para todo $n$ que son uno menos que una potencia de 2$$.
Bono
Aquí una foto de la $n=255$: