@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]?

@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.

Désolé , mauvaise lecture

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

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

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

@scarta

Ok pour la condition

@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

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

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

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

#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);
}

@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é).

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

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".

#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;
    }
}

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

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]);
        }
    }
}