27879

@ Scarta: parfait !

@ Milou : j'ai cherché où est ton erreur. Je crois que tu as dû cumuler à tort. Par exemple les possibilités avec 4 zéros englobent celles avec 2 zéros, il ne faut pas les additionner. Mais l'idée est bien là.

Bon, de retour avec une feuille excel !
calcul de X 0 parmi Y chiffres.
Un rapide calcul me dit que Y = 11
La somme de X entre C(X;Y) de 1 à 11 fait 2047 auquel j'ajoute un pour le nombre sans 0 !
Donc le résultat est proche de 1 1111 1111 1000 0000 0000 (2048 ième ?)
1 1111 1111 0000 1000 0000 est le 1981 ? (oui, je commence à douter de mon analyse)
Bon, je fini ma journée de boulot, je reprends ce soir

@ Francky : un tableur est une aide au calcul, ce n'est pas de la programmation.
C'est le bon résultat, bravo !

@ Orsa : c'est bon !

@ Godisdead : j'ajoute un peu de temps.

le premier 1111111111
10 nombres avec un 0
2 parmi 11 avec deux 0. En effet, si on en prend 2 nombre dans 1-11, le premier nombre donne la position dans le nombre binaire (il ne peut dépasser 10). Le second - 1 donne la position du deuxième.

De manière générale, le nombre de façons de placer k billes dans n boites est [latex]n + k -1 \choose k[/latex]
Le nombre de façons de placer k billes ou moins dans n boites est [latex]n + k \choose k[/latex]

On en déduit la formule suivante :

Soit n un nombre binaire à 10 1.
Soit m son nombre de 0.
Soit ak la position du k-ième 0 en partant de la fin. (par exemple a1 vaut 1 si le dernier 0 est situé entre le 9ième et le 10ième 1, a5 vaut 10 si le 5ième 0 en partant de la fin est situé avant le premier 1.
Le nombre de nombres binaires à 10 1 strictement inférieurs à n est :
[TeX]{10+m-1\choose m-1} + \sum_{k>0} {a_{k+1}+k-1\choose k}-{a_{k} + k - 1\choose k}[/TeX]
On peut cherche les coefficients de manière gloutonne, car ils agissent de la même manière que les coefficients en écriture décimale par exemple.

On veut donc chercher le nombre qui a 2020nombres binaires à 10 1 inférieur ou égal à lui, donc on veut décomposer 2020.
Soit [latex]n[/latex] le nombre de zéros pour le 2020-ème chiffre.
On a donc [latex]a_{n+1} = 10[/latex]
calculons [latex]10+m \choose m-1[/latex] pour [latex]m[/latex] incrémenté.
1 1
2 11
3 66
4 286
5 1001
6 3003

Donc on aura 5 zéros.

a_{6} vaut 10
Calculons [latex]{10+m \choose m-1} +  {a_{6}+5-1\choose 5}-{a_{5} + 5-1\choose 5}[/latex] en incrémentant [latex]a_5[/latex]
0 10001 + 2002- 0 = 3003
1 3003 - 1 = 3002
2 2982 - 6 = 2997
3 2982
4 2947
5 2877
6 2751
7 2541
8 1716

Donc le 1er 0 est situé entre le 2ème et le 3ème 1.

Calculons [latex]{10+m \choose m-1} +  {a_{6}+5-1\choose 5}-{a_{5} + 5-1\choose 5} +  {a_{5}+4-1\choose 4}-{a_{4} + 4-1\choose 4}[/latex] en incrémentant [latex]a_4[/latex]
[TeX]{a_{5}+4-1\choose 4}=330[/TeX]
0 1716 + 330 - 0 = 2046
1 2046 - 1 = 2045
2 2046 - 5 = 2041
3 2046 - 15 = 2031
4 2011

Donc le 2ième 0 est situé entre le 6ième et le 7ième 1.

Calculons [latex]{10+m \choose m-1} +  {a_{6}+5-1\choose 5}-{a_{5} + 5-1\choose 5} +  {a_{5}+4-1\choose 4}-{a_{4} + 4-1\choose 4} +  {a_{4}+3-1\choose 3}-{a_{3} + 3-1\choose 3}[/latex] en incrémentant [latex]a_3[/latex]
[TeX]{a_{4}+3-1\choose 3}=20[/TeX]
0 2011 + 20 = 2031
1 2031 - 1 = 2030
2 2031 - 4 = 2027
3 2021
4 2011

Donc le 3ième 0 est situé entre le 6ième et le 7ième 1.

Calculons [latex]{10+m \choose m-1} +  {a_{6}+5-1\choose 5}-{a_{5} + 5-1\choose 5} +  {a_{5}+4-1\choose 4}-{a_{4} + 4-1\choose 4} +  {a_{4}+3-1\choose 3}-{a_{3} + 3-1\choose 3}+  {a_{3}+2-1\choose 2}-{a_{2} + 2-1\choose 2}[/latex] en incrémentant [latex]a_2[/latex]
[TeX]{a_{3}+2-1\choose 2}=10[/TeX]
0 2011 + 10 = 2021
1 2021 - 1 = 2020

Donc le 4 ième 0 est situé entre le 9ième et le 10 ème 1, et le dernier 0 est situé derrière le dernier 1. On obtient donc :

110111100111010

Bon, j'ai surement fait une erreur de calcul (comme d'hab...), mais sait-on jamais...