Alternanza Binaria & k-bit attivi
Salve,
vorrei sapere se è possibile ricavare una proprietà generale da questo "problema".
Avendo un numero intero che rappresenta la lunghezza di un numero binario (abbiamo il numero di bit), applicando questa proprietà avremo il numero decimale corrispondente al numero rappresentato dal numero binario.
La proprietà sui binari, è mettere $1$ alternamente i bit, a somme di 2 bit:
$(01)_2 = (1)_10$
$(0101)_2 = (5)_10$
$(010101)_2 = (21)_10$
$(01010101)_2 = (85)_10$
avendo il numero $8$ applicando la funzione $f()$, perciò $f(8)=85$.
Se il problema è abbastanza chiaro, notate qualche proprietà?
Ringrazio
vorrei sapere se è possibile ricavare una proprietà generale da questo "problema".
Avendo un numero intero che rappresenta la lunghezza di un numero binario (abbiamo il numero di bit), applicando questa proprietà avremo il numero decimale corrispondente al numero rappresentato dal numero binario.
La proprietà sui binari, è mettere $1$ alternamente i bit, a somme di 2 bit:
$(01)_2 = (1)_10$
$(0101)_2 = (5)_10$
$(010101)_2 = (21)_10$
$(01010101)_2 = (85)_10$
avendo il numero $8$ applicando la funzione $f()$, perciò $f(8)=85$.
Se il problema è abbastanza chiaro, notate qualche proprietà?
Ringrazio
Risposte
Per ottenere il secondo partendo dal primo sommo $4$, dal secondo al terzo sommo $16$ dal terzo al quarto sommo $64$.
Alias: $4^1$, $4^2$, $4^3$ e così via..
Quindi direi:
$f(x) = (4^(x/2)-1)/3$
Però così puoi mettere solo numeri pari, quindi secondo me converebbe mettere:
[tex]g(x) = \frac{4^x-1}{3}[/tex]
E naturalmente $g(4)=f(8)$.
Alias: $4^1$, $4^2$, $4^3$ e così via..
Quindi direi:
$f(x) = (4^(x/2)-1)/3$
Però così puoi mettere solo numeri pari, quindi secondo me converebbe mettere:
[tex]g(x) = \frac{4^x-1}{3}[/tex]
E naturalmente $g(4)=f(8)$.
perfetto.
Ti ringrazio molto, mi eviti molti conti
Ti ringrazio molto, mi eviti molti conti
Insomma, serie geometrica...
Infatti un numero scritto in binario è:
[tex]$(c_N\ c_{N-1}\dots c_1\ c_0)_2=\sum_{n=0}^N c_n2^n$[/tex]
con [tex]$c_n=0,1$[/tex] per [tex]$n=0,1,\ldots ,N-1, N$[/tex]; ora, per i tuoi numeri hai [tex]$N$[/tex] pari (quindi [tex]$N=2H$[/tex] per un opportuno [tex]$H$[/tex]) ed inoltre:
[tex]$c_n=\begin{cases} 1 &\text{, se $n$ è pari} \\ 0 &\text{, se $n$ è dispari}\end{cases}$[/tex],
sicché il tuo generico numero si scrive:
[tex]$(c_{2H}\ 0\ c_{2(H-1)} 0\dots c_2\ 0\ c_0)_2=\sum_{h=0}^H 2^{2h} $[/tex]
[tex]$=\sum_{h=0}^H 4^{h}$[/tex]
[tex]$=\frac{4^{H+1}-1}{4-1}$[/tex] (formula della somma parziale della serie geometrica di ragione [tex]$4$[/tex])
[tex]$=\frac{4^{H+1}-1}{3}$[/tex],
come già determinato da altri.
Infatti un numero scritto in binario è:
[tex]$(c_N\ c_{N-1}\dots c_1\ c_0)_2=\sum_{n=0}^N c_n2^n$[/tex]
con [tex]$c_n=0,1$[/tex] per [tex]$n=0,1,\ldots ,N-1, N$[/tex]; ora, per i tuoi numeri hai [tex]$N$[/tex] pari (quindi [tex]$N=2H$[/tex] per un opportuno [tex]$H$[/tex]) ed inoltre:
[tex]$c_n=\begin{cases} 1 &\text{, se $n$ è pari} \\ 0 &\text{, se $n$ è dispari}\end{cases}$[/tex],
sicché il tuo generico numero si scrive:
[tex]$(c_{2H}\ 0\ c_{2(H-1)} 0\dots c_2\ 0\ c_0)_2=\sum_{h=0}^H 2^{2h} $[/tex]
[tex]$=\sum_{h=0}^H 4^{h}$[/tex]
[tex]$=\frac{4^{H+1}-1}{4-1}$[/tex] (formula della somma parziale della serie geometrica di ragione [tex]$4$[/tex])
[tex]$=\frac{4^{H+1}-1}{3}$[/tex],
come già determinato da altri.
grazie gugo82, non avevo mai fatto caso che un numero binario alla fine è una serie, davvero molto affascinante. Mi tornerà sicuramente utile
Ne approfitto del post per chiedere un altro aiuto su un problema simile, sempre nel cercare una proprietà generale sui numeri binari.
Il problema consiste nel trovare una formula che con operazioni primitive, mi restituisca i sottoinsiemi di $k$ elementi composti da ${1}$ o se si vuole, si può vedere come una permutazione.
Se ho un numero binario con $n$ elementi di di ${0}$, e $n-1$ elementi di ${1}$. Vorrei trovare un modo per elencare tutti i numeri con $k=n-1$ bit attivi.
es: $k=3$
$[0000111] = 7$
$[0001011] = 11$
$[0001101] = 13$
$[0001110] = 14$
$[0010011] = 19$
$[0010101] = 21$
$[0010110] = 22$
$[0011001] = 25$
$[0011010] = 26$
$[0011100] = 28$
$....$
ci sarebbe una restrizione sul problema cioè, trovare solo quelli con il primo bit attivo, cioè un sottoinsieme del problema sopra
che sarebbe: ${7,11,13,19,21,25,...}$
ma questo si può risolvere filtrando i dati e non è troppo costoso, l'importante sarebbe trovare un modo per calcolare quell'insieme di numeri (con $k$ bit attivi).
ho notato che alcuni numeri (decimali) sono multipli di $7$ e $11$, poi si va somme di $6$ da $13$, ma si ha un'eccezione con $26$ che non cade con le condizioni elencate.
Notate qualche proprietà "unica" che permeta di calcolare questi decimali?
Ringrazio
EDIT:
qualche dato in più, i primi cinque $k$ con decimali $[1,55]$ su $6$ bit di rappresentazione binaria (lo spazio di un bloc-notes)
$1={1,2,4,8,16,32}$
$2={3,5,6,9,10,12,17,18,20,24,33,34,36,40,48}$
$3={7,11,13,14,19,21,22,25,26,28,35,37,38,41,42,44,49,50,52}$
$4={15,23,27,29,30,39,43,45,46,51,53,54}$
$5={31,47,55}$
Ne approfitto del post per chiedere un altro aiuto su un problema simile, sempre nel cercare una proprietà generale sui numeri binari.
Il problema consiste nel trovare una formula che con operazioni primitive, mi restituisca i sottoinsiemi di $k$ elementi composti da ${1}$ o se si vuole, si può vedere come una permutazione.
Se ho un numero binario con $n$ elementi di di ${0}$, e $n-1$ elementi di ${1}$. Vorrei trovare un modo per elencare tutti i numeri con $k=n-1$ bit attivi.
es: $k=3$
$[0000111] = 7$
$[0001011] = 11$
$[0001101] = 13$
$[0001110] = 14$
$[0010011] = 19$
$[0010101] = 21$
$[0010110] = 22$
$[0011001] = 25$
$[0011010] = 26$
$[0011100] = 28$
$....$
ci sarebbe una restrizione sul problema cioè, trovare solo quelli con il primo bit attivo, cioè un sottoinsieme del problema sopra
che sarebbe: ${7,11,13,19,21,25,...}$
ma questo si può risolvere filtrando i dati e non è troppo costoso, l'importante sarebbe trovare un modo per calcolare quell'insieme di numeri (con $k$ bit attivi).
ho notato che alcuni numeri (decimali) sono multipli di $7$ e $11$, poi si va somme di $6$ da $13$, ma si ha un'eccezione con $26$ che non cade con le condizioni elencate.
Notate qualche proprietà "unica" che permeta di calcolare questi decimali?
Ringrazio
EDIT:
qualche dato in più, i primi cinque $k$ con decimali $[1,55]$ su $6$ bit di rappresentazione binaria (lo spazio di un bloc-notes)
$1={1,2,4,8,16,32}$
$2={3,5,6,9,10,12,17,18,20,24,33,34,36,40,48}$
$3={7,11,13,14,19,21,22,25,26,28,35,37,38,41,42,44,49,50,52}$
$4={15,23,27,29,30,39,43,45,46,51,53,54}$
$5={31,47,55}$
L'utente "apatriarca" qui mi ha trovato un possibile algoritmo, per risolvere questo problema.
Perciò sono a posto, grazie
Perciò sono a posto, grazie
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo