Relation entre L'entier et son écriture binaire

Salut tt le monde:

J'essaie de trouver une relation entre tout nombre entier naturel N et le nombre de chiffre constituant son écriture binaire.

EXPLE
Si N=4, alors dans la base (2), on écrit 4 = 100 => le nombre de chiffres est 3
Si N=17, en binaire 17=10001 => le nombre de chiffres est 5.

En général, si N=277971, le nombre de chiffres binaires est combien?
...
...
Pour N donné, le NCB de N est combien?

INDICATION

En binaire, un nombre entier N dans la base 10 est une suite de chiffres {0, 1}. On remarque que le chiffre binaire situé à l'extrême gauche désigne 2^(L-1) où L désigne le nombre de chiffres de l'écriture binaire de N (base 10).

Donc il suffit de déterminer ce L en se basant sur la définition de l'écriture binaire d'un nombre.

medba a écrit:NCB(N)= N DIV 2 + 1

medba, je crois que t'as oublié un exposant ou klk choz pareille.

NCB(256) = 8, car 256 = 1000 0000 dans la base 2.

C'est simple :

Le nombre de chiffres binaires nécessaires est : ln(n) / ln(base)
exemple :
n = 15 ; base = 2 ==> 3.9068905 çàd 4 chiffres
15(10) = 1111(2)

n = 150 ; base 8 ==> 2.409606 çàd 3 chiffres

manianis a écrit:C'est simple :
Le nombre de chiffres binaires nécessaires est : ln(n) / ln(base)
exemple :
n = 15 ; base = 2 ==> 3.9068905 çàd 4 chiffres
15(10) = 1111(2)
n = 150 ; base 8 ==> 2.409606 çàd 3 chiffres

Tout à fait manianis !!!
Une formulation plus exacte est la suivante:

NCB(N) = 1 + E[Ln(N)/Ln(2)]
avec "E" : la fonction "partie entière".

La démonstration que j'ai faite et la suivante:

Code:

N = 2^(L-1) + Somme(ai.2^i, i de 0 à L-2)
avec
N = Entier positif
L = nombre de chiffres binaires de N
ai= 0 ou 1


Il suffit d'encadrer la somme de l'expression.
L'encadrement est le suivant:

Code:

0 <= Somme(ai.2^i, i de 0 à L-2) <= Somme(2^i, i de 0 à L-2)

somme d'une suite géométrique de rapport 2.

Code:

0 <= Somme(ai.2^i, i de 0 à L-2) <= (1 - 2^(L-1))/(1 - 2) = 2^(L-1) - 1

l'idée est d'écrire 2^(L-1) - 1 < 2^(L-1).
d'où

Code:

0 <= Somme(ai.2^i, i de 0 à L-2) < 2^(L-1)

on ajoute 2^(L-1) pour avoir l'expression initiale de N

Code:

2^(L-1) <= N < 2^(L-1) + 2^(L-1)
2^(L-1) <= N < 2^L
d'où
(L-1) x Ln(2)<= Ln(N) < L x Ln(2)
L-1 <= Ln(N)/Ln(2) < L

On passe à la partie entière de l'expression:

Code:

E[Ln(N)/Ln(2)] = L - 1
L = NCB(N) = 1 + E[Ln(N)/Ln(2)]

Y-a-t-il quelqu'un pour valider le calcul ???