Nombres Premiers

Visualisation des nombres premiers

Dernière mise à jour le 23/06/2018
d3js3.x jquery3.2.1
Dernière mise à jour le 14/03/2016

Introduction

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).

Les nombres premiers inférieurs à 10000

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.

Les nombres premiers inférieurs à 1 million

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.

La distribution des nombres premiers

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

Approximation de π(x) par Gauss Limite de π(x)

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.

Limite de π(x) sur li(x) Calcul de li(x)

Spirale d'Ulam

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). Spiral 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;
}

Interactivité

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.

Les nombres premiers inférieurs à 100 millions

Revenons pour conclure à la réprésentation d'un grand ensemble de nombres premiers. L'image ci-dessous représente tous les nombres premiers inférieurs à 100 millions. Elle est construite de la façon suivante : Dessin des nombres premiers inférieurs à 100 millions

Voir le maître à l'oeuvre

Info: 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;
});

Quand les nombres premiers font dans la conspiration

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.

Si un nombre premier finit par 1, pour le suivant

Si un nombre premier finit par 3, pour le suivant

Si un nombre premier finit par 7, pour le suivant

Si un nombre premier finit par 9, pour le suivant

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.

A suivre : Fuite des données du site Ashley Madison Voir le tutoriel

comments powered by Disqus