Petits exerciciels d’arithmétique

lundi 26 mai 2014
par  Alain BUSSER , Florian TOBÉ

On peut classer des nombres entiers selon des catégories de nature arithmétique :

  • nombres pairs et impairs
  • nombres premiers et composés
  • résidus quadratiques ou non modulo un nombre donné
  • nombres parfaits, abondants ou déficients
  • nombres de Fibonacci ou non...

Quelques exemples en sont donnés ci-dessous.

Pour commencer, un exercice de dénombrement : Il s’agit de mettre un certain nombre d’objets dans un sac opaque :

exercice de comptage
pour enfants de CP
Alain Busser, Florian Tobé 2014

Cet exercice vise le niveau CP.

Puis un exercice de classement selon la parité :

classement par parité
les nombres sont donnés sous forme décimale, et calculés aléatoirement
Alain Busser, Florian Tobé 2014

Un autre, où les nombres doivent être calculés avant de les classer :

classement par parité
cette fois-ci ce sont des expressions qu’il faut classer
Alain Busser, Florian Tobé 2014

Théorie de ces exerciciels

Le fait qu’il est toujours possible (par un algorithme comme regarder si son dernier chiffre est 0, 2, 4, 6 ou 8) de savoir si un nombre est pair, s’exprime en disant que l’ensemble des nombres pairs est récursivement énumérable. Si, de plus, son complémentaire est aussi récursivement énumérable, on dit que l’ensemble des nombres pairs est un ensemble récursif. C’est le cas, parce qu’une caractérisation des ensembles récursivement énumérables est que leur fonction caractéristique est calculable par algorithme. Or

  • La fonction caractéristique des nombres pairs est 1-x%2
  • et celle des nombres impairs est x%2

Elles sont donc toutes deux calculables puisque chacune d’entre elles correspond au dernier chiffre binaire de x.

Ainsi, le fait que l’ensemble des nombres pairs est récursivement énumérable, signifie qu’il est toujours possible en un temps fini, de remplir correctement le sac de gauche. Le fait qu’il est également possible en un temps fini de remplir correctement le sac de droite, revient à dire que l’ensemble des nombres pairs est récursif. En fait, les deux notions ne sont pas équivalentes, quoique tous les ensembles finis soient récursifs. Moins évident, il en est de même pour les nombres premiers et les nombres de Fibonacci.

Le théorème de Matiiassevitch dit qu’un ensemble d’entiers est récursivement énumérable si et seulement s’il est l’ensemble des solutions d’une équation diophantienne. Trouver une telle équation pour les nombres de Fibonacci ou pour les nombres premiers, est loin d’être facile. Mais pour les nombres pairs ?

Exercice : Trouver un polynôme P(x) ne prenant que des valeurs paires pour tout x entier relatif.

Enfin un exercice où le classement se fait entre nombres premiers et nombres composés :

classement par primalité
l’usage d’une calculatrice est conseillé, pour tester certaines divisibilités
Alain Busser, Florian Tobé 2014

Une remarque probabiliste à propos de celui-ci : Il arrive assez fréquemment que l’ensemble des nombres premiers soit plus gros que celui des nombres composés, alors qu’il n’y a que 46 nombres premiers sur les 200 choisis au hasard. Mais en fait, les nombres ne sont choisis au hasard que parmi les nombres impairs de 3 à 201, et du coup la probabilité de tomber sur un nombre premier en choisissant un nombre au hasard est 0,45. Le nombre de nombres premiers dans l’exerciciel suit donc une loi binomiale de paramètres 10 et 0,45. La probabilité que plus de la moitié des nombres de l’exerciciel soit premiers est donc environ 0,2616 qui n’est pas si négligeable. Voici la loi suivie par le nombre de nombres premiers de l’exercice :

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

Pour savoir si un nombre est premier, un moyen rapide est de regarder s’il est dans le tableau des nombres premiers :

$("#premiers div").each (x) ->
	if eval($(this).text()) in crible then n++
$("#composés div").each (x) ->
	if eval($(this).text()) not in crible then n++

Cet algorithme est très rapide mais évidemment à condition d’avoir le tableau des nombres premiers sous la main. Il s’appelle crible parce qu’il est calculé au démarrage par la méthode d’Eratosthène :

crible = [2..200]
for diviseur in [2..20]
    crible = (x for x in crible when x<=diviseur or x%diviseur isnt 0)

Enfin, pour finir, un exercice de type Rallye mathématique basé sur le théorème des restes chinois :

système conguentiel
Alain Busser 2014

Documents joints

PDF - 80.7 kio

Commentaires