¿Es el vínculo entre Stern ' secuencia diatómico s y binario subsecuencias genuino o una coincidencia con excepciones?

Question

En una hermana de la pila, Martin Ender planteó una pregunta acerca de la función siguiente:

Vamos a definir una función de $f(N)$ sobre los enteros a través del siguiente algoritmo. Utilizaremos $N = 38$ como un ejemplo:

1. Obtener la representación binaria de $N$: $[1,0,0,1,1,0]$.
2. Tomar todas las subsecuencias de esta lista. Estos no necesitan ser contiguas, por lo $[1,1,1]$ es válido larga, por ejemplo. No olvides incluir el vacío larga: $$\{[], [1], [0], [0], [1], [1], [0], [1,0], ..., [1,0,1,1], \ldots, [1,0,0,1,1,0]\}$$
3. Convertir cada subsequence de nuevo a un número entero por medio de un tratamiento como una lista de bits. $[]$ debería ser cero: $$\{0, 1, 0, 0, 1, 1, 0, 2, \ldots, 11, \ldots, 38\}$$
4. Cuenta cuántos valores distintos de obtener. Los valores distintos en este caso son: $$\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 14, 18, 19, 22, 38\}$$ That's $17$. This is $f(N)$.

...

Esta secuencia parece ser idéntica a A007306, excepto que el índice es off-by-one (A007306 comienza con un adicional de 1)

Es realmente el caso que $f(N) = \textrm{A007306}(N+1)$, o que es sólo una coincidencia, que vale para un montón de números, pero tiene excepciones?

Answer 1

Es realmente el caso que $f(n) = \textrm{A007306}(n+1)$.

Para empezar, vamos a tomar la observación

Excepto para el nivel inicial, este es el extraño interseccion de A002487. - Franklin T. Adams-Watters, 25 De Mayo De 2015

Estamos muy felices de desechar el nivel inicial, debido a que resuelve el desplazamiento problema! A002487 es de Popa de diatómico secuencia y tiene el simple recurrencia $$\begin{eqnarray}\textrm{A002487}(0) & = & 0 \\ \textrm{A002487}(1) & = & 1 \\ \textrm{A002487}(2n) & = & \textrm{A002487}(n) \\ \textrm{A002487}(2n+1) & = & \textrm{A002487}(n) + \textrm{A002487}(n+1)\end{eqnarray}$$

Ya que queremos para bisecar, vamos a definir $N(k) = \textrm{A002487}(2k)$ $D(k) = \textrm{A002487}(2k+1)$ (para el numerador y el denominador, respectivamente). Entonces tenemos $$\begin{eqnarray}N(0) & = & 0\\ D(0) & = & 1\\ N(2k) & = & N(k) \\ D(2k) & = & N(k) + D(k) \\ N(2k+1) & = & D(k) \\ D(2k+1) & = & D(k) + N(k+1) \end{eqnarray}$$

Endeudamiento otra observación de OEIS,

$(\textrm{A002487}(n-1) + \textrm{A002487}(n+1))/\textrm{A002487}(n) = \textrm{A037227}(n)$ $n \ge 1$ . - Pedro Bala, Feb 07 De 2017

y desde $\textrm{A037227}(2k+1) = 1$ todos los $k$,$N(k) + N(k+1) = D(k)$, por lo que podemos reescribir este último caso como $$D(2k+1) = 2D(k) - N(k)$$

---

Ahora, consideremos $f(n)$ como se define en la OP. Deje $S_n$ el conjunto de los distintos valores obtenidos en el paso 4. Las subsecuencias que generan $S_{2k+i}$ $i \in \{0,1\}$ son las subsecuencias que generan $S_k$ y cada una de las subsecuencias con un $i$ anexa, y así tenemos un proceso iterativo de definición: $$\begin{eqnarray}S_0 & = & \{0\} \\ S_{2k} & = & S_k \cup \{2x \mid x \in S_k\} \\ S_{2k+1} & = & S_k \cup \{2x+1 \mid x \in S_k\} \end{eqnarray}$$

Podemos partición $S_n$ en cuatro subgrupos y, por tanto, la partición de $f(n) = |S_n|$ en cuatro tupla $(a_n, b_n, c_n, d_n)$ donde $$\begin{eqnarray} a_n = |\{x \mid x \in S_n \wedge 2x \in S_n \wedge 2x+1 \not\in S_n \}| \\ b_n = |\{x \mid x \in S_n \wedge 2x \not\in S_n \wedge 2x+1 \in S_n \}| \\ c_n = |\{x \mid x \in S_n \wedge 2x \in S_n \wedge 2x+1 \in S_n \}| \\ d_n = |\{x \mid x \in S_n \wedge 2x \not\in S_n \wedge 2x+1 \not\in S_n \}| \\ \end{eqnarray}$$

Entonces tenemos una simple recurrencia $$\begin{eqnarray}(a_0, b_0, c_0, d_0) & = & (1, 0, 0, 0) \\ (a_{2k}, b_{2k}, c_{2k}, d_{2k}) & = & (a_k + d_k, 0, b_k + c_k, b_k + d_k) \\ (a_{2k+1}, b_{2k+1}, c_{2k+1}, d_{2k+1}) & = & (0, b_k + d_k, a_k + c_k, a_k + d_k) \end{eqnarray}$$

Claramente $c_k = d_k$ todos los $k$, lo que simplifica las cosas un poco.

Definir $\nu_k = b_k + c_k$$\delta_k = a_k + b_k + 2 c_k = f(k)$. Entonces tenemos $$\begin{eqnarray}\nu_0 &= & 0 \\ \delta_0 & = & 1 \\ \nu_{2k} & = & b_k + c_k = \nu_k \\ \delta_{2k} & = & a_k + 2b_k + 3c_k = \nu_k + \delta_k \\ \nu_{2k+1} & = & a_k + b_k + 2c_k = \delta_k \\ \delta_{2k+1} & = & 2a_k + b_k + 3c_k = 2 \delta_k - \nu_k \end{eqnarray}$$

Por lo tanto $(\nu_k, \delta_k)$ sigue la misma recurrencia como $N(k), D(k)$ de las mismas condiciones iniciales, y por lo tanto es idéntico. QED.

---

Una más de combinatoria prueba sería bueno. Me pregunto si un enfoque alternativo se puede encontrar en Calkin y Wilf alternativa del conjunto de bits teorema, que sin duda parece conceptualmente vinculado.