Inscription / Connexion Nouveau Sujet
Recherche de nombres premiers sur critères
Bonjour,
J'ai le problème suivant :
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 bien un code (en Python, mais c'est sans importance) qui traite le problème, mais j'ai un sérieux problème d'optimisation : ça va durer des années (littéralement).
J'ai la liste des nombres premiers de 2 à 100 000 et au-delà jusqu'à 1 milliard, car j'ai supposé que la solution était probablement composée de nombres inférieurs à 100k.
Et je les ai également classés par puissance de 10, pour améliorer la recherche lorsqu'on les juxtapose.
Merci d'avance
Ce qui peut arriver de pire, c'est que tous les p_i aient le même nombre de chiffres (n). Dans ce cas, il faut savoir vérifier rapidement si un n'importe quel nombre inférieur à 10^(5n+1) est premier. Et il faut le faire 5 * 4 = 20 fois.
Si n = 3, ça va encore avec un crible et une recherche dichotomique. Si n >= 4, c'est plus ou moins foutu.
Si on ignore la contrainte de minimalité,
{p1, ..., p5} est solution si et seulement si c'est aussi le cas de
- A_j = {p1,...,p5} \ {pj} pour tout j
- p_jA_j et A_jp_j sont inclus dans l'ensemble des nombres premiers
Mais le problème, c'est que ça ne répond à la question que si p1 + ... + p4 > 10^5-11.
En général, rien ne dit que la solution pour 5 premiers puisse être construite à partir de celle pour 4 premiers ou moins.
Annuler
connectez vous