Feynman del Algoritmo para calcular el logaritmo de un número en [1,2]

Question

Me encontré con la siguiente cita sobre Feynman (todo el ensayo, este puede ser encontrado aquí):

Considere el problema de encontrar el logaritmo de un número fraccionario entre 1.0 y 2.0 (el algoritmo se puede generalizar sin demasiada dificultad). Feynman observó que cualquier número puede ser únicamente representado como un producto de números de la forma $1 + 2^{-k}$ donde $k$ es un número entero. Las pruebas de cada uno de estos factores en un número binario de representación es simplemente una cuestión de un cambio y una resta. Una vez que los factores son determinados, el logaritmo puede ser calculada mediante la suma de los precalculadas los logaritmos de los factores. El algoritmo de ajuste especialmente bien en la Conexión de la Máquina, ya que la pequeña tabla de los logaritmos de $1 + 2^{-k}$ podría ser compartida por todos los procesadores. El cálculo completo tomó menos tiempo que la división.

He dado este la mitad de un pensamiento y buscado un poco en internet, y, básicamente, por hacer una "búsqueda binaria" algoritmo, se puede determinar lo que es un conjunto de factores. Ver esta pregunta en otro sitio SE. Sin embargo, no estoy convencido de la factorización es única, ya que no puedo pensar en un argumento. (Por otro lado, el método de búsqueda binario no parece la forma más elegante para calcular los factores).

Así que mi pregunta es, más precisamente, de la siguiente. Para ${\bf a} = (a_1, a_2, \dots ) \in \{0,1\}^{{\bf N}}$, muestran que cada número $x \in (1,2]$ está únicamente representado por un determinado $\bf{a}$ tal que $$x = \prod_{k=1}^\infty (1+a_k 2^{-k}).$$

Sé $$\prod_{k=1}^\infty (1+a_k 2^{-k}) = 1 + \sum_{k=1}^\infty \left(a_k + \sum_{1\leq i<j,i+j=k} a_i a_j \right) 2^{-k} = 1 + \sum_{k=1}^\infty b_k 2^{-k}$$ donde $b_k$ son los dígitos binarios de $x$, pero este no me da mucha penetración.

Answer 1

La representación no puede ser único como se indica. Considere la posibilidad de $1+\dfrac{1}{2}$, que tiene la representación evidente $(1,0,0,\ldots)$. Pero $(1+\dfrac{1}{2})/(1+\dfrac{1}{4})=1.2<1+\dfrac{1}{4}$, y así tendrá una representación de la forma $(0,0,1,\ldots)$. Por lo $1+\dfrac{1}{2}$ también tienen una representación $$(1+\dfrac{1}{4})\cdot (0,0,1,\ldots)=(0,1,1,\ldots)$$

El punto es similar a la conocida observación de que $1.=0.\overline{9}$ en decimal. En consecuencia, ningún número real de representación puede ser únicos, a menos que las restricciones adicionales impuestas (de hecho, esa es una importante técnica de punto en diagonal de Cantor argumento). Entonces, creo que la pregunta más interesante es ¿qué condiciones deben ser impuestas para obtener un único Feynman representación...