2^n e n stesse cifre?

[bĕlcōlŏn]

Dimostrare che per ogni numero naturale $k$ esiste almeno un numero $n$ di $k$ cifre tale che $2^n$ e $n$ terminano esattamente e nello stesso ordine con le stesse cifre.

[Ouroboros]

Emh... temo di non aver capito...
Dunque, prendo k=1... n é tra 0 e 9, ovviamente non é dispari perché altrimenti non può terminare come $ 2^n $...
Però $ 2^0=1, 2^2=4, 2^4=16, 2^6=64, 2^8=256 $... nessun $ 2^n $ termina come n...
Oppure ho capito male?

[bĕlcōlŏn]

Pardon, $k \geq 2$.

[Drago96]

Cosa vuol dire che "terminano"? Che le ultime cifre di $2^n$ sono esattamente quelle di $n$? (dato che $2^n$ ha tante più cifre di $n$)

[Ido Bovski]

Nel tentativo di dimostrare questo fatto ho provato che esiste almeno un numero $n$ di $k$ cifre tale che $2^n$ e $n$ terminano esattamente e nello stesso ordine con le stesse $k-1$ cifre
C'è un errore nel testo o devo ricontrollare le mie disuguaglianze?

[bĕlcōlŏn]

Ido, posta la tua soluzione e vediamo. Io ci riesco anche con k (penso)

[Ido Bovski]

Ido, posta la tua soluzione e vediamo.

Dimostro che esiste un $n$ di $k+1$ cifre tale che $10^k\mid 2^n-n$, con $k\ge1$.
Sia $n_1=2^k(1+\varphi(5)h_1)$ e $n_i=n_{i-1}+2^k\varphi(5^i)h_i$, con $i=2, \ldots, k$. Chiaramente $2^k\mid 2^{n_i}-n_i$ per ogni $i$. Proviamo per induzione su $i$ che esiste $h_i$ tale che $5^i\mid 2^{n_i}-n_i$.
Passo base: banalmente verificato. Passo induttivo: $2^{n_i}-n_i\equiv (2^{n_{i-1}}-n_{i-1})-2^k\varphi(5^i)h_i\equiv 5^{i-1}\alpha-2^{k+2}\cdot 5^{i-1}h_i\equiv 0 \pmod {5^i}$, da cui $h_i\equiv 2^{-k-2}\alpha \pmod 5$.
Prendendo $n=n_k$, abbiamo che $10^k\mid 2^n-n$. Osserviamo ora che $n=2^k\left(1+\sum_{i=1}^k \varphi(5^i)h_i\right)$ e che $h_i\in\{1, 2, 3, 4\}$. Allora $n\ge 10^k$ e $n\le 2^k(4\cdot5^k-3)<10^{k+1}$, ovvero $n$ ha $k+1$ cifre.