Annonce

Bienvenue sur le site support de mes ouvrages d'introduction à SAS

La 4ème édition de mon ouvrage est toujours disponible !

Où trouver cet ouvrage ?


#1 04-05-2016 07:57:13

SAS-SR
Administrateur
Lieu: Université d'Orléans
Date d'inscription: 01-09-2008
Site web

[archive] Lisbeth Salander

Bonjour

Je vais vous étonner : je ne lis pas que des livres qui ont trait à SAS… Il m’arrive de lire autre chose.

Et en ce moment, je lis Millénium IV… et Lisbeth Salander m’a donné l’idée de ce nouveau sujet des beaux mercredis (merci Lisbeth !)

Page 316, notre Lisbeth est avec August qui griffonne des chiffres sur un morceau de papier et, comme c’est un autiste savant, il ne griffonne pas n’importe quels chiffres. Il griffonne ainsi la suite 641 647 653 659 qui ne vous dira rien… Lisbeth, n’est pas contrairement à nous, une idiote : elle reconnait immédiatement un "sexy prime quadruplet" ! (trop forte, Lisbeth !).

Et vous allez me dire : mais qu’est-ce qu’un « sexy prime quadruplet » (que le traducteur n'a pas traduit) ?

Pffff… vous pourriez faire un effort… Et bien il s’agit d’un quadruplet de quatre nombres premiers qui différent de 6. (641+6=647 etc. ).

Et pourquoi dit-on « sexy » ? Là, c’est wikipédia qui nous dit qu’il s’agit d’un jeu de mot… SEXy pour SIX…
https://fr.wikipedia.org/wiki/Nombres_premiers_sexy

Pour la semaine prochaine, vous allez devoir trouver tous les sexy primes quadruplets parmi les 100 000 premiers nombres premiers.

Bon… je vais vous aider un peu en vous proposant un programme qui génère les 100 000 premiers nombres premiers (en 2.20 secondes).

Code:

data np(keep=np) ;
   array p(100000) _temporary_;
   np=2;
   p(1)=2;
   remp=1;
   output;
   do np=3 to 10**9 by 2 until (remp=100000);
      do j=1 to remp;
         blop=0;
         if p(j)>np**0.5 then leave;
         if mod(np,p(j))=0 then do ;
              blop+1; 
              leave;
         end;
      end;
      if blop=0 then do ;
         remp+1;
         p(remp)=np;
         output;
      end;
   end;
run;

En fouillant bien, vous trouverez dans le forum de discussions un sujet posté il y a quelques années dans lequel deux étudiants (enfin, à l’époque, ils étaient étudiants…) avaient proposés un programme en réponse à un exercice que je proposais alors.

Ces deux (ex)étudiants ont fait du chemin depuis puisqu’ils travaillent tous les deux chez SAS France…

Bref, on va revenir sur le programme proposé par Vincent ICI (vous ne pouvez suivre ce lien que si vous êtes inscrit sur ce site). Nous n’avons pas approfondi ce programme parce que nous nous sommes ensuite perdus dans des discussions sur les performances de SAS 9.2, 9.3, 9.4 , 32 Vs. 64 bits…

Ce programme était vraiment très malin et le programme proposé plus haut (et 4 ans plus tard…) tente de l'améliorer.

Nous construisons une table NP qui va contenir les 100 000 premiers nombres premiers.

Code:

   array p(100000) _temporary_;
   np=2;
   p(1)=2;
   remp=1;
   output;

On commence par créer un tableau temporaire au moyen d’ARRAY – celui-ci contient 100 000 variables (et sur mon portable, qui a quelques années, ça passe sans problème).

NP=2 : la première de ces variables a pour valeur 2 (le premier nombre premier) et on donne 1 comme modalité à une variable appelée REMP. On a là notre première observation d'où l'instruction OUTPUT.

Code:

   do np=3 to 10**9 by 2 until (remp=100000);
      do j=1 to remp;
         blop=0;
         if p(j)>np**0.5 then leave;
         if mod(np,p(j))=0 then do ;
              blop+1; 
              leave;
         end;
      end;

On va ensuite regarder toutes les valeurs comprises entre 3 et 10**9 en allant de 2 en 2 (à moins que REMP soit égale à 100 000).

Explication : un nombre premier ne peut pas être pair (pas besoin d’être Lisbeth Salender pour le comprendre) – il est donc inutile de regarder les nombres pairs (d’où le BY 2).

REMP est la variable qui va compter le nombre de nombres premiers que nous allons trouver. Nous en voulons 100 000 d’où la condition UNTIL (REMP=100000).

Une seconde boucle intervient – elle va aller de 1 jusqu’à la valeur de REMP. Ce que vous devez comprendre ici, c’est que nos nombres premiers vont être, certes, produits dans une table, mais ils vont aussi être présents dans notre tableau créé par ARRAY.

REMP est égal au nombre de nombre premier trouvé : si on a par exemple trouvé 100 nombres premiers, ce n’est pas la peine de regarder les variables X101 – X100000 de notre tableau.

On fixe alors la valeur d’une variable BLOP à 0 et vient après une étrange condition :

Code:

if p(j)>np**0.5 then leave;

Si le nombre premier contenu dans la variable P(J) du tableau est supérieur à la racine carrée du nombre que l’on teste afin de savoir s’il est premier, alors, on doit quitter la boucle.

Pourquoi cela ?

103 est un nombre premier. Au moment où NP=103, nous savons déjà que 2,3,5,7,11,13…97 et 101 sont des nombres premiers. Et on sait déjà (voir ensuite) que 103 n’est pas divisible par 2,3,5 et 7. Pourquoi alors vérifier que 103 est divisible par 11 (entier immédiatement supérieur à la racine carrée de 103) puisqu’il ne peut pas être le produite de 11 par un nombre supérieur à 11 : le résultat serait en effet supérieur à 103.

Que fait-on ensuite ? On utiliser la fonction MOD :

Code:

         if mod(np,p(j))=0 then do ;
              blop+1; 
              leave;
         end;

MOD(NP,p(j)) donne le reste de la division de NP par p(j) : si c’est égal à zéro, c’est que le nombre n’est pas premier. On modifie la valeur de BLOP et on peut quitter la boucle.

Code:

if blop=0 then do ;
         remp+1;
         p(remp)=np;
         output;
      end;

Si, à la sortie de la boucle, BLOP est toujours égal à zero, alors nous avons un nombre premier. On augmente la valeur de REMP de 1, on enregistre ce nombre premier dans le tableau (P(REMP)=NP) et on peut alors écrire l’observation. On remonte ensuite à la boucle sur NP et regardons si la valeur suivante de NP n'est pas un nombre premier.

Voilà, vous savez tout.

Maintenant, c’est à votre tour !

Trouvez tous les sexy prime quadruplets parmi les 100 000 premiers nombres premiers !

A la semaine prochaine !

Hors ligne

 

#2 08-05-2016 06:40:06

SAS-SR
Administrateur
Lieu: Université d'Orléans
Date d'inscription: 01-09-2008
Site web

Re: [archive] Lisbeth Salander

Petit ajout pour vous convaincre que l’exercice proposé n’est pas si simple que ça… (et qu’il mérite que vous vous penchiez dessus…)

Voici les 10 premiers sexy primes quadruplets (et il y en a 404 à trouver) :

Code:

Obs.    sexy

   1    5-11-17-23
   2    11-17-23-29
   3    41-47-53-59
   4    61-67-73-79
   5    251-257-263-269
   6    601-607-613-619
   7    641-647-653-659
   8    1091-1097-1103-1109
   9    1481-1487-1493-1499
  10    1601-1607-1613-1619

Regardez bien le premier quadruplet : 5-11-17-23

Entre 5 et 11, il y a un autre nombre premier (7).

Aussi, si vous avez trouvé 234 quadruplets et que le premier quadruplet trouvé est 251-257-263-269, vous vous êtes limités à des quadruplets particuliers : les quadruplets pour lesquels il n’y a pas de nombres premiers entre chacun des membres du quadruplet.

A mercredi prochain...

Ce sujet est maintenant archivé - seuls les utilisateurs inscrits de www.sas-sr.com peuvent consulter l'intégralité du sujet et les réponses aux questions posées.
pour vous identifier, suivez ce lien
pour vous inscrire, suivez ce lien

Hors ligne

 

Pied de page des forums

Propulsé par FluxBB
Traduction par FluxBB.fr
Flux RSS