Mathématice, intégration des Tice dans l'enseignement des mathématiques  
Sommaire > N°45 - mai 2015 > Regards croisés sur l’algorithmique et la (...)

Regards croisés sur l’algorithmique et la programmation (9)
statistiques et arithmétique
Moteur de recherche
Mis en ligne le 10 avril 2015, par Alain Busser, Guillaume Connan, Hubert Raymondaud, Pierre-Marc Mazat, Stéphan Manganelli, Yves Martin

Dans ce numéro de "regards croisés", nos compères marient arithmétique et statistiques.

Cet article peut être librement diffusé et son contenu réutilisé pour une utilisation non commerciale (contacter l’auteur pour une utilisation commerciale) suivant la licence CC-by-nc-sa (http://creativecommons.org/licenses/by-nc-sa/3.0/fr/legalcode)

Bien que non sollicité pour cet article, René Grothmann a déjà publié quelque chose d’intéressant sur la répartition des nombres permiers. Ne pas oublier des résultats récents sur la répartition du k-ième facteur premier.

Contribution d’Alain Busser

  • répartition des nombres premiers avec CoffeeScript
l’article en pdf son source en odt
PDF - 8.6 Mo
OpenDocument Text - 798.9 ko

Les pages 41 à 43 du manuel considèrent les nombres inférieurs à n comme une série statistique, et étudient la fréquence du caractère "est premier avec n". En faisant varier n, on a une nouvelle série statistique : l’indicatrice d’Euler. Cet article étudie la répartition des entiers premiers entre eux.

  • nombre de diviseurs premiers avec awk

statistiques avec awk

Awk est à la fois un langage de programmation et l’outil Unix permettant de programmer dans ce langage. Pour voir en quoi ce langage est intéressant pour faire des statistiques, si on est sous Unix, il suffit, dans une console, d’écrire

man awk

Ceci affiche dans la console le "manuel" d’awk. On y apprend notamment que le nom d’awk est formé des initiales de ses créateurs : Alfred Aho, Peter Weinberger et Brian Kernighan, trois immenses spécialistes de l’informatique théorique. Les voici :

Alfred Aho, spécialiste des compilateurs Peter Weinberger, d’Unix à Google Brian Kernighan, créateur d’Unix et de C
JPEG - 45.3 ko
JPEG - 185.9 ko
JPEG - 47.8 ko

On va utiliser awk pour étudier la répartition des facteurs premiers des entiers de 2 à 1002. Dans un premier temps, on cherche à produire un fichier statistique contenant les facteurs premiers des entiers en question. Cela se fera sans awk mais avec Unix, en l’occurence l’outil bash. Si on écrit

factor 2015

on obtient 2015: 5 13 31 ce qui montre que, dans le fichier à faire analyser par awk, l’entier considéré est en colonne 1 suivi d’un double-point, et ses facteurs premiers dans les colonnes suivantes. Le nombre de facteurs premiers sera donc un de moins que le nombre de colonnes. Pour constituer un tableau pour toutes les valeurs de n allant de 2 à 10 il suffit de mettre "factor $n" dans une boucle de bash :

for n in `seq 2 10`; do factor $n; done

L’affichage produit est le suivant :

2: 2
3: 3
4: 2 2
5: 5
6: 2 3
7: 7
8: 2 2 2
9: 3 3
10: 2 5

On voit en passant que les facteurs sont comptés avec leur multiplicité. Pour produire le fichier statistique téléchargeable en bas de l’article (facteurs.txt), on n’a qu’à boucler sur plus de valeurs de n, et rediriger le résultat dans le fichier facteurs.txt, avec le symbole de redirection ">" qui évoque une flèche allant vers le fichier :

for n in `seq 2 1002`; do factor $n; done > facteurs.txt

Au bout de quelques secondes, le fichier est calculé. On va maintenant pouvoir faire des statistiques dessus avec awk.

Tout d’abord, on peut facilement avoir la liste des nombres premiers entre 2 et 1002 : Ce sont ceux qui n’ont qu’un diviseur premier. Pour ceux-là la variable NF est inférieure à 3. Dans ce cas on affiche le premier facteur premier $2 (deuxième colonne ; en effet le nombre lui-même $1 est suivi d’un encombrant double-point). Pour améliorer l’affichage, on branche un tuyau ("|" qui s’obtient en faisant AltGr et le chiffre 6 du haut du clavier en même temps) ; la sortie du tuyau est envoyée au translateur "tr" de bash, qui est chargé de remplacer les sauts à la ligne ("\n") par des virgules :

awk '{if(NF<3){print $2}}' facteurs.txt | tr "\n" ","

La liste des nombres premiers jusqu’à 1000 est presque immédiatement affichée :

On constate la virgule et l’espace superflus à la fin. Mais au fait, il y en a combien, des nombres premiers inférieurs à 1002 ?

awk '{if(NF<3){print $1}}' facteurs.txt | wc -l

("wc" veut dire "word count" et l’option "-l" veut dire qu’on compte les lignes au lieu des mots.)

On apprend qu’il y en a 168, soit 16,8% des nombres inférieurs à 1000 sont premiers.

Ensuite on peut faire une statistique sur le nombre de facteurs premiers (en comptant les multiplicités). Ce nombre est un de moins que le nombre de "champs" NF ("number of fields"). En effet le premier champ est le nombre lui-même. Alors on fait

awk '{print NF-1}' facteurs.txt | tr "\n" ","

Le résultat est une longue liste de 1000 petits entiers séparés par des virgules. Une légère modification permet de calculer le nombre moyen de facteurs premiers (avec multiplicité) entre 2 et 1002 : On additionne le nombre de facteurs premiers, et quand on a fini, on affiche le quotient de cette somme par le nombre de lignes (parce que c’est ça, une moyenne : La somme divisée par l’effectif total) :

awk '{somme+=NF-1} END {print somme/NR}' facteurs.txt

On apprend alors que le nombre moyen de diviseurs premiers est 2,88012. Résultat à placer dans un repas... Et le nombre médian de diviseurs premiers ? On peut brancher un tuyau entre la sortie de awk et l’entrée de sort -n qui trie numériquement les nombres obtenus :

awk '{print NF-1}' facteurs.txt | sort -n

Le résultat est formé de nombres allant de 1 (nombres premiers) à 9 (deux fois). Pour connaître la médiane, il suffit de lire le 500ème nombre de cette longue liste (et le 250ème pour Q1 et le 750ème pour Q3). On branche un tuyau entre le tableau et tail -500 qui renvoie les 500 derniers éléments du tableau, et un autre tuyau vers head -1 qui renvoie le premier élément du tableau obtenu. Ceci donne la médiane :

  1. awk '{print NF-1}' facteurs.txt | sort -n | tail -500 | head -1
  2. awk '{print NF-1}' facteurs.txt | sort -n | tail -750 | head -1
  3. awk '{print NF-1}' facteurs.txt | sort -n | tail -250 | head -1

Télécharger

Ce qui révèle que la médiane, le premier quartile et le dernier quartile valent respectivement 3, 2 et 4. Cela aussi est à placer à l’occasion dans un repas...

Un tableau d’effectifs peut même être fait avec

awk '{effectifs[NF-1]++} END {for (n=1;n<=9;n++) {print effectifs[n]}}' facteurs.txt

On remarque que la construction du tableau d’effectifs est très concise : {effectifs[NF-1]++} ; l’affichage est plus long : {for (n=1;n<=9;n++) {print effectifs[n]}}. On trouve ces effectifs :

1 2 3 4 5 6 7 8 9
168 299 249 149 76 37 14 7 2

Voici le diagramme en bâtons [1] correspondant :

image/svg+xml 0 1 2 3 4 5 6 7 8 9

Et les facteurs premiers comptés sans multiplicité ? Après tout 8 n’a qu’un facteur premier qui est 2, non ? On peut remplacer les suites de 2 par un seul 2 avec cette expression régulière :

awk '{sub(/( 2)+/, " 2"); print }' facteurs.txt > uniques.txt

sub veut dire "substituer" ; l’expression à substituer est entre les "/" et vaut ( 2)+ : Un espace suivi d’un 2, le tout au moins une fois. Donc si, sur une ligne, apparaît une suite non vide de " 2", on demande à awk de la remplcer par une seule fois le " 2". Le début du fichier uniques.txt ainsi conçu ressemble à ceci :

Les facteurs 2 sont donc bien uniques. Il reste à faire la même chose avec les 3, 5 etc. Globalement perl permet de remplacer des expressions régulières variables du type "un vide suivi d’un nombre, le tout répété au moins une fois" avec ceci [2] :

perl -pe 's/\n/ \n/; s/(\d+ )\1+/$1/g' facteurs.txt > uniques.txt

qui produit le fichier uniques.txt téléchargeable en bas de l’article, sur lequel on peut refaire les statistiques précédentes. Par exemple voici le début de la répartition du plus petit facteur premier (statistiques sur la colonne $2 [3]) :

2 3 5 7 11 13 17 19 23 29 31 37
501 167 67 39 21 17 11 9 7 3 2 1

Le plus petit facteur premier est 2 pour les nombres pairs et 3 pour les nombres impairs multiples de 3. Pas de surprise donc, la moitié des nombres entre 2 et 1002 sont pairs, et le sixième de ces nombres a 3 pour plus petit facteur premier. On peut le dire avec le vocabulaire des fractions : Pour la suite du tableau, on a enlevé la moitié 1/2 (les nombres pairs) puis le tiers de la moitié restante (1/3×1/2=1/6). Il reste alors le tiers des nombres de départ, dont on enlève le cinquième 1/5×1/3=1/15 : Un nombre sur 15 a 5 pour plus petit facteur premier. Et le quinzième de 1000 fait bien environ 67. Ensuite il reste 1/3-1/15=4/15, parmi lesquels le septième, soit 1/7×4/15=4/105 des nombres de départ, ont 7 pour plus petit diviseur premier. Cela fait bien 39 nombres.

Et les statistiques sur le second facteur premier (colonne $3) :

3 5 7 11 13 17 19 23 29 31 37
167 100 66 40 29 20 17 15 16 17 15

Celle du troisième facteur premier :

5 7 11 13 17 19 23 29 31 37
33 34 24 26 25 24 19 14 12 11

Surprise : Le quatrième facteur premier le plus fréquent n’est pas 5 comme on pouvait s’y attendre, mais 7.

Et le quatrième facteur premier ?

7 11 13 17 19 23 29 31
4 6 5 2 2 2 1 1

Contribution de Guillaume Connan

A venir, courant juin.

Contribution de Stephan Manganelli

Entre 2 et 1002, il y a 1000 entiers. Combien d’entre eux ont 3 comme plus petit facteur premier ? Stephan Manganelli répond avec LARP, et il semble y avoir peu de publications sur l’arithmétique avec LARP, ce qui confère à cet article un caractère innovant

l’article en pdf
PDF - 470.1 ko

Contribution d’Yves Martin

"C’est pas pour dire mais impair multiple de 3 : y a un nombre sur 6, et 1/6
ça s’approche par 0,16667

Est-ce qu’il faut vraiment des stats pour ça ?"

Quelques réflexions sur le sujet

La question fondamentale posée ici est celle de la part que l’on fait encore, dans la société, dans l’enseignement, à la théorie, à la conceptualisation par rapport à la part de plus en plus grande donnée à la simulation.

La question n’est pas triviale pour de nombreuses raisons. Que l’on pense à l’entrée dans l’algèbre au collège : quelle part de complexité ? Faut-il commencer par des problèmes d’arithmétique algébrisés comme ici de la division euclidienne habillée de statistique ?

Mais que la simulation remplace la théorie même dans les cas élémentaires n’est-ce pas aussi la même chose que sortir une calculatrice pour savoir "combien fait" (ie quel approximation décimale) le nombre 3/4 ? De la paresse intellectuelle...

D’un autre côté la simulation permet d’être opérationnel avant toute théorisation. Mais quelle société scientifique veut-on construire ?

J’ai par exemple été surpris que, ayant modélisé la forme de la comète Tchouri, pour calculer la trajectoire optimale de Philaé, on n’ait pas fait tourner des équations différentielles, que nenni. On a simulé environ un milliard d’atterissages (sur l’unique lieu prévu) et on a choisi ’le meilleur". En un sens que je ne connais pas mais probablement le plus stable, le plus robuste aux conditions initiales.

Donc la simulation est présentée y compris au plus haut niveau !

Je n’oublie pas non plus le concept de 4° paradigme scientifique qui veut que ce seront des algo de big data qui feront les conceptualisations de demain, car l’approche humaine reste rudimentaire en général : l’humanité n’a finalement trouvé - selon les partisans du 4° paradigme - que des invariants triviaux qui s’expriment souvent en une formule d’une ligne, même Schrodinger ....

D’ou l’argument "apprendre à simuler c’est apprendre la science de demain".
Mais bon, faut-il tout abandonner de la réflexion théorique pour autant ? Je serais plus prudent.

Mais tout va très vite. Aux USA déjà et à la rentrée prochaine en Finlande, on va avoir les premières générations d’enfants qui n’auront pas appris l’écriture manuscrite mais directement le clavier en maternelle ... Donc pour la conceptualisation c’est peut être aussi, partiellement, sur les rails ...

@ suivre


notes

[1obtenu en exportant les effectifs vers alcoffeethmique.

[2le programme perl est celui qui est écrit entre apostrophes ; l’option -pe demande justement à perl d’exécuter ce programme. Ce programme est formé de deux sous-programmes, exécutés l’un après l’autre, et séparés par un point-virgule. Le premier remplace ("s") le saut à la ligne ("\n") par la même chose mais précédé d’un espace. Cela permet au second programme de repérer les champs numériques, ce sont des nombres à la fois précédés et suivis d’un espace. Le seocond programme va substituer ("s") globalement ("g") la première expression régulière par la seconde. La syntaxe est donc s/e1/e2/g. On constate que la première expression régulière est la plus complexe des deux. L’expression régulière entre parenthèses est un espace suivi d’une suite de chiffres ("\d" comme "digit"). Le "+" veut dire qu’il y a au moins un chiffre. L’expression entre parenthèses décrit donc un entier précédé et suivi d’un espace. Sitôt que perl a trouvé ce genre d’expression, il l’enregistre dans une variable "\1". Le "+" situé après l’expression régulière siginfie donc que le nombre précédé d’un espace a été trouvé au moins une deuxième fois, et doit donc être remplacé par la variable 1, une seule fois. Ou plus précisément par son contenu, d’où le dollar devant le dernier "1"

[3Le script ayant affiché ce tableau d’effectifs est le suivant :awk '{effectifs[$2]++} END {for(n=2;n<=40;n++){if(effectifs[n]){print n,"->", effectifs[n]}}}' uniques.txt

Documents associés à l'article
     |   (Texte - 11.7 ko)
     |   (Texte - 11.2 ko)
Réagir à cet article
Vous souhaitez compléter cet article pour un numéro futur, réagir à son contenu, demander des précisions à l'auteur ou au comité de rédaction...
À lire aussi ici
MathémaTICE est un projet
en collaboration avec
Suivre la vie du site Flux RSS 2.0  |  Espace de rédaction  |  Nous contacter  |  Site réalisé avec: SPIP  |  N° ISSN 2109-9197