Ayuda con una recurrencia con términos pares e Impares

Question

Tengo la siguiente recurrencia que he estado machacando:

$$ a(0)=1\\ a(1)=1\\ a(2)=2\\ a(2n)=a(n)+a(n+1)+n\ \ \ (\forall n>1)\\ a(2n+1)=a(n)+a(n-1)+1\ \ \ (\forall n\ge 1) $$

No tengo mucha experiencia en resolver estas cosas, así que he estado buscando en Google diferentes técnicas. Por desgracia, aún no he podido aplicarlas correctamente. Hasta ahora lo he intentado:

• Ecuaciones características
• Generación de funciones
• Conectándolo a Wolfram Alpha
• Telescopio
• Observación

Estoy seguro de que uno o más de estos es el camino a seguir, pero mi mayor problema en este momento es averiguar cómo lidiar con la idea de que hay diferentes ecuaciones para impar e incluso valores de $n$ . No estoy buscando necesariamente una solución (aunque sería aceptada con gratitud), pero cualquier empujón en la dirección correcta sería muy apreciado.

---

Para continuar, resultó que el problema de velocidad descrito en mi comentario, más abajo, estaba relacionado con la implementación de Decimal en Python 2.7. El cambio a Python 3.3 (y Java) hizo que todo mejorara en muchos órdenes de magnitud.

Answer 1

Tengo una forma casi cerrada. Utiliza las funciones $z_2(n)$ que es el número de ceros en la representación binaria de $n$ (después del primer dígito distinto de cero, por supuesto) y $Z_2(n)=\sum_{i=1}^n z_2(n)$ . Estoy seguro de que se pueden calcular rápidamente, pero lo dejaré en sus manos.

---

Sección 1: Una forma cerrada para S(n).

A partir de la respuesta de Michael Biro, donde definen $S(n)=a(n+2)-a(n)$ y calcular que $S(2n)=S(n)+1$ y $S(2n+1)=S(n-1)$ podemos encontrar una forma cerrada para $S$ y luego encontrar una suma ordenada para ello.

En particular, reescribir Michaels dos propiedades como: $$S(n)=S(2n+3)=S(2n)-1.$$ y considera que esto mide la cantidad de números pares que pasamos mientras iteramos la función $f(2n+3)=n$ y $f(2n)=n$ . También tenemos las condiciones de borde $$S(0)=1$$ $$S(1)=2$$ $$S(2)=5$$ Ahora bien, esta relación trata claramente de algo que ocurre en binario - pero aún mejor que en binario es escribir $n$ en la base $2$ , encabezando con el dígito $1$ o $3$ y en caso contrario utilizando los dígitos $0$ y $3$ - lo que significa que la expansión de $2n$ es la expansión de $n$ con un $0$ y la ampliación de $2n+3$ es la expansión de $n$ con un $3$ anexa. Esto significa que el mapa $f$ ¡simplemente corta los últimos dígitos de esta representación! A continuación se presenta una tabla de estas representaciones: \begin {array}{ll} n & n_2 \\ 1 & 1 \\ 2 & 10 \\ 3 & 3 \\ 4 & 100 \\ 5 & 13 \\ 6 & 30 \\ 7 & 103 \\ 8 & 1000 \\ 9 & 33 \\ 10 & 130 \\ 11 & 1003 \\ 12 & 300 \\ 13 & 133 \\ 14 & 1030 \\ 15 & 303 \\ 16 & 10000 \\ 17 & 1033 \\ \end {array} Lo que es notable es que si el patrón comienza con "3", entonces iterará a $0$ en $f$ después de un cierto número de pasos, es decir $S(n)$ sería el número de $0$ s en la expansión (cuántas veces la órbita de $n$ en $f$ pasado por los números pares), más $S(0)=1$ . Si el patrón comienza con "10", entonces $n$ primero pasa por $2$ en $f$ Así que $S(n)$ sería el número de ceros en la expansión (excluyendo el primero utilizado en el patrón "10") más $S(2)=5$ . Si el patrón comienza con "13", entonces $n$ pasa a través de $1$ en $f$ y así $S(n)$ es igual al número de ceros del patrón, más $S(1)=2$ .

Esto parece un poco intimidante para empezar, pero en realidad no está tan mal. Fíjate en que si cortamos el dígito más significativo de nuestra representación, la representación resultante es divisible por $3$ ya que sólo utiliza los dígitos $0$ y $3$ y, además, si lo dividimos por $3$ y lo escribimos en binario normal, es lo mismo que si sustituimos cada $3$ por un $1$ . Por lo tanto, si dejamos que $z_2(n)$ sea el número de ceros en la representación binaria normal de $n$ entonces podemos interpretar lo anterior de la siguiente manera, dejando que $2^b$ sea el valor posicional del $1$ en nuestra representación de $n$ si existe (lo que debe ocurrir si $3$ no divide $n$ ): $$S(n)=\begin{cases}z_2\left(\frac{n}3\right)+1&&\text{if }n\equiv 0\pmod 3 \\ z_2\left(\frac{n+2\cdot 2^b}3\right)+2&&\text{if }5\cdot 2^{b-1} \leq n \\ z_2\left(\frac{n+2\cdot 2^b}3\right)+4&&\text{if }n < 5\cdot 2^{b-1}\end{cases}$$ donde añadimos $2\cdot 2^b$ a $n$ para convertir el primer dígito de un $1$ a un $3$ y la condición de que $5\cdot 2^{b-1}\leq n$ es equivalente a la expansión de $n$ que comienza con "13". Requerimos saber $b$ para calcular lo anterior, pero notando que debemos tener que $$n=2^b+3\cdot k$$ para algunos $0\leq k \leq 2^b-1$ , lo que implica $2^b\leq n \leq 4\cdot 2^b - 3$ es obvio que $b$ debe ser $\lfloor\log_2(n)\rfloor$ o $\lfloor\log_2(n)\rfloor-1$ y que $n-2^b$ es divisible por $3$ . Así, podríamos escribir: $$b=\begin{cases}\lfloor\log_2(n)\rfloor && \text{if }2^{\lfloor\log_2(n)\rfloor}\equiv n\pmod 3\\\lfloor\log_2(n)\rfloor-1 && \text{if }2^{\lfloor\log_2(n)\rfloor-1}\equiv n\pmod 3\end{cases}.$$

Podríamos escribir rápidamente la expansión de algún número entero grande utilizando esta información. Digamos que queremos conocer la representación de $124315$ que es $1$ mod $3$ y está entre $2^{16}$ y $2^{17}-1$ así que $b'=16$ . Observamos que $124315-2^{16}$ es divisible por $3$ Así que sabemos que nuestra expansión tendrá un $1$ en el $2^{16}$ seguido de la representación binaria de $\frac{124315-2^{16}}3=1110010110011011_2$ con $1$ se sustituye por $3$ 's. Esto da: $$124315=13330030330033033_2$$

---

Sección 2: Una forma cerrada para $a(n)$

Vamos a tener que dividirnos en casos para esto, lo cual es molesto. En particular, a partir de la definición de $S$ obviamente lo hemos hecho: $$a(2n)=1+\sum_{i=0}^{n-1}S(2i)$$ $$a(2n+1)=1+\sum_{i=0}^{n-1}S(2i+1)$$ Empecemos por el caso par, porque es el que mejor funciona. En particular, reescribamos $S(2i)=S(i)+1$ y conseguir: $$a(2n)=1+\sum_{i=0}^{n-1}S(i)+1$$ lo que significa que estamos tomando la suma de $S$ sobre todos los números menores que $n$ . Para ello, basta con encontrar todas las representaciones de nuestro sistema que den un número menor que $n$ . Por comodidad, definiremos $[n]$ sea el mayor número entero estrictamente menor que $n$ (así $[5]=4$ por ejemplo). A continuación, llegamos a cuatro casos

1. En primer lugar, vamos a enumerar todas las representaciones que empiezan por "3". Esto equivale a enumerar todas las representaciones binarias menores que $\frac{n}3$ . Por lo tanto, ya que $S(3n)=z_2(n)+1$ si definimos $$Z_2(n)=\sum_{i=1}^{n}z_2(i)$$ entonces la contribución de estos $2\left[\frac{n}3\right]$ términos a la suma es: $$Z_2\left(\left[\frac{n}3\right]\right)+2\left[\frac{n}3\right]$$

2. A continuación, considere las representaciones que empiezan por "13". Elija $b_1$ sea tal que $5\cdot 2^{b_1-1}\leq n\leq 4\cdot 2^{b_1}-3$ que sería el valor posicional del $1$ en la mayor de dichas representaciones menor o igual a $n$ . Obsérvese que si el $1$ está en un valor de posición más bajo, pero la cadena todavía empezaba "13", entonces la representación seguiría siendo menor que $n$ ya que estaría acotado por encima de $2\cdot 2^{b_1}< 5\cdot 2^{b_1-1} \leq n$ . Por lo tanto, si tomamos un número binario menor que $\frac{n-2^{b_1}}{3}$ Si se convirtieran todos los 1s en 3s y se les antepusiera un "1", obtendríamos una representación válida que empezaría por "3". La contribución de estos términos a la suma sería: $$Z_2\left(\left[\frac{n-2^{b_1}}3\right]\right)+3\left[\frac{n-2^{b_1}}3\right]$$ Es posible que no haya ningún $b_1$ existe, en cuyo caso se elige $b_1$ para ser el mayor valor tal que $4\cdot 2^{b_1}-3<n$ , lo que significa que cualquier número con el $1$ en el lugar con valor $2^{b_1}$ obras, dando una contribución de $2^{b_1-1}-1$ términos como: $$Z_2\left(2^{b_1-1}-1\right)+3\cdot 2^{b_1-1}-3$$

3. Ahora, considera las representaciones que empiezan por "100". Elija $b_2$ sea tal que $$2^{b_2}\leq n \leq 7\cdot 2^{b_2-2}-3.$$ La contribución de estos términos será $$Z_2\left(\left[\frac{n-2^{b_2-1}}3\right]\right)+7\left[\frac{n-2^{b_2-1}}3\right]$$ o, si no hay tal $b_2$ existe, dejando que $b_2$ en cambio, sea el mayor valor tal que $2^{b_2}\leq n$ , dando una contribución de: $$Z_2\left(2^{b_2-2}-1\right)+7\cdot 2^{b_2-2}-7$$

4. Por último, consideramos la representación que empieza por "103". Elija $b_3$ sea tal que $7\cdot 2^{b_3-2}\leq n \leq 5\cdot 2^{b_3-1}-3$ . La contribución de estos términos será $$Z_2\left(\left[\frac{n-2^{b_3}}3\right]\right)+6\left[\frac{n-2^{b_3}}3\right]$$ y si no hay tal $b_3$ existe, elija el más grande tal que $7\cdot 2^{b_3-2}<n$ . Entonces, la contribución será: $$Z_2\left(2^{b_3-2}-1\right)+6\cdot 2^{b_3-2}-1.$$

5. Todavía no hemos contado las cadenas "10", y "1". Contribuyen $9$ a la suma (suponiendo que $n>2$ ).

Ahora bien, si se suman todas esas contribuciones, haciendo la gran suposición de que no he cometido ni un solo error de cálculo en todo este post, se debería obtener $a(2n)$ . En realidad no vale la pena compilarlos en una sola ecuación, ya que hay esencialmente $8$ casos. Te dejaré los casos de impar, pero debería proceder de forma análoga. Sólo tienes que calcular $Z_2(n)$ rápidamente, pero creo que esto es probablemente bastante fácil ya que tiene la identidad: $$Z_2(2^{k}-1)=k\cdot (2^{k-1}-1)$$ y debería tener bonitas identidades para $Z_2(2^{k_1}+2^{k_2}-1)$ y así sucesivamente a medida que especificamos más dígitos. (Todavía hay que hacer un cálculo sustancial aquí, pero debería tomar lineal tiempo en el número de dígitos, en lugar de tiempo cuadrático, como tardaría el algoritmo ingenuo)

Answer 2

Esto no es una respuesta completa, pero podría hacer una solución más manejable.

Definir $S(n) = a(n+2) - a(n)$ . (Para su información, no he podido encontrar $S(n)$ secuencia en OEIS tampoco)

Entonces, obtenemos que

$S(2n) = a(2n+2) - a(2n) = a(n+2) + a(n+1) + (n+1) - a(n+1) - a(n) - n = a(n+2) - a(n) + 1 = S(n) + 1$

y

$S(2n+1) = a(2n+3) - a(2n+1) = a(n+1) + a(n) + 1 - a(n) - a(n-1) - 1 = a(n+1) - a(n-1) = S(n-1)$

Así que la recurrencia para $S(2n) = S(n) + 1$ y $S(2n+1) = S(n-1)$ . Esto todavía tiene una diferencia de paridad en la recursión, pero es un poco más simple.

Estuve un rato intentando elaborar una solución tipo problema de Josefo para $S(n)$ con resultados parciales (es decir, si $n = 2^k + 3(2^j-1)$ con $0 \leq j < k$ y $2 \leq k$ entonces $S(n) = k - j + 4$ ). Como mínimo, esto demuestra que las diferencias entre $a(n+2)$ y $a(n)$ varían entre pequeños valores constantes y valores ascendentes en torno a $\log n$ .

Answer 3

Sólo para ahorrar a los demás el cálculo de la secuencia, he aquí un programa para la primera $m$ términos:

package main
import "fmt"
const m = 100
func main() {
    a := [m]int{1, 1, 2}
    for i := 3; i < m; i++ {
        if i % 2 == 1 {
            h := (i - 1)/2
            a[i] = a[h] + a[h-1] + 1
        } else {
            h := i/2
            a[i] = a[h] + a[h+1] + h
        }
    }
    fmt.Println(a)
}

Para $m=100$ obtenemos

1 1 2 3 7 4 13 6 15 11 22 12 25 18 28 20 34 22 42 27 44 34 48 35 55 38 59 44 62 47 69 49 72 55 81 57 87 65 90 70 98 72 103 79 105 83 113 84 117 91 122 94 129 98 133 104 137 107 145 110 148 117 152 119 159 122 169 128 172 137 179 139 188 145 192 153 198 156 207 161 210 169 216 171 224 176 227 183 232 185 241 189 243 197 248 198 256 202 262 209

Esto no aparece en el sitio web de secuencias de números enteros.

Answer 4

Si se considera cada elemento y $a_0$ , $a_1$ , $a_2$ ,... Al final se ve $a_2$ es sólo y(0) $a_{0}$ . Y $a_3$ es sólo y(1) $a_{1}$ . $a_4$ = y(2)*y(0) $a_0$ . $a_5$ = y(3)*y(1) $a_1$ . Suponiendo que se obtenga una respuesta diferente para $a_0$ y $a_1$ . Siempre obtendrá resultados diferentes para entradas pares e Impares.