Magazine

Sommes Egales de Nombres Premiers Consécutifs

Publié le 03 juin 2008 par Dr_goulu @goulu

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é:

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[p[[i, 1]] < p[[1, 1]],
      p = ReplacePart[p, i -> PSP[list[[i]], p[[i, 2]] + 1]]];
    ];
   While[p[[1, 1]] < p[[2, 1]],
    p = ReplacePart[p, 1 -> PSP[list[[1]], p[[1, 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é !


Vous pourriez être intéressé par :

Retour à La Une de Logo Paperblog

Ces articles peuvent vous intéresser :

  • Inlandsis : Premiers Froids

    Un nom a vous glacer les os, Inlandsis, qui désigne un glacier continent (comme sur le Groenland) et des sons a vous ravirent les esgourdes ! Lire la suite

    Par  Danydan
    MUSIQUE
  • Sommes-nous réels ?

    La question semble saugrenue, on se demande même comment une telle idée est concevable . Mais à y regarder de plus près, l'évacuer d'un revers de main serait... Lire la suite

    Par  Olivier Leguay
    SCIENCE, SCIENCE & VIE
  • Sommes-nous vaccinés ?

    Sommes-nous vaccinés

    Il y a une expression utilisée en économie qui dit que : "Quand les Américains toussent, on attrape le rhume". C'est encore plus vrai aujourd'hui avec le... Lire la suite

    Par  Louis Sabourin
    FINANCES, IMMOBILIER
  • Dès 3 mois, un nourrisson a le sens des nombres

    Tous les êtres humains, quelles que soient leur culture et leur éducation, possèdent ce qu’on appelle le sens du nombre. Ce sens du nombre nous permet, par... Lire la suite

    Par  Guy Marion
    SCIENCE, SCIENCE & VIE
  • le 3 et le 7 sont mes nombres préférés

    Ca tombe bien puisque mon prochain bébé qui devrait naître aujourd'hui (sans douleur ni péridurale), est le numéro 3 de la saga des Agathe ainsi que le 7ème... Lire la suite

    Par  Irène Pauletich
    JOURNAL INTIME, TALENTS
  • Derrière les images se cachent des nombres

    Le tableau de Seurat, Un dimanche après-midi sur l'île de la Grande Jatte, réalisé avec 106000 canettes en aluminium, soit le nombre de canettes utilisées toute... Lire la suite

    Par  Koreus
    INSOLITE, VIDÉOS INSOLITES
  • Mes premiers textes imprimés...

    premiers textes imprimés...

    Participation à la revue Ananda #4 avec dessins... et textes. Deux têtes de l'art. J'apprécie beaucoup la mise en page en général, mais là je dois dire que mes... Lire la suite

    Par  Thibault Balahy
    BD & DESSINS, TALENTS

A propos de l’auteur


Dr_goulu 3475 partages Voir son profil
Voir son blog