Playing - Nombres Premiers
Visualisation des nombres premiers (D3JS & Canvas)
d3js3.x
jquery3.2.1
Sources :
Ce tutoriel s'intéresse aux nombres premiers (un nombre divisible uniquement par lui-même et par un). Le but ici est d'étudier les différentes formes de visualisation que nous pouvons utiliser pour représenter la distribution des nombres premiers. A cette fin nous utiliserons la fonction suivante qui est assez efficace pour déterminer si un nombre est premier ou non.
function isPrime(i) {
if (i === 1 || i === 0) return false;
if (i < 4) return true; // 2 & 3
if (i % 2 === 0) return false; // Pair
if (i < 9) return true; // 5 & 7
if (i % 3 === 0) return false;
var lim = Math.sqrt(i) + 1;
for (var j = 5; j <= lim; j += 6) {
if (i % j === 0) return false;
if (i % (j + 2) === 0) return false;
}
return true;
}
L'efficacité de cette fonction vient du fait qu'on ne tente pas de faire le modulo entre le nombre i par tous les nombres compris entre 1 et i
comme on pourrait vouloir le faire intuitivement mais que l'on s'arrête à la racine carré de i. Ainsi lorsque i = 1000000 on
s'arrête à 1000. L'explication est assez simple : si i est divisible par un nombre plus grand que 1000, notons le p alors
il est le produit de p et d'un nombre plus petit que 1000 (sinon le produit dépasserait 1000000, 1000 * 1000 = 1000000).
Le reste du code est une optimisation pour ne tester que les nombres finissant par 1, 3, 7 ou 9 (les autres ne peuvent pas être premier, ils sont
soit paires soit divisible par 5).
Nous cherchons à visualiser les nombres premiers en utilisant D3JS, commençons par leur attribuer une couleur. Les couleurs suivantes indiquent le dernier chiffre du nombre (11 est premier, sa couleur sera le bleu).
Nous choisissons ici de représenter tous les nombres premiers compris entre 0 et 10000 sous la forme d'une matrice, si la cellule est blanche alors le nombre n'est pas premier, si celle-ci est colorée alors le nombre est premier et sa couleur indique s'il finit par 1, 2, 3, 5, 7 ou 9. La matrice représente 100 cellules à l'horizontal et 100 à la verticale, ainsi chaque colonne finit par un chiffre identique (ce qui explique les colonnes de bleu, de vert...). Notez qu'une seule cellule est orange, c'est celle du chiffre 2 (tout en haut à gauche, même chose pour le 5 en violet). Par ailleurs, la visualisation est plutôt de petite taille alors qu'elle représente 10000 nombres, c'est d'autant plus étonnant quand on sait que chaque nombre est représenté par un carré de 4 pixels de large et de haut. Mise à part la verticalité des couleurs, il ne semble n'y avoir aucune règle, il y a des blancs plus ou moins gros à des emplacements ne répondant à aucune logique évidente.
Pour générer cette visualisation, nous avons utilisé un canvas et le code D3JS suivant.
var colors = ['','#1f8dd6','#f37b1d','#5eb95e','','#8058A5','','#dd514c','','#fad232'];
drawCanvas("#canvas1", 10000, 400, 400, 4, 4);
function drawCanvas(canvasId, size, width, height, dx, dy) {
var canvas = d3.select(canvasId).append("canvas")
.attr("width", width)
.attr("height", height);
var context = canvas.node().getContext("2d");
var x = 0,
y = 0;
for (var i = 0; i < size; ++i ) {
if (isPrime(i)) {
context.fillStyle = colors[i % 10];
context.fillRect(x, y, dx, dy);
}
x += dx;
if (x >= width) {
x = 0;
y += dy;
}
}
}
Par facilité, les couleurs sont placées dans un tableau représentant tous les chiffres de 0 à 9. dx et dy représente
la largeur et la hauteur de chacune des cellules.
Continuons sur notre lancée et tentons de représenter les nombres premiers de 1 à 1000000. Il nous suffit pour cela de rappeler la fonction drawCanvas
avec le code suivant.
drawCanvas("#canvas2", 1000000, 1000, 1000, 1, 1);Cette fois-ci les cellules font seulement 1 pixel et le fond est noir (voir le CSS) pour offrir une meilleure visualisation des points. Il est amusant de constater à quel point cette image ressemble à celle d'un ancien téléviseur dont la réception hertzienne serait défaillante même si l'on devine encore la verticalité des couleurs.
Parmi les entiers naturels N, il y a de moins en moins de nombres premiers à mesure que N grandit. Mais il y en a quand même une infinité (c'est Euclide
qui l'a prouvé). Le graphique suivant montre en bleu le nombre de nombres premiers entre 0 et 100 (ce nombre est noté π(x)).
Ce nombre est négligeable devant x lorsque x tend vers l'infini (Théorème de la raréfaction des nombres premiers).
Gauss a fait une approximation de ce nombre en utilisant le logarithme népérien (il s'agit du Théorème des nombres premiers et la courbe de cette approximation est en rouge dans le graphique) :
Un peu plus tard Il a été prouvé que π(x) est égal lorsque x tend vers l'infini à li(x) (la fonction logarithme intégrale
représentée en vert dans le graphique). Les mathématiques derrières cette démonstration sont d'un niveau plutôt élevé, plus d'information ici :
Fonction de compte des nombres premiers.
Revenons à des informations plus visuelles avec la spirale d'Ulam, ou spirale des nombres premiers, qui est une méthode simple pour la représentation des nombres
premiers qui révèle un motif qui n'a jamais été pleinement expliqué. Pour réaliser cette spirale, il faut écrire 1 au milieu d'une feuille puis 2 sur la droite,
ensuite 3 juste au dessus et ainsi de suite de manière à former une spirale comme dans le schéma ci-dessous (plus de détails sur Wikipedia :
Spirale D'Ulam).
Il nous suffit de dessiner cette spirale dans un canvas avec D3JS pour représenter chaque nombre premier par sa couleur et l'on voit tout de suite se dessiner
plusieurs diagonales. Elles représentent des fonctions polynomiales qui sont connues pour posséder un grand nombre de nombres premiers. Euler en avait trouvé
une : n² + n + 17 (valable pour n de 0 à 15). Il proposa une autre formule, n² - n + 41, qui, pour des valeurs successives de n
entre 0 et 40, ne produit que des nombres premiers. Par calcul sur ordinateur, on montra que la formule d'Euler n² - n + 41 était étonnamment bonne,
puisqu'elle engendre des nombres premiers inférieurs à dix millions dans 47,5 % des cas. Ulam trouva d'autres formules dont les pourcentages de succès étaient
presque aussi bons que pour celle d'Euler.
Le code ayant permis cette génération est le suivant. L'agorithme de parcours en spiral a été trouvé sur Internet (ici, même s'il faut un peu bidouiller pour que le code fonctionne).
drawUlanSpiralCanvas("#canvas3", 10000, 400, 400, 4, 4, "PRIME");
function drawUlanSpiralCanvas(canvasId, size, width, height, dx, dy, mode) {
var canvas = d3.select(canvasId).append("canvas")
.attr("width", width)
.attr("height", height);
var context = canvas.node().getContext("2d"),
dir = 0,
direct = [[1, 0], [0, -1], [-1, 0], [0, 1]],
moves = 0,
movesMax = 1,
alt = 0,
last = [ Math.floor(width / 2), Math.floor(height / 2)];
for (var i = 1; i < size; i++) {
if (mode === "DIVIDOR") {
context.fillStyle = "#3370d4";
context.beginPath();
context.arc(last[0], last[1], getDivisorsCount(i).length / 7, 0, Math.PI*2, true);
context.closePath();
context.fill();
}
else if (isPrime(i)) {
context.fillStyle = (mode === "DIVIDOR" ? "red" : colors[i % 10]);
context.fillRect(last[0], last[1], dx, dy);
}
if (moves === movesMax) {
moves = 0;
dir = (dir == direct.length - 1) ? 0 : dir + 1;
alt++;
}
if(alt === 2) {
alt = 0;
movesMax++;
}
moves++;
last[0] += direct[dir][0] * dx;
last[1] += direct[dir][1] * dy;
}
}Une autre façon de mettre en évidence des alignements obliques est de tracer au-dessus de chaque nombre, un cercle dont le rayon est proportionnel à son nombre de diviseurs avec le code suivant :
drawUlanSpiralCanvas("#canvas4", 10000, 600, 600, 6, 6, "DIVIDOR");Le code pour trouver les diviseurs en Javascript :
function getDivisors(i) {
var result = [];
if (i == 0) {
return result;
}
if (i <= 2) {
result.push(1);
return result;
}
for (var j = Math.floor(Math.sqrt(i)); j >= 1; j--) {
if (i % j == 0) {
result.push(j);
if (j != 1 && $.inArray(i/j, result) === -1) {
result.push(i/j);
}
}
}
return result;
}Cette spirale est une variante de la spirale d'Ulam inventée par Robert Sacks en 1994, les différences sont les suivantes (repris de Wikipedia) :
La visualisation ci-dessous permet clairement d'identifier les fonctions polynomiales génératrices d'un grand nombre de nombres premiers.
La plus dense est celle qui vient presque toucher le degré 165. Elle correspond à la fonction n² - n + 41 qui produit 58% de nombres premiers
entre 0 et 1 000 000.
Le code pour générer cette spiral est relativement simple :
function drawSacksSpiralCanvas(canvasId) {
const margin = 80,
spiralWidth = $("#container").width() - margin,
spiralHeight = $("#container").width() - margin,
spiralCenter = {x : spiralWidth / 2 + margin / 2, y : spiralHeight / 2 + margin / 2},
radius = spiralWidth / 2,
limit_prime = radius * radius;
// Création du canvas
var canvas = d3.select(canvasId).append("canvas")
.attr("width", spiralWidth + margin)
.attr("height", spiralHeight + margin)
.style("display", "block")
.style("margin", "auto")
.style("width", spiralWidth + margin + "px")
.style("height", spiralHeight + margin + "px");
var context = canvas.node().getContext("2d");
// Voir le code source pour la génération du cercle extérieur
// Voir le code source pour la génération des degrés
context.globalAlpha = 1;
for (var j = 0; j <= limit_prime; j++) {
let i = j + 1;
if (isPrime(j)) {
let r = Math.sqrt(i);
let theta = r * 2 * Math.PI;
let x = Math.cos(theta) * r + spiralCenter.x;
let y = -Math.sin(theta) * r + spiralCenter.y;
context.fillStyle = "#3370d4";
context.beginPath();
context.arc(x, y, 1, 0, Math.PI * 2);
context.fill();
}
}
}D3JS le permet, nous n'oublions pas d'ajouter un peu d'interactivité. Le graphique suivant permet de survoler chaque nombre jusque 2500 et de faire apparaître ses diviseurs.
En cliquant sur ce lien vous pourrez voir ce dessin se construire au fur et à mesure.
N'hésitez pas à prendre le code source et à le modifier pour aller plus loin, jusque 500 millions par exemple. Sachez juste que vous
devrez agrandir le canvas vers le bas, la droite et un peu vers le haut. Vous pouvez également modifier l'attribut step qui indique
le nombre de pixels qu'il faut parcourir dans chaque direction.
Il n'est pas évident de retenir quelquechose de ce dessin d'un point de vue mathématique. Parfois il évolue rapidement dans une direction indiquant un pic de 1,3,7 ou 9 mais globalement la répartition semble parfaitement aléatoire. Pour vous en convaincre le graphique suivant indique la répartion des nombres premiers jusque 1 milliard et il faut dire que ça ne pourrait pas être plus carré.
Voici le code servant à la génération de l'image qui est contenu dans un canvas. La fonction d3.timer() permet d'avoir l'animation et de visualiser la construction au fur et à mesure.
var width = 850,
height = 800;
var canvas = d3.select("#container").append("canvas")
.attr("width", width)
.attr("height", height)
.attr("class", "canvas");
var context = canvas.node().getContext("2d");
var limit = 100000000, // Limite à tester
x = 100, // Position X de départ
y = 200, // Position Y de départ
cur = 0, // Nombre courant (par pas de blocSize)
blocSize = 20000, // Les nombres premiers entre cur et cur + blocSize sont desssinés en une fois
step = 1; // Nombre de pixels à dessiner dans chaque direction
// Dessin de la légende (à voir dans le code source directement)...
context.globalAlpha = 0.1;
d3.timer(function() {
for (var j = cur; j < cur + blocSize && j < limit; j++) {
if (isPrime(j)) {
context.fillStyle = d3.hsl((j * 360 / limit) % 360, 1, .5) + "";
if (j % 10 === 1) {
context.fillRect(x, y - step, 1, step); // Vers le haut
y -= step;
} else if (j % 10 === 3) {
context.fillRect(x, y, step, 1); // Vers la droite
x += step;
} else if (j % 10 === 7) {
context.fillRect(x, y, 1, step); // Vers le bas
y += step;
} else if (j % 10 === 9) {
context.fillRect(x - step, y, step, 1); // Vers la gauche
x -= step;
}
}
}
if (cur >= limit) { // Condition d'arrêt de la fonction timer()
return true;
}
cur += blocSize;
});Nous venons de voir que la répartition des nombres premiers finissant par 1, 3, 7 ou 9 est quasiment identique. Des chercheurs viennent de découvrir (à la date du 13/03/2016) quelque chose d'assez étonnant. Ainsi lorsqu'un nombre premier finit par 1 le suivant à beaucoup moins de chance de finir par 1. C'est particulièrement déroutant car il faut peut-être passer plusieurs centaines de nombres avant de trouver le suivant. Voici le lien vers l'article (en anglais) : Mathematicians Discover Prime Conspiracy. Etonnament cette propriété n'avait jamais été découverte. Voici donc la répartition des nombres premiers qui suivent un autre nombre premier jusque 1 milliard.
Notre travail sur les nombres premiers s'achèvent ici (pour l'instant) en espérant qu'il vous ait inspiré. On trouve d'autres exemples sur Internet de visualisations (comme celle-ci) qui méritent le détour.
COMMENTAIRES