 |
#1 - 05-09-2016 14:20:06
- caduk
- Professionnel de Prise2Tete
- Enigmes résolues : 45
- Messages : 398
décilaux vs binaire
Bonjour,
Existe il un couple [latex](i,j)\in\mathbb{N}^*[/latex] tel que le nombre de décimales de [latex]20^i[/latex] (écrit en base 10) soit égal au nombre de bits de [latex]20^j[/latex](écrit en base 2) ?
exemple: les premières puissances de 20 sont: 20 ->2 décimales 400 ->3 décimales 8000 -> 4 décimales 160000 -> 6 décimales 3200000 -> 7 décimales 64000000 ->8 décimales
20 en binaire s'écrit 10100 -> 5 bits aucune puissance de 20 ne contient 5 décimales...
Pour les plus courageux, on pourra chercher à démontrer que pour tout entier k, il existe une unique puissance de 2 qui s'écrit avec k chiffres (en décimal ou en binaire)
Bon courage 
#2 - 05-09-2016 19:38:14
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Décimaux v binaire
Bonsoir Caduk,
Il me semble qu'on ne peut pas.
Soient les nombres 20^n et 20^m ayant le même nombre k de décimales.
On écrit les encadrements: 10^(k-1) < 20 ^n < 10 ^ k 2 ^ (k-1) < 20 ^m < 2 ^ k Notons l'encadrement strict, une puissance de 20 n'est ni une puissance de 2, ni une puissance de 10.
Le produit des 2 nombres est encadré par le produit des encadrants :
20 ^(k-1) < 20 ^(n+m) < 20 ^k
Cette inégalité stricte est absurde !
#3 - 05-09-2016 19:43:20
- caduk
- Professionnel de Prise2Tete
- Enigmes résolues : 45
- Messages : 398
Déciimaux vs binaire
nodgim Très bien! 
#4 - 05-09-2016 19:57:11
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Décimaux s binaire
Ce qui est étonnant, sauf erreur, c'est que les nombres manquants dans la liste des nombres de chiffres des puissances de 20 en base 10 correspondent exactement aux nb de chiffres des puissances de 20 écrites en base 2 !
#5 - 05-09-2016 21:33:41
- caduk
- Professionnel de Prise2Tete
- Enigmes résolues : 45
- Messages : 398
Décmiaux vs binaire
nodgim C'est exact, et c'est d'ailleurs là que ça devient intéressant  J'aurais dû l'écrire plus explicitement dans l'énigme. Spoiler : [Afficher le message] On pourra chercher le nombre de puissances de 20 inférieures à [latex]10^N[/latex] et celles inférieures à [latex]2^N[/latex]et encadrer le nombre de possibilités d'écrire une puissance de 20 en binaire ou en décimal avec moins de N chiffres
#6 - 06-09-2016 19:31:24
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
décimauw vs binaire
Ce problème est surprenant. Il n'est pas si dur d'intuiter la solution (un tel couple n'existe pas), mais le rédiger clairement nécessite un certain travail. J'essaie donc.
Notons C_b(n) le nombre de chiffres en n en base b. Par exemple, si n=1024, C_10(n)=4 et C_2(n)=11.
On commence par un lemme : pour tout n>=1, C_10(5^n)+C_10(2^n) = n+1. Il se démontre aisément en considérant l'écriture scientifique de 5^n et de 2^n.
On peut ensuite observer que comme 10<20<100, la suite (C_10(20^n)) augmente de 1 ou de 2 à chaque terme : ses premiers termes sont 2;3;4 ; 6;7;8 ; 10;11;12 ; 14;15;16;17 ; 19... Pour résoudre le problème, il suffit de montrer que les termes de (C_2(20^n)), qui commence par 5;9;13;18... s'insèrent dans les "trous" laissés par (C_10(20^n)).
On considère donc un terme quelconque de cette dernière suite : soit n>=1, on pose C_2(20^n)=k. Alors C_2(5^n)=k-2n donc 2^{k-2n-1} <= 5^n < 2^{k-2n} et en multipliant par 5^{k-2n}, il vient 5.10^{k-2n-1} <= 5^{k-n} < 10^{k-2n} donc C_10(5^{k-n-1}) = C_10(5^{k-n}) = k-2n.
Enfin, C_10(20^{k-n-1}) = (k-n-1) + C_10(2^{k-n-1}) = (k-n-1) + (k-n-1)+1-C_10(5^{k-n-1}) (par le lemme) = (k-n-1) + (k-n-1)+1-(k-2n) = k-1 et de même, C_10(20^{k-n}) = k+1, cqfd : la valeur k de la deuxième suite s'est insérée entre les valeurs k-1 et k+1 de la première.
NB : on peut même réciproquement démontrer que tous les trous de la première suite sont comblés par des termes de la deuxième, i.e. que les deux suites recouvrent l'ensemble des entiers >=2.
#7 - 06-09-2016 20:24:59
- caduk
- Professionnel de Prise2Tete
- Enigmes résolues : 45
- Messages : 398
DDécimaux vs binaire
Ebichu Pas mal, un peu laborieux mais ça marche (quoique ma solution soit à peu près aussi laborieuse... ) Si on ne veut que montrer que les nombres de chiffres sont tous différents, nodgim a trouvé une solution très efficace.
Si tu souhaites t'attaquer à la généralisation, essaye de démontrer que pour tout entier k, il existe un unique [latex](ab)^N[/latex] de longueur k en base a ou en base b à la condition qu'il n'existe pas p et q tels que [latex]a^p = b^q[/latex] (a,b,p,q entiers)
#8 - 08-09-2016 08:42:00
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Décimmaux vs binaire
J'ai une autre solution arithmétique bien plus jolie et plus complète. Je la rédigerais au besoin, si elle est différente encore de ce qui aura été trouvé.
#9 - 08-09-2016 14:33:32
- caduk
- Professionnel de Prise2Tete
- Enigmes résolues : 45
- Messages : 398
Décimau xvs binaire
Voilà une proposition de résolution: Le nombre de puissances de 20 inférieures à [latex]10^N[/latex] est [latex]\lfloor log_{20}(10^N)\rfloor+1[/latex] idem pour 2^N, il y en a [latex]\lfloor log_{20}(2^N)+1\rfloor[/latex] Le nombre de possibilités d'écrire une puissance de 20 en binaire ou en décimal avec moins de N chiffres est donc [latex]n(N) = \lfloor log_{20}(10^N)\rfloor + \lfloor log_{20}(2^N)\rfloor+2[/latex] On a alors [latex]log_{20}(10^N) -1 + log_{20}(2^N) -1 +2 < n(N) < log_{20}(10^N) + log_{20}(2^N)+2 \iff N< n(N) < N+2 \iff n = N+1[/latex] (inégalités strictes car [latex]log_{20}(10^N)[/latex] est irrationnel On en déduit que le nombre de possibilités d'écrire une puissance de 20 en binaire ou en décimal avec N chiffres est n(N) - n(N-1) = 1. Donc cette écriture existe et est unique!
Une autre façon de démontrer le problème est: Le nombre de chiffres de [latex]20^n[/latex] est [latex]\lfloor log_{10}(20^n) \rfloor +1[/latex] en décimal et [latex]\lfloor log_{2}(20^n) \rfloor +1[/latex] en binaire. D'après le théorème de Beatty, ces deux suites forment une partition de N (irrationalité et somme des inverses égale à 1 OK) La démonstration de ce théorème étonnant est finalement la même que ma méthode ci dessus.
nodgim, je serai intéressé de voir ta réponse 
#10 - 08-09-2016 17:06:11
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Décimaux vs inaire
C'est également par le théorème de Beatty que je suis arrivé à une preuve plus générale. Tout en ignorant encore ce matin l'existence de ce théorème...
Je vais rédiger quelque chose là dessus, ma démarche est un peu différente de la tienne.
#11 - 08-09-2016 18:18:27
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Décimaux vs binair
Le problème plus général revient à savoir si pour un entier k donné , il existe n tel que (ab) ^ n comporte k chiffres, soit en écriture base a, soit en écriture base b.
Pour cela travaillons en logarithmes: - Les log des puissances de a, c'est à dire les multiples de a - Les log des puissances de b, c'est à dire les multiples de b - Les log des puissances de ab, c'est à dire les multiples de (a+b)
Et donc la question est de savoir si la partie entière de n(a+b) / a ou n(a+b) / b est unique, d'une part, et si pour tout entier k on trouve un unique multiple de (a+b)/a ou (a+b)/b tel que ce multiple est k < n(a+b)/a < k+1 ou (exclusif) k < m (a+b)/b < k+1, d'autre part. Remarquons que la seconde contrainte englobe de fait la 1ère.
Si on pose x = b/a et b > a, alors on a affaire aux multiples de (1+x) et (1+1/x), avec x > 1 et irrationnel.
Pour un entier k donné, on n'a pas une infinité de choix pour ces multiples : - 1+x ou - 2+2x ou ...ou -[k/2] + [k/2]x ou
- k + k/x ou -(k-1) + (k-1)/x ou ...ou -[(k+1)/2] + [(k+1)/2]/x
Or, chacun de ces choix correspond à une valeur de x dans un intervalle, et tous ces intervalles sont disjoints mais sans trous. - k + k / x si k < x - 1 + x si (k-1) < x < k - (k-1) + (k-1) / x si (k-1)/2 < x < k-1. etc....
Les différents jalons entre les intervalles, du plus grand au plus petit, sont : k/1, (k-1)/1, (k-1)/2, (k-1)/3, (k-2)/3, (k-2)/4, (k-3)/4, (k-3)/5,....1 les intervalles étant occupés alternativement par 1 multiple de (1+ x) et 1 multiple de (1+1/x).
Pour un x donné et un k donné, on a donc bien une solution unique.
CQFD
#12 - 08-09-2016 18:39:25
- caduk
- Professionnel de Prise2Tete
- Enigmes résolues : 45
- Messages : 398
décimaux vs binairr
Pas mal, c'est en effet différent, par contre j'ai l'impression que tu es passé de a et b bases à a et b logarithmes... J'avais abordé ce problème dans ma réponse à Ebichu, et il se démontre exactement de la même manière avec ma méthode. A noter que la condition que j'avais noté est équivalente à celle que le quotient des logarithmes soit irrationnel.
|
 |