Sommes Egales de Nombres Premiers Consécutifs

Le quatrième et dernier problème de la Google Treasure Hunt 2008 mérite un article à lui tout seul. (J'ai parlé des trois autres dans cet article et ses commentaires)

Il s'agit de trouver le plus petit nombre premier P qui soit en même temps :

  • la somme de 9 nombres premiers consécutifs
  • la somme de 119 nombres premiers consécutifs
  • la somme de 215 nombres premiers consécutifs
  • et la somme de 675 nombres premiers consécutifs !

(les nombres 9, 119, 215 et 675 sont différents pour chaque concurrent...)

C'est étonnant, mais beaucoup de nombres premiers sont des sommes de nombres premiers consécutifs (abrégé SNPC ci après), par exemple :

5+7+11+13+17 = 53
7+11+13+17+19 =67
11+13+17+19+23 =83

De plus, il est fréquent qu'un même nombre premier soit égal à plusieurs SNPC. Par exemple sur ce site on mentionne:

34421 = 269 + … + 709 (71 nombres premiers)
34421 = 1429 + … + 1571 (23 nombres premiers)
34421 = 3793 + … + 3853 (9 nombres premiers)
34421 = 4889 + … + 4937 (7 nombres premiers)
34421 = 11467 + … + 11483 (3 nombres premiers)

Le nombre P recherché n'est donc peut-être pas très grand, d'autant que la somme des 675 premiers nombres premiers ne vaut que 1'578'242. Il n'y a probablement pas besoin de calculer en "bigint", les entiers sur 32 bits, voire 64 disponibles avec n'importe quel langage de programmation devraient suffire. Par contre, il est pratique de disposer de fonctions prédéfinies pour manipuler des nombres premiers, c'est pourquoi j'ai choisi d'utiliser Mathematica.

Les fonctions suivantes suffisent pour résoudre le problème posé:
(code modifié le 4/6/8 suite aux commentaires de b0z0)

SCP[i_, n_] := Sum [Prime[j], {j, i, i + n - 1}]
PSP[n_, i_] := {m = i; While[p = SCP[m, n]; Not[PrimeQ[p]], m++]; p, m}
PSP[n_] := PSP[n, 1]
CPSP[list_] := {p = Map[PSP, list]; p1 = {};
While[p != p1, p1 = p; Print[p];
For[i = 2, i <= Length[list], i++,
While[pi, 1 < p1, 1,
p = ReplacePart[p, i -> PSP[listi, pi, 2 + 1]]];
While[p1, 1 < pi, 1,
p = ReplacePart[p, 1 -> PSP[list1, p1, 2 + 1]]];
];
]

La fonction SCP (Sum of Consecutive Primes) renvoie la somme des n nombres premiers consécutifs en commençant par le i-ème nombre premier en utilisant la fonction prédéfinie Prime[j] qui renvoie directement le j-ème nombre premier.

Cette somme n'étant pas forcément un nombre premier, la fonction PSP (Prime Sum of Primes) appelle répétitivement SCP en augmentant i jusqu'à ce que la somme soit un nombre premier, vérifié grâce au test de primalité PrimeQ, une fonction non triviale bien utile ici. Pour une raison expliquée plus bas, PSP renvoie une paire de résultats : la somme, et l'indice du premier nombre premier de la somme.

Enfin, la fonction CPSP (Compound Prime Sum of Primes) implante l'algorithme que j'ai inventé pour la circonstance. Elle prend en paramêtre la liste des nombres de nombres premiers consécutifs sommés. Pour résoudre notre problème, on appellera  CPSP[{675, 215, 119, 9}]

  1. on initialise une liste p avec les n résultats de PSP obtenus pour chacun des nombres de nombres premiers consécutifs à additioner. Ainsi, pour CPSP[{675, 215, 119, 9}], p est initialisé à {{1583291,2},{149993,15},{41641,10},{127,2}}. Autrement dit, 1583291 est le plus petit nombre premier qui soit la somme de 675 nombres premiers consécutifs, et cette somme commence avec le 2ème nombre premier. 149993 est le plus petit nombre premier qui soit la somme de 215 nombres premiers, en commençant par le 15ème, et ainsi de suite
  2. par paresse (qualité indispensable chez les programmeurs...) , la détection de la fin de l'algorithme est réduite au minimum vital : dès que la liste p n'est plus modifiée par l'algorithme, on arrête
  3. Pour chaque élément de la liste p en commençant par le deuxième, on regarde si la somme est inférieure à la somme du premier indice. Si c'est le cas, on calcule une somme supérieure en incrémentant l'indice correspondant, jusqu'à ce que la somme soit égale à la première, ou la dépasse. Après cette étape, la liste p devient {{1583291,10},{1600981,840},{1589563,1526},{1584829,15997}} : on voit que les sommes 2,3 et 4 ont dépassé la somme 1
  4. Si la somme 1 est plus petite que la somme 2, on augmente la somme 1 jusqu'à ce que'elle atteigne ou dépasse la somme 2. On arrive ainsi à {{1623917,10},{1600981,840},{1589563,1526},{1584829,15997}}. On boucle au point 2

Les trois dernières boucles donnent les listes suivantes qui montrent bien le fonctionnement de l'algorithme:

{{8256361,1127},{8112103,3883},{8115539,6728},{8112787,71376}}
{{8275409,1130},{8259353,3947},{8264171,6833},{8256383,72536}}
{{8275409,1130},{8275409,3954},{8275409,6841},{8275409,72696}}

et voilà : 8'275'409 est égale à la somme des:

  • 675 nombres premiers consécutifs à partir du 1130-ème (9109)
  • 215 nombres premiers consécutifs à partir du 3954-ème (37339)
  • 119 nombres premiers consécutifs à partir du 6841-ème (68821)
  • 9 nombres premiers consécutifs à partir du 72696-ème (919421)

Quelques minutes pour choisir le bon outil (Mathematica) + quelques minutes de programmation + 30 secondes de calcul, c'est gagné !

Comment | , , , , . permalink.
  • b0z0

    Bonjour, j’ai tenté d’implémenter cet algorithme en Java et je doit avouer que j’ai été surpris par son efficacité (bien plus performant que la méthode que j’avais mis au point…). Par contre, j’ai rencontré une petite faille dans l’algorithme : avec mes valeurs (1035,9,5,3) , je me retrouvais dans le cas suivant :

    1035 nombres premiers consécutifs a partir du 352ème : 7049621
    9 nombres premiers consécutifs a partir du 62706ème : 7049621
    5 nombres premiers consécutifs a partir du 107801ème : 7049857
    3 nombres premiers consécutifs a partir du 172870ème : 7049879

    Les 2 premières valeurs étant identiques et les 2 dernières étant « croissante », l’algorithme s’arrête puisqu’il n’y a plus de modification. Je voudrait donc proposer une 5ème étape, dans laquelle on vérifie si les 2ème, 3ème et 4ème valeurs sont identiques (inutile de le faire pour la première puisque cela et déjà fait par le travail conjoint des étapes 3 et 4). Si ce n’est pas le cas, alors on incrémente le i de la somme 1 et on reboucle. Grâce a cela, j’ai obtenu le résultat suivant :

    1035 nombres premiers consécutifs a partir du 356ème : 7086173
    9 nombres premiers consécutifs a partir du 63004ème : 7086173
    5 nombres premiers consécutifs a partir du 108293ème : 7086173
    3 nombres premiers consécutifs a partir du 173696ème : 7086173

  • http://goulu.net Dr. Goulu

    Oui, vous avez raison mon test de fin de l’algo n’est pas suffisant. Comme je l’indique au point 2, je considère la paresse comme une qualité… ou plus sérieusement, l’eXtreme Programming dont je suis adepte consiste à faire juste ce qu’il faut pour que le programme fasse ce pour quoi il a été conçu (et ça le fait dans mon cas) et ensuite l’étendre au besoin pour couvrir d’autres cas (le votre).

    Mais dans ce cas il faut faire simple : pas besoin d’étape 5, il suffit d’améliorer le test à l’étape 2 pour boucler tant que toutes les valeurs ne sont pas égales. On doit pouvoir faire ça très compact en Mathematica, mais je vous laisse le faire en Java ;-)

  • http://goulu.net Dr. Goulu

    Est-ce que l’algo auquel vous aviez pensé utilise un test de primalité ( PrimeQ de Mathematica) ? Je pense que beaucoup de programmeurs imaginent qu’un test de primalité est très coûteux, donc l’évitent ou l’implantent eux-mêmes de façon très peu efficace, alors qu’il existe des algos très rapides comme celui-ci expliqué en Java
    Certains sont effrayés par le fait que ces tests sont « probabilistes », donc peuvent théoriquement se tromper. Ceux là devraient lire le paragraphe 5.5 du livre que je finirai peut-être un jour …

  • b0z0

    Oui, j’utilisai la méthode BigInteger.isProbablePrime() qui est basée sur l’algorithme de Miller Rabin (entre autres…). Mais j’avais pris le problème à l’envers, en testant chaque nombre premier pour voir si il correspondait aux contraintes (très bruteforce comme méthodes….).

    Je suis tout a fait d’accord avec le principe de l’XP, par contre, je voudrais préciser que modifier le test à l’étape 2 ne changerais probablement rien : si on sort de la boucle a l’origine, c’est parce que le tableau de valeurs n’est plus modifié : en restant dans la boucle après un test plus approfondi, ce tableau restera toujours le même indéfiniment (mais bon, je chipote….)

  • http://goulu.net Dr. Goulu

    Ouaip, juste, c’est plutôt le test de l’étape 4 qui doit être revu. Le plus simple est d’intégrer l’étape 4 dans la boucle du 3. J’ai modifié le code de l’article en conséquence, et ça marche!