Función de Euler y de las sumas

Question

Me he encontrado con un pequeño problema combinatorio. En primer lugar tenemos el vector $(1, 1)$. En cada iteración para cada dos números consecutivos del vector añadimos la suma entre ellos: $$(1, 2, 1)$$ $$(1, 3, 2, 3, 1)$$ $$(1, 4, 3, 5, 2, 5, 3, 4, 1)$$ $$(1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1)$$ ad infinitum.

Aquí está la pregunta. Cuántas veces el número de $n$ será escrito en la final del vector? I v calculado con las respuestas de $1, \dots, 15$: $$2, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8$$

Y estos valores coinciden con los valores de Euler totient función. Pero, ¿cómo demostrar que la respuesta es siempre $\phi(n)$? Y puede uno simplemente se derivan de esta idea sin forma explícita escribiendo primero los valores?

Answer 1

Primero vamos a nombre de los vectores $v_1, v_2$ y así sucesivamente.

Primero de todo, podemos notar que los números consecutivos del vector son coprime por inducción. El caso base es trivial. Ahora suponga que tiene de $v_{n-1}$ y considerar la posibilidad de $v_n$. Deje $a,b$ número consecutivo en $v_n$. Entonces, debido a la forma en que los números se agregan a los vectores tenemos $a,|b-a|$ o $b, |a-b|$ aparecen como números consecutivos en $v_{n-1}$. WLOG que sea la primera opción. Pero, a continuación,$\gcd(a,b) = \gcd(a,|b-a|) =1$. Por lo tanto la prueba.

Ahora vamos a notar que un número $n$ pueden aparecer en el vector si $a,b$ aparecen como enteros consecutivos en un vector y $a+b = n$. Pero desde arriba tenemos que ni de $a,b$ puede compartir un factor común de $n$. Ahora el uso de la inducción en $n$ vamos a probar que tal una combinación de números enteros consecutivos $(a,b)$ sólo puede aparecer en un único vector. El caso base para $n=1,2,3$ es cierto. Supongamos ahora que tenemos enteros consecutivos, $a,b$ que aparece en diferentes vectores, es decir,$v_i$$v_j$, de forma que ambos suma a $n$. WLOG deje $a<b$. A continuación, voy a regresar en $v_{i-1}$ $v_{j-1}$ tenemos los números enteros consecutivos $a, b-a$ en ambos vectores. Pero esto contradice la hipótesis inductiva como los dos pares suma a $b<n$.

A partir de aquí podemos concluir que un entero $n$ será en la mayoría de las $\phi(n)$ en el final del vector. Ahora queda por mostrar que cada una combinación de $a,b$ s.t. $\gcd(a,b) = 1$ aparece como números enteros consecutivos en algún momento.

[ACTUALIZACIÓN]

Similares a las anteriores, vamos a probar la última reclamación por inducción en $n$. La base de casos $n=1,2,3$ son trivialmente verdadera. Supongamos ahora que el reclamo es válido para todos los números menos de $n$. Ahora vamos a $a,b$ ser cualquier enteros tales que $a+b=n$ $\gcd(a,b)=1$ y WLOG $a<b$. Sabemos que van a aparecer en $v_i$ si y sólo si $a,b-a$ aparecen como números enteros consecutivos en $v_i$. Pero por la hipótesis inductiva tenemos que $a,b-a$ no aparecen como números enteros consecutivos en un único vector. Por eso $a,b$ parecen demasiado y en un único vector. Por lo tanto la prueba.

RESUMEN: podemos contar los pares de enteros consecutivos por su izquierda miembro y resumen de encima tenemos que si $a<n$$\gcd(a,n) = 1$, luego, finalmente, los enteros $a,n-a$ aparecerá sólo una vez en los vectores. Tenga en cuenta que el caso de $n-a,a$ es contada por el uso de $n-a$. Por lo tanto, cada uno de los enteros aparece $\phi(n)$ veces en el final del vector.