Palabra problema con funciones generatrices

Question

Pregunta

Deje $(a_n)_{n\geq 0}$ será cada vez más una secuencia de enteros no negativos tales que cada entero no negativo, se puede expresar de forma única en el formulario de $a_i+2a_j+4a_k$ donde $i,j,k$ no son necesariamente distintos. Calcular $a_{1998}$.

Mi intento

Poner $A(x)=\sum_{j\geq 0}x^{a_j}$ y traducir la condición dada en el lenguaje de la generación de funciones de rendimiento que $$ \frac{1}{1-x}=A(x)a(x^2) (x^4).\tag{0} $$ Sustituyendo $x^2$ en lugar de $x$ en $(0)$ de los rendimientos que $$ \frac{A(x)a(x^2) (x^4)}{1+x}=\frac{1}{1-x^2}=A(x^2) (x^4) (x^8)\etiqueta{1} $$ Por lo $A(x)=(1+x)A(x^8)$. La iteración obtenemos que $$ Una(x)=\prod_{j\geq0}(1+x^{8^j})=\sum_{j\geq0}x^{a_j}.\la etiqueta{2} $$ Mi Problema

Pero yo soy no sé cómo deducir $a_{1998}$ de $(2)$. Cualquier ayuda es muy apreciada.

Answer 1

Prefiero ir de baja tecnología, en este caso - encontrar un par de valores, a continuación, busque un patrón. Claramente tenemos $a_0=0$ como $0+2\cdot 0+4\cdot 0$ es la única manera de conseguir cero, $a_1=1$. Tenemos todo lo que hasta $7$ de que manera, pero $8$ es demasiado grande, por lo $a_2=8$. ¿Qué es lo próximo? Bueno, no podemos obtener $9$; necesitamos una copia de $8$ , pero el resto de $1$ no puede ser encontrado a partir de la $2$ e $4$ múltiplos de sobra. Por lo tanto $a_3=9$.

Después de eso, es mucho tiempo - todo a $63=9+2\cdot 9+4\cdot 9$ obras. Que deja a $x_4=64$ - y, de forma similar a cómo teníamos $9$, tenemos $x_5=65$.

OK, veo que el patrón de ahora tomemos todo con una base de 8 de expansión que consta completamente de ceros y unos. Comprobación... podemos construir una suma de cualquier número entero no negativo "dígito" por "dígito", usando lo que ya sabemos acerca de la construcción de $0$ través $7$ de los ceros y los unos. Todo el paquete con el mismo multiplicador juntos, y no lo es.

Bien, ¿cómo podemos extraer un elemento de la secuencia de un índice en particular? Escribirlo en base $2$, lo leí en base $8$. Para $1998$, que $$8^{10}+8^9+8^8+8^7+8^6+8^3+8^2+8^1 = 1227096648$$

Answer 2

Enfoque agradable! Para terminar, en primer lugar compruebe que su expresión es compatible con la condición de que el $a_j$ estrictamente aumento de la con $j$. Usted puede hacer esto mediante la demostración de que todos los coeficientes en el finito producto $$ P_k(x)=\prod_{j=0}^k\left(1+x^{8^j}\right)=(1+x)\left(1+x^8\right)\left(1+x^{64}\right)\ldots\left(1+x^{8^k}\right) $$ la igualdad de $0$ o $1$, el uso de la inducción en $k$. Puedes utilizar ese $1+8+64+\ldots+8^k<8^{k+1}$.). Usted, de hecho, han logrado más, en haber demostrado que el $a_j$ son precisamente los enteros no negativos cuya base-$8$ representación sólo utiliza los dígitos $0$ e $1$.

Así que ahora usted necesita el $1998^\text{th}$ tales entero (con $0$ siendo el cero). La primera será el $1_8=1$; la segunda se $10_8=8$; el tercero, a $11_8=9$. Ahora debería ver la receta en jmerry la respuesta se aplica.

Answer 3

Si es correcta su fórmula de A(x), <span class="math-container">$a_j$</span> es la suma de potencias distintas de ocho. Pero 1998 es congruente con 6 mod 8 y así no se puede escribir de esta manera.

Por lo tanto <span class="math-container">$a_{1998} = 0$</span>.