neuneutrinos a écrit:

Plop à tous !

Voici encore un petit défis.

Edité par neuneutrinos il y a 11 minutes

YOUPI !!!

S'il le faut, je peux donner quelques indices.

Pour le défis N°3 , un exemple avec 18.

5,7,11,13,17 sont premiers avec 18.

5+7+11+13+17= 53
5*7*11*13*17 = 85085

53%18 = 17

85085%18 =17

Pour 18, les propriétés sont vérifiées ;) 

-
Edité par neuneutrinos 17 juillet 2017 à 9:56:09

mad scientist et cauld ont réussi le défis 1&2 avec deux manières différentes

Petite précision pour le défis n°3

les nombres premiers avec N ne sont pas nécessairement premier.

exemple pour N=5.

2,3,4 sont premiers avec 5

et les propriétés sont vérifiée pour N=5

-
Edité par neuneutrinos 17 juillet 2017 à 10:02:31

Bon, comme je suis pas très très bon en math, je vais quand même demander de l'aide pour le premier exercice, parcequ'il y a un truc que je pige pas ...
Je prends une lettre chez moi. puis j'applique l'opérateur, ça me donne un nombre en binaire. A tout hasard, on va dire

0000 0000 0000 0000 1001 1001 0011 1010

Si par contre, j’enlève le 0xff, ça me donne
0000 0001 0101 1001 1001 0010 0011 1010.
Je vais les mettre l'un en dessous de l'autre

0000 0000 0000 0000 1001 1001 0011 1010
0000 0001 0101 1001 1001 0010 0011 1010

Est-ce que quelqu'un peut m'expliquer pourquoi ça me donne ça? (Je sais ce que ça fait de faire &0xff, mais j'arrive pas à comprendre le résultat la..., a moins que ce soit une erreur?)

X&0xff ne garde que le premier octet.

On dirait que tu as fais 0xf ou 0x0f au lieu de 0xff.

Sans le code je ne peux pas dire autre chose malheureusement

Comment dire ... un moment je fais :

int main(void)
{
 int lettre;
 const int multiplicateur=57;
 while(scanf("%c",&lettre)==1)
 {
  printf("%02x",(multiplicateur * lettre)&0xff);
 }

 // (multiplicateur * lettre)&0xff) (a) = 993a =    0000 0000 0000 0000 1001 1001 0011 1010
 // (multiplicateur * lettre)       (a) = 159923a = 0000 0001 0101 1001 1001 0010 0011 1010
 printf("\n");
 return 0;
}

et apres je fais

int main(void)
{
 int lettre;
 const int multiplicateur=57;
 while(scanf("%c",&lettre)==1)
 {
  printf("%02x",(multiplicateur * lettre));
 }

 // (multiplicateur * lettre)&0xff) (a) = 993a =    0000 0000 0000 0000 1001 1001 0011 1010
 // (multiplicateur * lettre)       (a) = 159923a = 0000 0001 0101 1001 1001 0010 0011 1010
 printf("\n");
 return 0;
}

Le premier resultat devrait être 3a. Rien de plus.

essaie avec un format en décimal. Sinon ( &0xff == %256) mais je ne vois pas pourquoi tu trouve autre chose

Je me disais que je trouvais ça bizarre!
Mais peut-être que j'ai trouvé une piste. Quand je fais

printf("%0x %0x",(multiplicateur * lettre)&0xff,(multiplicateur * lettre)&0xff);

le résultat est 99 993a 3a ...
Ce que je pensais c'était qu'il prenait mon retour chariot en compte, mais je comprends pas pourquoi il est avant, et pas après ...

-
Edité par KirbXCoucou 18 juillet 2017 à 14:08:43

hmmm test en mettant multiplicateur à 1. on sera fixé sur les caractères lu

ça me donne 61a

tu ne devrais pas pouvoir dépasser 255. c'est le principe même du &0xff...

sinon fait un  %256.

ça me donne la même chose
Je vais essayé de voir en flushant ma sortie avant de print

Sinon J'ai eugchriss qui a réussi le défis 1&2

-
Edité par neuneutrinos 18 juillet 2017 à 19:02:58

Pour le moment le défis n°3 résiste encore toujours aux programmeurs.
Non il n'est pas si trivial qu'il n'y paraît...

Si personne ne trouve, je commencerai à donner quelques indices :) 

plop !

2 personnes ont validé le troisième défis !

Leur pseudo ?

fromvega et XDeath !

Je ferais une correction prochainement !

Pour les retardataires, vous pouvez toujours le faire pour vous !

Rédaction de la correction

Si vous aviez eu des points bloquants ou des questionsque je peux intégrer, faites-en part !

voici ma solution du N°1 ;

comme je suis fâché avec les maths ,j'utilise un tableau pour stocker toutes les possibilités de codage sur 1 octet (256) , puis 

je boucle pour chaque nombre hexadécimal afin de retrouver sa valeur dans le tableau ....

J'avoue avoir eu du mal avec sscanf(,,,) mais il y a un bout de temps que je n'avait pas codé en C et l'on sait que les chaînes 

de caractères sont loin d'être le point fort de cet EXCELLENT langage !

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

int main(void)
{
    int tableau[256],i,j,tmp;
    const int multiplicateur=57;
    char* tab = "992a7d62d4f1e9225b94207eaf7d9bd420f0999b200d7e20d2b77e2045b7d420447d20f0999b9b7d3e3ab4287d270b99d37d27619b2799270c617d2759207d9bd420d2617d7e20457d610c0c7d0d6220593a3a";
    int longueur = strlen(tab)/2;
    char *clair = malloc(longueur);
    for(i = 0;i<256;i++) { tableau[i] = (multiplicateur*i)&0xff; }
    for(j=0;j<longueur;j++)
    {
        sscanf(tab+j*2,"%02x",&tmp);
        for(i = 0;i<256;i++) { if(tmp == tableau[i]) break; }
        *(clair+j) = i;
    }
    printf("%s",clair);
    return 0;
}

Pour le N°2 : On change la signature de main() 

int main(int argc,char *argv[])

puis plus loin :

if(argc > 1) { multiplicateur = atoi(argv[1]); }

En ayant pris soin de ne pas déclarer 'multiplicateur' constant.

-
Edité par PhilippeBeckx 8 août 2017 à 18:38:36

Bonsoir tous.

l'addition des nombres modulo 4 est : 3

la multiplication des nombres modulo 4 est : 3

l'addition des nombres modulo 42 est : 41

la multiplication des nombres modulo 42 est : 1

l'addition des nombres modulo 424242 est : 424241

la multiplication des nombres modulo 424242 est : 52577

l'addition des nombres modulo 666666 est : 666665

la multiplication des nombres modulo 666666 est : 293063

l'addition des nombres modulo 666667 est : 666666

la multiplication des nombres modulo 666667 est : 0

l'addition des nombres modulo 4294967295 est : 4294967292

la multiplication des nombres modulo 4294967295 est : 0

Visiblement ,les propriétés sont vérifiées pour 4 et 42.

Voici mon code (pas très efficace car je stocke tous les nombres et appelle realloc() souvent.

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

void calculus(unsigned long n,unsigned long nbre,unsigned long *nombres)
{
    unsigned long totalAdd = 0;
    unsigned long totalMul = 1;
    
    for(unsigned long j=0;j<nbre;j++)
    {
        totalAdd += *(nombres + j);
        totalMul *= *(nombres + j);
    }
    printf("l'addition des nombres modulo %lu est : %lu\n",n,totalAdd%n);
    printf("la multiplication des nombres modulo %lu est : %lu\n",n,totalMul%n);
}

int main(int argc,char *argv[])
{
    unsigned long tmp,nombre,borneSup,divisible,index = 0,taille = 2,borneInf = 2;
    unsigned long *diviseur = malloc(taille*sizeof(unsigned long));
    unsigned long *candidats = malloc(taille*sizeof(unsigned long));
    
    if(argc < 2 || atol(argv[1]) < 4)
    {
        printf("Usage : %s <nombre> --> nombre > 3\n",argv[0]);
        exit(-1);
    }
    nombre = borneSup = atol(argv[1]);
    while(borneInf<borneSup)
    {
        if(!(borneSup%borneInf))
        {
            borneSup = borneSup/borneInf;
            *(diviseur + index++) = borneInf;//stockage diviseur
            // éviter les doublons
            if(borneSup>borneInf) *(diviseur + index++) = borneSup;//stockage quotient
            if(index == taille)
            {
                taille *= 2;
                if((diviseur = realloc(diviseur,taille*sizeof(unsigned long))) == NULL)
                {
                    printf("ERREUR re-allocation mémoire ...");
                    exit(-1);
                }
            }
        }
        borneInf++;
    }
    if(index)
    {
        /*printf("Diviseurs de %lu : ",nombre);
        for(unsigned long j=0;j<index;j++) { printf(" %lu ",*(diviseur + j)); }
        printf("\n");*/
        tmp = 0; taille = 2;
        for(unsigned long i=nombre-1;i>2;i--)
        {
            divisible = 0;
            for(unsigned long j=0;j<index;j++)
            {
                if(!(i%(*(diviseur+j))))
                {
                    divisible = 1;
                    break;
                }
            }
            if(!divisible)
            {
                *(candidats + tmp++) = i;
                if(tmp == taille)
                {
                    taille *= 2;
                    if((candidats = realloc(candidats,taille*sizeof(unsigned long))) == NULL)
                    {
                        printf("ERREUR re-allocation mémoire ...");
                        exit(-1);
                    }
                }
            }
        }
        /*printf("Nombres premiers avec %lu : ",nombre);
        for(unsigned long j=0;j<tmp;j++) { printf(" %lu ",*(candidats + j)); }
        printf("\n");*/
        calculus(nombre,tmp,candidats);
    }
    else//nombre est premier <=> pas de diviseur
    {
        //printf("%lu est un nombre premier.\n",nombre);
        candidats = realloc(candidats,(nombre-2)*sizeof(unsigned long));
        for (unsigned long i=nombre-1; i>1; i--) { *(candidats+index++) = i; }
        calculus(nombre,index,candidats);
    }
    
    return 0;
}

Plop, je suis pas mal occuppé ces temps çi.

Mais j'ai écrits environs 50% du corrigé.

Prière de ne pas poster ici vos, solutions, et de laisser chaque personne partir sur la même base ;) 

PhilippeBeckx les résultats ne sont pas les bons, mais je vais y revenir dans le corrigé.

Pour t'en convaincre : le résultat avec 666667 est assez convaincant.

Tu ne multiplies que des nombre premier avec 666667 et tu arrives à 0.C'est à dire avec un nombre multiple de 666667 (donc non premier avec 66667)
Comment est-ce possible ?

-
Edité par neuneutrinos 14 août 2017 à 2:08:39

Une question : lorsque N est premier faut-il 

considerer le produit de ses diviseurs (c'est à dire 1et N ) ou bien considéré qu'il n'a pas de diviseur et considerer se produit égal à zéro ?

parce que pour le modulo ça change tout !!

si N est premier, alors il est premier avec tous les entiers > 1 inférieur à lui.

exemple : 11

2,3,4,5,6,7,8,9,10

Pour les nombres premiers il existe un théorème affirmant Que ce résultat sera pour la factorisation , de N-1.

avec 43 je dois trouver (42,42)

avec 1013 (1012,1012)

etc...

-
Edité par neuneutrinos 14 août 2017 à 8:29:29

OK. Apparement un problème de taille des données.

Pour 43 par exemple on aura probablement un nombre tel que 10^45 !?

Faut-il fabriquer un algorithme pour traiter les multiplications avec une infinité de nombre ?

Hello PhilippeBeckx

J'vais te répondre en lieu et place de neuneutrinos (pas taper stp gars)

En fait quand tu fais ton algorithme sur 4 bits, le produit et la somme des éléments passé un certain stade sont en overflow càd qu'un entier codé sur 4 bits NE PEUT PAS stocker le résultat sans dépasser la limite (et te sort n'importe quoi, on dit qu'il est passé en comportement indéterminé (unexpected behavior))... Pour palier à ce problème, en général, on passe sur un type plus grand (8 bits, 16 bits,...). Toutefois, et c'est bien le but du défi, tu ne dois pas les utiliser (ni même caster) !

Pour ce faire tu dois créer un algorithme qui gère le dépassement tout en restant sur 4 bits et c'est là tout le problème du défi

PhilippeBeckx a écrit:

Pour 43 par exemple on aura probablement un nombre tel que 10^45 !?

Sûrement pas, enfin pour le résultat de retour, vu qu'on modulo le nombre. Donc t'auras au plus nombre-1 comme valeur


PS: Les valeurs de retour du produit et de la somme sont des propriétés des mathématiques modulaires, j'vais pas dire combien elles valent, mais il n'y a pas 36000 valeurs possibles 

-
Edité par XDeath 14 août 2017 à 21:46:39

OK XDeath ; je m'y attelle en ce moment même ...

Pourquoi je te taperai ?Je pense terminer le corrigé pour ce week-end

-
Edité par neuneutrinos 15 août 2017 à 9:24:23

Je crois que je vais abandonner  Y aurait moyen de faire en stockant les nombres sous forme de chaines mais en ne traitant que 

des entiers je vois pas ?! Le problème c'est de détecter le moment du dépassement de capacité ainsi que le stockage du résultat 

intermédiaire puis de recommencer les multiplications ; parce que je suis désolé mais pour  43 il faut multiplier tous les nombres 

avant lui ( 1,2,3,4,5, ... 42) et on arrive bien grosso modo vers 10^40 !! C'est l'enfer

Si X%N =a
Si Y%N =b
Alors (X*Y)%N = (a*b)%N

Du coup, pour 43, mon calcul ne dépassera jamais 42² soit 1764 , loin des 10^40.
Cependant... cela n'est pas encore suffisant.

Hahaha une tape amicale nan ? 

N'abandonne pas, t'as jusqu'au weekend pour le finir, c'est largement suffisant 

Indice : Y'a une technique où tu n'es pas obligé de gérer le moment où ça dépasse, renseigne-toi du côté des opérateurs du C mais je te préviens, c'est pas facile