Discussion :

[MarvinLeRouge]

Bonjour,

J'ai un problème de recherche de nombres premiers, mais je me heurte à de gros problèmes d'optimisation : mon code (en python, mais ça n'a pas d'importance) ne pourra pas résoudre le problème avant au mieux quelques années.
Si quelqu'un peut me donner un coup de main sur la façon d'optimiser ça, mathématiquement et/ou algorithmiquement, ce serait vraiment sympa.

Problème :

Le trio de nombres premiers (3, 37, 67) possède une propriété intéressante. Si on concatène deux de ses nombres, on obtient toujours un nombre premier (337, 367, 373, 673, 3767, 6737 sont tous premiers).
Le quadruplet (3, 7, 109, 673) possède également cette propriété.

Intéressons-nous aux quintuplets la possédant. Plus particulièrement au quintuplet (p1, p2, p3, p4, p5) défini ainsi :

p1, p2, p3, p4 et p5 sont des nombres premiers
p1 < p2 < p3 < p4 < p5
Si on concatène deux nombres du quintuplet, on obtient toujours un nombre premier
La somme S=p1+p2+p3+p4+p5 est la plus petite possible qui soit supérieure à 100 000

J'ai la liste des nombres premiers de 2 à 100k, car j'ai supposé que la solution comprenait probablement uniquement des nombres inférieurs à 100k, mais c'est une pure supposition.
J'ai la liste des nombres premiers de 2 à 1 milliard
Et je l'ai également triée par longueur (donc tous les nombres premiers inférieurs à 10, de 10 à 99, de 100 à 999, etc...

Merci d'avance

[Flodelarab]

Bonjour

• Tu expliques une situation, mais pas un problème. On ne sait pas ce que tu veux faire.
• Tu demandes une optimisation mais tu n'as rien fait. Donc, rien n'est à optimiser.

Et puis, même la situation n'est pas super bien décrite. Le triplet (3;3;7) est-il un triplet de départ acceptable ? Autrement dit, peut-on répéter les nombres ?

[CosmoKnacki]

Autrement dit, peut-on répéter les nombres ?

À priori, je dirais non puisque p1 < p2 < p3 < p4 < p5.

[MarvinLeRouge]

Pour l'instant, j'ai la liste des nombres premiers, de 2 à 100 000, et de 100 000 à 1 milliard, et j'ai 5 boucles imbriquées

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
pour 0 de 1 à n - 5
  pour j de i + 1 à n - 4
    si concat(p[i], p[j]) est dans p et si concat(p[j], p[i] est dans p alors
      pour k de j + 1 à n - 3
        si concat(p[i], p[k]) est dans p et si concat(p[k], p[i] est dans p et si concat(p[k], p[j] est dans p et si concat(p[j], p[k] est dans p alors
          ...
          // Et on continue sur 5 niveaux

mais c'est inefficace.
J'ai essayé de construire une liste de tous les premiers dont la concaténation est aussi un entier, mais c'est aussi extrêmement long.

NB : Si la concaténation de 2 premiers est plus grande que le max du tableau des premiers (1 milliard), on fait un test de primalité en utilisant le tableau en question pour les diviseurs potentiels.

[Guesset]

Bonjour CosmoKnacki,

À priori, je dirais non puisque p1 < p2 < p3 < p4 < p5.

Il y a une autre raison, ces nombres seraient de la forme 10ⁿp+p (n étant le nombre de chiffres de p). nous aurions donc comme résultat un nombre multiple de 10ⁿ+1 donc non premier. Il n'y a que le cas de p = 1 qui marcherais, mais p=1 est lui même exclu des premiers.

Salut.

[CosmoKnacki]

Bien vu, effectivement, la concatenation d'un même nombre est forcément multiple de 11, 101, 1001... Sauf pour 1 qui n'est pas premier de toute façon.

À noter que pour ce qui nous occupe, on peut d'emblée retirer 2 et 5 de la liste.

[Guesset]

Bonjour,

Je crois que j'aurais tendance à prendre le problème à l'envers.

Je partirais des plus grands de la liste pour aller vers les plus petits.

1. Balayage descendant. Pour chaque n j'estimerais la puissance de 10 correspondante, la diviserais par 2 et arrondirais le résultat à l'entier supérieur t, pour pouvoir calculer d = 10^t
2. Div/mod d me donnent alors deux nombres qui doivent être premiers pour ce sujet.
3. Si c'est le cas, alimenter deux entrée dans une liste (triée). Pour chaque entrée, augmenter cmpt + 1, noter son index premier propre et ajouter à sa propre liste secondaire d'index de premiers celui qui est associé.
4. Réitérer en prenant d = 10*d jusqu'à d >= n. Revenir en 2
5. Passer au n inférieur. Revenir en 1
6. Nettoyage. Ensuite, pour des couples parmi 5, supprimer toutes les entrées de la liste dont le compteur cmpt est inférieur à 4.
7. Diminuer le compteur de toutes les entrées de la liste secondaire dont un des index de premier ne correspond pas à une entrée de la liste principale et la retirer de cette liste secondaire. S'il y a au moins une diminution, revenir en 6

A la fin nous avons une liste réduite (voire vide) d'entrées qui sont toutes associées à au moins 4 autres. Il faut vérifier que les sous listes (augmentées de l'index propre à l'entrée) se recoupent et que le recoupement est bien d'au moins 5 (si plus il y a des combinatoires dans l'air).

L'idée est d'utiliser l'appauvrissement naturel. Le découpage d'un premier en deux nombres sera invalide dès que l'un d'eux sera non premier ce qui sera très fréquent. On devrait être, au doigt mouillé, en O(nlog(n)).
Comme beaucoup d'algorithmes qui cherchent à gagner du temps, celui-ci est assez gourmand en espace mémoire.

C'est une idée non testée qui mérite certainement des aménagements et correctifs.

Salutations

[Flodelarab]

Bravo pour vos réponses brillantes.

Ici, je n'ai qu'un fichier avec les nombres premiers jusqu'à un million. J'ai considéré qu'un n-uplet était un (n-1)-uplet auquel on rajoutait un élément. On va donc déterminer les couples de nombres premiers qui s'acceptent, puis on va successivement agrandir le n-uplet. Comment ? En calculant un score. On ajoute 1 si le nombre est toléré par un nombre existant déjà dans le n-uplet. Exemple : Si un nombre atteint un score de 3 à partir d'un triplet c'est que ce nombre est compatible avec tous les autres. On peut donc créer un quadruplet.

Voici le code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
./uplet.awk prems.txt >couples.txt
 
./agrandir_uplet.awk couples.txt couples.txt >triplets.txt
echo "----- triplets -----"
cat triplets.txt
./agrandir_uplet.awk couples.txt triplets.txt >quadruplets.txt
echo "----- quadruplets -----"
cat quadruplets.txt
./agrandir_uplet.awk couples.txt quadruplets.txt >quintuplets.txt
echo "----- quintuplets -----"
cat quintuplets.txt

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#!//usr/bin/awk -f
 
{
        p[NR]=$1;
        v[$1]++;
}
 
END{
        for (i=1;i<=NR;i++)
        {
                #print "----",i,p[i],"-----"
                for (j=i+1;j<=NR;j++)
                        if (length(""p[i]""p[j])<7)
                        {
                                if ((v[p[i]""p[j]]!="")&&(v[p[j]""p[i]]!=""))
                                        print p[i],p[j];
                        }
                        else
                                break;
        }
}

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#!/usr/bin/awk -f
 
(FNR==NR){
        q[$1]++;
        c[$1,q[$1]]=$2;
        next;
}
 
{
        delete score;
        for (r=1;r<=NF;r++)
                for (i=1;i<=q[$r];i++)
                        score[c[$r,i]]++;
        for (m in score)
                if (score[m]==NF)
                        print $0,m;
}

Et la fin de la sortie :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
631 739 751
661 877 883
683 719 911
709 823 967
719 911 947
733 883 991
809 821 827
809 929 983
821 827 857
----- quadruplets -----
3 7 109 673
3 37 67 5923
3 37 67 2377
7 19 97 4507
7 19 97 3727
23 311 677 827
----- quintuplets -----

Il ne trouve pas de quintuplet. Ce n'est pas étonnant car la plus grosse concaténation ne peut pas dépasser 6 chiffres.
Pour information, le temps total d'exécution du programme ne dépasse pas 2 secondes.