Ah le potenze di 2....

[andreamasi1]

Salve a tutti
inizio da qui con questo bell'enigma che trovo bellissimo sia nella formulazione sia, soprattutto, nella dimostrazione (potevo anche postarlo in teoria dei numeri , magari lo metto anche li come esercizio.....)..
Esiste una potenza di 2 tale che le sue cifre, riarrangiate, costituiscano un'altra potenza di 2 ? Ovviamente non valgono gli 0 come leading digits...
buon divertimento
AM

[megas_archon]

Cosa significa "riarrangiate"?

[andreamasi1]

hai ragione : si intende che devono essere le stesse cifre della potenza di 2 originale.
es. da 4096 risultano 9064, 4069, ecc...

[megas_archon]

Si può formalizzare meglio il problema: si tratta di determinare se esiste un intero $n \ge 1$ con la proprietà che detta \((d_k,\dots, d_1, d_0)\) l'espansione decimale di \(2^n\), esista una permutazione \(\sigma : [k+1] \to [k+1]\) tale che \((d_{\sigma k}, \dots, d_{\sigma 1}, d_{\sigma 0})\) sia l'espansione decimale di un'altra potenza di 2, diciamo \(2^r\).

Beh, una maniera brutale di risolvere il problema è: fissa \(n\); prendi le cifre di \(2^n\); permutale in tutti i modi possibili; converti in base 2 ciascuna permutazione delle cifre; le permutazioni che ti interessano sono quelle che ora si scrivono come \(10\dots 0\). Ovviamente questo è computazionalmente molto stupido, devi fare \(\lfloor \log n\rfloor!\) operazioni...

[marmi1]

Ciao,

siano $a=2^m$, $b=2^n$; valga $n>m$; e sia $k=2^{n-m}$
$b-a=2^n-2^m=(2^{n-m}-1)*2^m=(k-1)*a$ deve essere divisibile per 9 (i due numeri hanno le stesse cifre),
quindi $k-1$ deve essere divisibile per 9 ($a=2^m$ non e' divisibile per 3)
$b<10*a$ (il numero di cifre e' lo stesso senza 0 "leading digit"), quindi $b-a<9*a$.
$k-1$ non puo' essere divisibile per 9 e contemporaneamente $<9$ (e $>1$).

Ciao,
Marmi

[andreamasi1]

grazie marmi!
propongo la demo che mi ha fatto innamorare di questo problema per la sua semplicità e bellezza. Mi scuso , devo ancora studiare la sintassi del sito per le formule.
Supponiamo che esistano 2 potenze di 2 tali che la seconda sia un puro riarrangiamento delle cifre della prima. [ ricordiamo che un numero è equivalente, modulo 9 alla somma delle sue cifre] . Questo significa che esse devono avere lo stesso numero di cifre, and che la somma delle cifre modulo 9 è la stessa (es. 4096 , 9064, 4069 ecc.). Ma la somma delle cifre modulo 9 delle potenze di 2 si ripete ciclicamente con periodo 6: 2^(n+6)=(2^n)(2^6)= (2^n)*64 = 2^n (mod9) perchè 64 =1 (mod 9). Cosicchè le 2 potenze di 2 distano almeno 6 step l'uno dall'altra: ma allora non possono avere lo stesso numero di cifre (l'una sarà 64 volte maggiore dell'altra) il che contraddice il nostro punto di partenza. Pertanto non esistono 2 potenze di 2 tali che le cifre dell'una siano un semplice riarrangiamento delle cifre dell'altra.
Ah quasi dimenticavo, purtroppo la dim non è mia, nè del mio amico. E' di Terence Tao.

al prossimo enigma