Altro giochino con la $\phi$

[<enigma>]

Trovare tutti gli $n \in \mathbb N$ tali che l'equazione $\phi^k(x)=n$ ha soluzione per ogni $k \in \mathbb N$.
NB: $\phi ^k= \underbrace{\phi \circ \phi \circ \dots \circ \phi}_{\text{$k$ volte}}$.

[Leonida]

Noto che $n = 2^m$ funziona per ogni $m \in \mathbb{N}$. Infatti dato che $\varphi \left(2^a \right) = 2^{a-1}$, scelgo $x = 2^{m +k}$ e ottengo:
\[
\varphi^k \left(2^{m +k} \right) = 2^m
\]
Fatto: se $n$ non è una potenza di $2$, allora $v_2 \left(\varphi \left(n\right) \right) \geq v_2 \left(n \right)$.
Dim.: sia $n = 2^a \cdot \displaystyle \prod_{i=1}^{m} \displaystyle p_i ^{\alpha_{i}}$, dove i $p_i$ sono primi dispari e $m \geq 1$ perchè $n$ non è potenza di $2$. Vale:
\[
v_2 \left(\varphi \left(n \right) \right) = v_2 \left( 2^{a-1} \cdot \prod_{i=1}^{m} \displaystyle p_i ^{\alpha_{i} -1} \left(p_i - 1 \right) \right) = a -1 + \sum_{i=1}^{m} v_2 \left(p_i - 1 \right)
\]
Dato che ogni addendo nella sommatoria vale almeno $1$ si ha:
\[
v_2 \left(\varphi \left(n \right) \right) \geq a -1 + m \geq a = v_2 \left(n \right)
\]
e l'ultima disuguaglianza è vera per $m \geq 1$. Segue il Fatto.
Dimostro che se $n \neq 2^m$, esistono $k$ arbitrariamente grandi per cui l'equazione del testo non ammette soluzione.
Per assurdo, a ogni $k$ corrispondono delle soluzioni $x = x_k$. Vale sempre:
\[
x_k > \varphi \left(x_k \right) > \varphi^2 \left(x_k \right) > \ ... \ > \varphi^k \left(x_k \right)
\]
Se per un certo $k$ si ha che $\varphi^k \left(x_k \right)$ è una potenza di 2, ho trovato l'assurdo. Altrimenti, posso applicare il Fatto:
\[
v_2 \left(x_k \right) \leq v_2 \left(\varphi \left(x_k \right) \right) \leq \ ... \ \leq v_2 \left(\varphi^k \left(x_k \right) \right)
\]
Definisco $d_x = \displaystyle \frac{x}{2^{v_2 \left(x \right)}}$. Allora combinando le 2 disuguaglianze precedenti, ottengo:
\[
\displaystyle \displaystyle d_{x_k} > d_{\varphi \left(x_k \right)} > \ ... \ > d_{\varphi^k \left(x_k \right)}
\]
Quest'ultima è una sequenza di interi strettamente decrescente: dunque per $k$ sufficientemente grande, $\displaystyle d_{\varphi^k \left(x_k \right)} = 1$. Cio implica che $\varphi^k \left(x_k \right)$ è una potenza di 2, di conseguenza $n$ è una potenza di 2, ma questo è assurdo perchè sto esaminando $n \neq 2^m$.

[<enigma>]

• $n=6$ ha $x_k= 6 \cdot 3^k$.
• Però è vero che gli $n$ potenze di $2$ sono soluzioni.
• Hai sbagliato alla fine quando costruisci la sequenza dei $d$: non è vero che $d_{\phi^k(x_k)}=1$ definitivamente-è vero che hai una catena decrescente di $k$ interi, ma puoi solo usare $k$ fissato perché al crescere di $k$ può crescere anche $d_{x_k}$.