Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 18-08-2021 20:12:21

Sydre
Professionnel de Prise2Tete
Enigmes résolues : 15
Messages : 245

Rayons cosmiiques

Un entier naturel aléatoire multiple de [latex]3[/latex] est stocké sous forme binaire sur un disque dur.

Manque de chance, des rayons cosmiques entrent en collision avec celui-ci. Cela a pour effet d'inverser [latex]2[/latex] de ses bits au hasard.

Quelle est la probabilité pour que le nombre ainsi altéré soit toujours un multiple de [latex]3[/latex]?

Attention: le "inverser" de l'énoncé ne veut pas dire que l'on "échange" [latex]2[/latex] bits de place. Inverser un bit en informatique c'est passer sa valeur de [latex]0[/latex] à [latex]1[/latex] ou réciproquement.

  • |
  • Répondre

#0 Pub

 #2 - 19-08-2021 09:11:39

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,426E+3

Rayons coosmiques

Bonjour

Les puissances de 2 sont alternativement congrues à 1 ou 2 modulo 3 donc on ne change pas la congruence en échangeant deux bits dont les rangs ont la même parité . On ne change pas non plus la congruence modulo 3 si on échange deux chiffres identiques sur des rangs de parité différentes . On a donc en tout trois chances sur quatre de garder un multiple de 3 .

Vasimolo

 #3 - 19-08-2021 11:38:00

Sydre
Professionnel de Prise2Tete
Enigmes résolues : 15
Messages : 245

rayonq cosmiques

@Vasimolo

Salut

Tu commences bien mais il me semble que tu as mal classifié certains cas.

on ne change pas la congruence en échangeant deux bits dont les rangs ont la même parité

Quid de:

> + puissance paire + puissance paire
> + puissance impaire + puissance impaire
> - puissance paire - puissance paire
> - puissance impaire - puissance impaire

On ne change pas non plus la congruence modulo 3 si on échange deux chiffres identiques sur des rangs de parité différentes

Ok.

Mais surtout, est on certain que tous ces cas soient équiprobables pour un entier naturel multiple de [latex]3[/latex]?

 #4 - 19-08-2021 12:10:58

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,426E+3

Rayons comsiques

Je me suis sans doute mal exprimé smile

La congruence modulo 3 de l'entier est la somme des congruences de chacun des bits multiplié par la congruence de son rang ( c'est pas clair mais je ne suis mal à l'aise avec l'informatique ) . Si on échange deux rangs de même parité , on ne change rien à la congruence modulo 3 ( on se fiche complètement des valeurs des bits ) .

Que l'entier initial soit multiple de 3 ou non est sans intérêt , on conserve le modulo 3 .

Vasimolo

 #5 - 19-08-2021 13:04:25

Sydre
Professionnel de Prise2Tete
Enigmes résolues : 15
Messages : 245

ratons cosmiques

@Vasimolo

La congruence modulo 3 de l'entier est la somme des congruences de chacun des bits multiplié par la congruence de son rang

On est d'accord.

Si on échange deux rangs de même parité , on ne change rien à la congruence modulo 3 ( on se fiche complètement des valeurs des bits )

Je crois avoir compris d'où vient la confusion.

Attention: le "inverser" de l'énoncé ne veut pas dire que l'on "échange" [latex]2[/latex] bits de place. Inverser un bit en informatique c'est passer sa valeur de [latex]0[/latex] à [latex]1[/latex] ou réciproquement.

 #6 - 19-08-2021 17:17:25

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3221
Lieu: Luxembourg

Rayons cosmqiues

Salut,
Au début, j’avais aussi compris que les deux bits étaient intervertis (et pas inversés).
En binaire, le nombre s’écrit comme la somme de: ak.(2^k), avec: ak valant 0 ou 1.
En inversant les valeurs de rangs i et j (avec i>j): ai et aj deviennent 1-ai et 1-aj.
Je calcule la différence entre l'ancien et le nouveau nombre:
D = (2.ai–1).(2^i) + (2.aj–1).(2^j) = (2^j).[(2.ai–1).(2^(i-j)) + (2.aj–1)]
Pour que le nombre reste divisible par 3, il faut et il suffit que cette différence le soit aussi, ce que je je peux ramener à deux cas seulement:
1) si: ai=aj, alors: D = (+/-).(2^j).[(2^(i-j))+1]
2) si: ai<>aj, alors: D = (+/-).(2^j).[(2^(i-j))-1]
On sait que (2^j) n’est pas divisible par 3 et que: 2^(i-j)–1; 2^(i-j) et 2^(i-j)+1 sont trois nombres consécutifs dont celui du milieu est pair.
Donc les nombres: 2^(i-j)–1 et 2^(i-j)+1 sont "alternativement" divisibles par 3 (une fois l'un et une fois l'autre).
En final, la probabilité demandée est de: 1/2.
A+

 #7 - 19-08-2021 18:33:57

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,426E+3

Rayons cosmiues

Désolé , mauvaise lecture sad

Dans ces conditions ( sauf nouvelle erreur ) , il faut que les deux rangs soient de même parité ou ( exclusif ) les deux bits identiques , soit une probabilité de 1/2 .

Vasimolo

 #8 - 19-08-2021 23:47:56

Sydre
Professionnel de Prise2Tete
Enigmes résolues : 15
Messages : 245

rayons cosmuques

@Franky1103 et @Vasimolo

Ok! Vous avez bien identifié les cas pour lesquels ça fonctionne ou pas smile

On aurait donc envie de dire que la probabilité est [latex]1/2[/latex]. Mais cela n'est vrai que si tous ces évenements sont équiprobables. Est-ce vraiment le cas pour un entier naturel aléatoire multiple de [latex]3[/latex]?

Très clairement si l'on prend comme nombre initial [latex]3\,(11)[/latex], [latex]6\,(110)[/latex] ou [latex]9\,(1001)[/latex] par exemple ça ne fonctionne pas.

Mais "en moyenne" sur l'ensemble des entiers naturels multiples de [latex]3[/latex]?

 #9 - 20-08-2021 12:42:37

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,426E+3

raypns cosmiques

La question serait donc de savoir si pour un multiple de 3 , il y a en moyenne autant de 0 en rang pair que de 0 en rang impair que de 1 en rang pair et que de 1 en rang impair . Cela me semble complètement évident sauf si on limite le nombre de bits , il faut le démontrer ?

Vasimolo

 #10 - 20-08-2021 13:48:09

Sydre
Professionnel de Prise2Tete
Enigmes résolues : 15
Messages : 245

Rayons cosmiquues

@Vasimolo

C'est la question qu'il faut se poser pour pouvoir conclure, oui.

La réponse semble intuitive mais pas sur que ça soit si évident que ça à démontrer wink

Effectivement on pourrait aussi se poser la question pour un sous-ensemble des multiples de [latex]3[/latex] en restreignant le nombre de bits. Après tout en pratique la taille du nombre est limitée par la capacité du disque dur!

 #11 - 20-08-2021 14:56:09

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1965

Rayoons cosmiques

Allez je me lance : on commence par regarder 2^n modulo 3 : on trouve alternativement 1 et -1
==> Soit N un nombre dont l'écriture binaire est ...n2n1n0, N est multiple de 3 si et seulement si n0-n1+n2-n3+etc... est multiple de 3 aussi

On arrive donc au résultat suivant :
> Si les deux bits ont des indices de parité différente
> > Si dans ce cas les deux bits étaient identiques, le bitflip ne change pas le modulo
> > Sinon, on a une différence de +/-2 modulo 3 avec le nombre de départ, qui était un multiple de 3 ==> ça ne sera plus le cas après bitflip
> Si les deux bits ont des indices de même parité
> > Si les deux bits étaient identiques, le bitflip fait une différence de +/-2 ==> pas multiple de 3
> > Sinon, on a le même résultat dans notre somme, et donc c'est un multiple de 3

Pour parler "binaire", on arrive à la conclusion suivante :
- Si "ni" == "nj" ^ (i%2 == j%2)     -- lire XOR
- Alors le nouveau nombre est multiple de 3
(il faut qu'une et une seule des deux conditions "bits égaux" et "parité égale" soit vraie)

Après, y'a plus qu'à... mais techniquement, puisque le nombre est stocké sur une machine, alors il est forcément probablement de taille fixe => il faut aussi compter avec les bitflips des "leading zeros" : le nombre 3 par exemple peut tout à fait être bitflipé en un multiple de 3, puisqu'il s'écrit, sur 32 bits par exemple : 00000000000000000000000000000011, et qu'on peut en faire un 11000000000000000000000000000011 par exemple...

Bon allez je vais coder un bidule on verra bien

 #12 - 20-08-2021 15:26:31

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1965

raypns cosmiques

Voilà, c'est fait. Sur tous les entiers 32 bits :

Code:

Total: 355050630208 of 710101259440
65.45s user 0.31s system 99% cpu 1:06.38 total

Une bonne minute pour sortir le nombre de bitflips valides sur tous les bitflips possibles, uniquement pour les multiples de 3.
On peut arrondir ça à 50,00000006872%... ça fait plutôt équilibré je trouve big_smile

 #13 - 20-08-2021 15:27:03

Sydre
Professionnel de Prise2Tete
Enigmes résolues : 15
Messages : 245

rayons cosmiqies

@scarta

Ok pour la condition smile

@tout le monde

Par contre ce n'est peut être pas clair dans l'énoncé mais on considère qu'il n'y a pas de leading zeros. Les bitflips ne peuvent avoir lieu que sur les bits du nombre et pas sur le reste des bits de son contenant. La capacité du disque dur est supposée infinie.

A la base cette histoire de disque dur et de rayons cosmiques c'était surtout pour la mise en scène lol

Mais il est vrai que ça oriente sur des variantes intéressantes du problème :

- Lorsque le disque dur a une capacité finie et que celle-ci limite la taille du nombre
- Lorsque que les bitflips peuvent se produire sur l'ensemble du disque dur et pas seulement sur les bits du nombre

 #14 - 20-08-2021 15:37:48

Sydre
Professionnel de Prise2Tete
Enigmes résolues : 15
Messages : 245

rayons xosmiques

@scarta

Merci pour la confirmation empirique du [latex]1/2[/latex]!

Il reste à pousser la démonstration jusqu'au bout pour les plus courageux tongue

 #15 - 20-08-2021 16:02:14

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1965

tayons cosmiques

je pense que les formules que j'utilise dans mon code peuvent grandement faciliter cette démonstration smile - oui parce que j'ai pas testé à la main les 710101259440 combinaisons.
Par contre, c'est avec du leading zero sad

En gros, pour un nombre donné, je calcule 4 valeurs : les nombres de 0 et de 1 pour les rangs pairs et impairs (j'utilise pour ça ma fonction magique bitCount, bien plus efficace que de regarder les bits un par un, et un masque qui permet de ne considérer qu'une partie des bits). J'appelle ces valeurs IU, IZ, PU et PZ (Impair/Pair, Un/Zero)

Et ensuite, le nombre de bonnes combinaisons pour cet entier c'est IU * IZ + PU * PZ + PU * IU + PZ * IZ

Code:

#include <stdio.h>

int bitCount(unsigned long n) {
        int result = 0;
        while(n) {
                result ++;
                n = n&(n-1);
        }
        return result;
}

int main(int argc, char** argv) {

        //Borne max (32 bits)
        unsigned long limit = 1L<<32;

        //Bitflips possibles ( 32*31/2 possibilités pour chaque multiple de 3)
        unsigned long count = (limit / 3) * 32 * 31 / 2;

        //Magic number : 101010101010... en binaire - pour faire des calculs rapides
        unsigned long magicNumber = 2863311530;

        unsigned long result = 0;

        unsigned long n;
        for(n=3; n<limit; n+=3) {

                //on calcule PZ, PU, IZ, IU, le nombre de zero et de 1 pour chaque parité
                unsigned long IN = n&magicNumber;
                int IU = bitCount(IN);
                int IZ = 16 - IU;
                int PU = bitCount(n) - IU;
                int PZ = 16 - PU;


                //Combinaison valide : bits identiques sur indexs de parités différentes ou bits différents sur parité identique

                // - bits différents sur parité identique : on compte tous les 0 et tous les 1, pour une parité donnée, on a Z et U
                // Nombre de résultats valides : Z * U (on prend un "zero" et un "un" parmi la disponibilité)
                result += IU * IZ + PU * PZ;

                // - bits identiques sur parité différente : on compte PZ * IZ et PU * IU
                result += PU * IU + PZ * IZ;
        }

        printf("Total: %lu of %lu\n", result, count);
}

 #16 - 20-08-2021 17:29:10

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1965

rayons vosmiques

Deux petites remarques :

1. on peut facilement factoriser IU * IZ + PU * PZ + PU * IU + PZ * IZ en (IU + PZ) * (PU + IZ) ==> calculs encore plus rapides (-12sec)

2. j'ai fait une version sans leading zeros, on n'a plus le même résultat du tout...
MAIS ça oscille autour d'une courbe qui tend elle meme vers 1/2

Code:

Bits:2, result: 100.000000% - 1 of 1
Bits:3, result: 75.000000% - 3 of 4
Bits:4, result: 68.181818% - 15 of 22
Bits:5, result: 54.166667% - 39 of 72
Bits:6, result: 54.430380% - 129 of 237
Bits:7, result: 50.884956% - 345 of 678
Bits:8, result: 51.062699% - 961 of 1882
Bits:9, result: 50.202347% - 2481 of 4942
Bits:10, result: 50.257181% - 6351 of 12637
Bits:11, result: 50.047783% - 15711 of 31392
Bits:12, result: 50.062770% - 38283 of 76470
Bits:13, result: 50.011479% - 91491 of 182940
Bits:14, result: 50.015413% - 215797 of 431461
Bits:15, result: 50.002786% - 502461 of 1004866
Bits:16, result: 50.003800% - 1157901 of 2315626
Bits:17, result: 50.000681% - 2643309 of 5286546
Bits:18, result: 50.000940% - 5985747 of 11971269
Bits:19, result: 50.000167% - 13456755 of 26913420
Bits:20, result: 50.000233% - 30059335 of 60118390
Bits:21, result: 50.000041% - 66759375 of 133518640
Bits:22, result: 50.000058% - 147499881 of 294999421
Bits:23, result: 50.000010% - 324359553 of 648718974
Bits:24, result: 50.000014% - 710235705 of 1420471002
Bits:25, result: 50.000003% - 1549096329 of 3098192502
Bits:26, result: 50.000004% - 3366628279 of 6733256077
Bits:27, result: 50.000001% - 7292496615 of 14584993048
Bits:28, result: 50.000001% - 15748213731 of 31496426902
Bits:29, result: 50.000000% - 33912346011 of 67824691812
Bits:30, result: 50.000000% - 72835487421 of 145670974197
Bits:31, result: 50.000000% - 156050478501 of 312100956762
Bits:32, result: 50.000000% - 333575793733 of 667151586730

Edit : bugfix --> nouveaux resultats, mais ça change pas grand chose

 #17 - 21-08-2021 00:16:30

Sydre
Professionnel de Prise2Tete
Enigmes résolues : 15
Messages : 245

Rayons cosmiqques

@scarta

Ok sur le principe de ton algorithme à un détail près:

Le nombre initial est choisi au hasard donc la probabilité recherchée ne se calcule pas en faisant directement le ratio des cas favorables sur le nombre total de cas. Il faut calculer la probabilité pour chaque multiple puis faire la moyenne.

Mais à priori la variance est faible sur l'ensemble des multiple de [latex]3[/latex] et donc ça ne devrait pas changer grand chose à tes résultats.

2. j'ai fait une version sans leading zeros, on n'a plus le même résultat du tout...
MAIS ça oscille autour d'une courbe qui tend elle meme vers 1/2

Oui, la probabilité recherchée tend vers [latex]1/2[/latex] lorsque le nombre initial tend vers l'infini. Et donc sur l'ensemble des multiples de [latex]3[/latex] la probabilité moyenne (celle d'un multiple choisi au hasard) est elle aussi [latex]1/2[/latex].

Dans ton tableau de résultats tu décomposes l'ensemble des multiples en sous ensembles de multiples de même taille. On voit très clairement qu'à mesure que la taille augmente, l'amplitude de l'oscillation diminue: le phénomène à l'origine de la variance est fonction du nombre de bits (et de sa parité).

 #18 - 21-08-2021 22:00:49

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1965

Rayons cosmiuqes

J’ai un autre algo qu’il faut que j’écrive. Ça serait du o(n) en fonction du nombre de bits.
En gros la quantité q=PZ+IU suffit. J’ai l’autre partie PU+IZ en regardant son complément à N le nombre de bits. Et cette quantité permet de aussi de savoir si le nombre est un multiple de 3 (en regardant 2q-N si N est pair ou 2q-N-1 sinon).
Donc tout ce que j’ai à faire c’est de stocker le nombre d’entiers pour chaque q et dérouler.
Pour le N suivant, dynamic programming de base je peux calculer tous les nouveaux candidats pour chaque q en sommant deux des anciens : tous ceux qui font q pour N bits feront N-q et N-q+1 pour N+1 bits (suivant qu’on ajoute 1 ou 0 tout à droite)

 #19 - 23-08-2021 09:49:46

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1965

Rayons cosmiquse

Et voilà le travail - les stats pour chaque nombre de bit possible (entre 1 et 55), ça tourne en moins de 1ms

Code:

Using exactly  2 bits : 100.000000% - 1 of 1
Using exactly  3 bits : 66.666664% - 2 of 3
Using exactly  4 bits : 66.666664% - 12 of 18
Using exactly  5 bits : 48.000000% - 24 of 50
Using exactly  6 bits : 54.545456% - 90 of 165
Using exactly  7 bits : 48.979591% - 216 of 441
Using exactly  8 bits : 51.162792% - 616 of 1204
Using exactly  9 bits : 49.673203% - 1520 of 3060
Using exactly 10 bits : 50.292397% - 3870 of 7695
Using exactly 11 bits : 49.906693% - 9360 of 18755
Using exactly 12 bits : 50.073208% - 22572 of 45078
Using exactly 13 bits : 49.974640% - 53208 of 106470
Using exactly 14 bits : 50.018307% - 124306 of 248521
Using exactly 15 bits : 49.993286% - 286664 of 573405
Using exactly 16 bits : 50.004578% - 655440 of 1310760
Using exactly 17 bits : 49.998249% - 1485408 of 2970920
Using exactly 18 bits : 50.001144% - 3342438 of 6684723
Using exactly 19 bits : 49.999550% - 7471008 of 14942151
Using exactly 20 bits : 50.000286% - 16602580 of 33204970
Using exactly 21 bits : 49.999886% - 36700040 of 73400250
Using exactly 22 bits : 50.000069% - 80740506 of 161480781
Using exactly 23 bits : 49.999977% - 176859672 of 353719553
Using exactly 24 bits : 50.000023% - 385876152 of 771752028
Using exactly 25 bits : 49.999992% - 838860624 of 1677721500
Using exactly 26 bits : 50.000000% - 1817531950 of 3635063575
Using exactly 27 bits : 49.999996% - 3925868336 of 7851736971
Using exactly 28 bits : 50.000000% - 8455717116 of 16911433854
Using exactly 29 bits : 50.000000% - 18164132280 of 36328264910
Using exactly 30 bits : 50.000000% - 38923141410 of 77846282385
Using exactly 31 bits : 50.000000% - 83214991080 of 166429982565
Using exactly 32 bits : 49.999996% - 177525315232 of 355050629968
Using exactly 33 bits : 50.000000% - 377957121728 of 755914243920
Using exactly 34 bits : 50.000000% - 803158884726 of 1606317768891
Using exactly 35 bits : 49.999996% - 1703670360384 of 3407340721295
Using exactly 36 bits : 50.000000% - 3607772529060 of 7215545057490
Using exactly 37 bits : 50.000000% - 7627861917288 of 15255723835170
Using exactly 38 bits : 50.000000% - 16103264048938 of 32206528097173
Using exactly 39 bits : 50.000000% - 33947421507128 of 67894843014921
Using exactly 40 bits : 50.000000% - 71468255805960 of 142936511611140
Using exactly 41 bits : 50.000000% - 150266589128880 of 300533178258500
Using exactly 42 bits : 50.000000% - 315559837172286 of 631119674343711
Using exactly 43 bits : 50.000000% - 661905999920592 of 1323811999842003
Using exactly 44 bits : 50.000000% - 1386850666502092 of 2773701333003238
Using exactly 45 bits : 50.000000% - 2902710697328024 of 5805421394656950
Using exactly 46 bits : 50.000000% - 6069304185324210 of 12138608370647385
Using exactly 47 bits : 50.000004% - 12678102076008456 of 25356204152017901
Using exactly 48 bits : 50.000000% - 26458647810802416 of 52917295621603704
Using exactly 49 bits : 50.000000% - 55169095435287840 of 110338190870576760
Using exactly 50 bits : 50.000004% - 114935615490185350 of 229871230980369475
Using exactly 51 bits : 50.000000% - 239253730204056800 of 478507460408114775
Using exactly 52 bits : 50.000000% - 497647758824440692 of 995295517648880058
Using exactly 53 bits : 50.000000% - 1034326714419423048 of 2068653428838847370
Using exactly 54 bits : 50.000000% - 2148217022255727546 of 4296434044511453661
Using exactly 55 bits : 50.000000% - 4458563631096790104 of 8917127262193581585

Sortir plus de résultat n'est pas plus long, simplement ça demande d'utiliser autre chose que des longs...

Pour répondre à la remarque de Sydre sur les moyennes : à nombre de bit fixé, c'est identique. La probabilité pour qu'un nombre de n bits soit toujours un multiple de 3, c'est le nombre de configurations "gagnantes" sur le nombre total de configurations... qui reste constant à un nombre de bits donné...

Je pense que le code vaut qu'on y regarde un peu, pour arriver à une démonstration formelle : pour N+1 bits, je considère les N en dehors du premier
1) je définis ma quantité Q = PZ + IU
2) je compte, pour un nombre de bits donnés, le nombre de candidats pour chaque valeur de Q
3) je considère que le premier bit vaut 1, pour éviter les leading zeros
4) pour N pair et pour N impair, on a deux calculs différents qui aboutissent au même résultat : si Q = 2N+1 modulo 3, alors "1 suivi de N bits qui correspondent à la valeur Q" est un multiple de 3
5) de là, je calcule le nombre de "bonnes" combinaisons via (PZ+IU)*(PU+IZ) et je multiplie ça par le nombre de candidats à cette valeur de Q
6) les comptes pour chaque Q sont définis par récurrence, cf la fin de l'algo : soit je termine par 0 et dans ce cas je regarde pour Q-1 les résultats "inverses", soit je termine par 1 et je regarde alors pour Q les résultats "inverses".

Code:

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char** argv) {

    int bitLimit = argc > 1 ? atoi(argv[1]) : 48;
    
    unsigned long *currentCount = (unsigned long*)malloc((bitLimit+1) * sizeof(unsigned long));
    unsigned long *nextCount = (unsigned long*)malloc((bitLimit+1) * sizeof(unsigned long));
    unsigned long *tmp;

    int size, i, currentQ;
    unsigned long result, total;
    currentCount[0] = currentCount[1] = 1;

    for(size = 1; size < bitLimit; size++){    
        result = 0;
        for(currentQ = (2 * size + 1)%3; currentQ <= size; currentQ += 3)
            result += currentCount[currentQ] * (currentQ + (size&1)) * ((size|1) - currentQ);
        total = ((1UL<<size)+1)/3 * size * (size+1)/2;
        printf("Using exactly %2d bits : %f%% - %lu of %lu\n", size+1, 100.0f*result / total, result, total);

        for(i=0; i<=size+1; i++) nextCount[i] = currentCount[size + 1 - i] + currentCount[size - i];
        tmp = nextCount;
        nextCount = currentCount;
        currentCount = tmp;
    }
}

 #20 - 23-08-2021 09:58:20

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1965

Rayons ccosmiques

J'oubliais le plus important : c'est intéressant de voir que dans un sens ça converge vers 1/2 par le bas, et vers 1/2 par le haut pour l'autre sens big_smile

 #21 - 23-08-2021 21:20:59

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1965

rayons cosmisues

Bon, pour la beauté de la chose, j'ai refait un algo avec support des bigIntegers, je suis monté sans souci jusqu'à 10.000 bits en moins de 30 secondes - après ce sont les opérations de base sur les bigints qui prennent de plus en plus de temps...

Pour en revenir à la démonstration formelle : je viens de faire une découverte assez intéressante...
Comme je l'ai déjà expliqué, je pars d'une quantité Q, et je compte le nombre d'entiers qui correspondent à chaque valeur de Q, entre 0 et N le nombre de bits.
Cette quantité, je la calcule via deux valeurs précédentes situées "à l'opposé" du tableau précédent. Mais la magie de la symétrie aidant... on a en fait LE TRIANGLE DE PASCAL !!!

Par exemple, sur 9 bits, avec le premier qui vaut 1, on a C(8,3) = 56 nombres qui vérifient la quantité Q=3

Autrement dit, pour un nombre de bits N+1 donné, la moyenne sur les entiers à N+1 bits est calculée de la manière suivante
- on calcule Q0 = 2N+1 mod 3
- pour N pair, on fait la somme pour Q allant de Q0 à 2N avec un step de 3 de C(N,Q) * Q * (N+1 - Q)
- pour N impair, on fait la somme pour Q allant de Q0 à 2N avec un step de 3 de C(N,Q) * (Q+1) * (N - Q)
(en gros, la quantité Q est ajustée avec le bit de poids fort qui vaut 1, si et seulement si c'est un indice impair).
- Et on divise le tout par le nombre de combinaisons : le nombre de multiple de 3 * (N+1) * N / 2

Et le programme associé (en java) - je ne calcule bien évidemment pas les C à chaque tour hein, je calcule la ligne suivante dans le triangle de Pascal

Code:

import java.math.BigInteger;

class Multiple {

    public static void main(String[] args) {
        int bitLimit = args.length == 0 ? 48 : Integer.parseInt(args[0]);
        BigInteger[] currentCount = new BigInteger[bitLimit + 1];

        int size, i, currentQ;
        BigInteger result, total;

        currentCount[0] = currentCount[1] = BigInteger.ONE;
        for(i=2; i<=bitLimit; i++) currentCount[i] = BigInteger.ZERO;

        for (size = 1; size < bitLimit; size++) {
            result = BigInteger.ZERO;
            for (currentQ = (size * 2 + 1)%3; currentQ <= size; currentQ += 3)
                result = result.add(currentCount[currentQ].multiply(BigInteger.valueOf((currentQ + (size&1)) * ((size | 1) - currentQ))));
            total = BigInteger.ONE.shiftLeft(size).add(BigInteger.ONE).divide(BigInteger.valueOf(3)).multiply(BigInteger.valueOf(size*(size+1)/2));
            System.out.println("Using exactly " + (size+1) + " bits : " + result.doubleValue()*100 / total.doubleValue() + "% - " + result.toString()+" of " + total.toString());

            for(i=size+1; i>=1; i--) currentCount[i] = currentCount[i].add(currentCount[i-1]);
        }
    }
}
 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Tim, Tam et ?

Sujets similaires

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete