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 :

HTML - 20.9 ko
exercice de comptage
pour enfants de CP

Cet exercice vise le niveau CP.


Puis un exercice de classement selon la parité :

HTML - 2.4 ko
classement par parité
les nombres sont donnés sous forme décimale, et calculés aléatoirement

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

HTML - 2.4 ko
classement par parité
cette fois-ci ce sont des expressions qu’il faut classer

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 :

HTML - 2.7 ko
classement par primalité
l’usage d’une calculatrice est conseillé, pour tester certaines divisibilités

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 :

HTML - 4 ko
système conguentiel

Commentaires

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

- Mercredi 14 juin 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mercredi 21 juin 2017, 14h-18h, 146 route de Grand-Coude, Saint-Joseph


Brèves

Décès de Roger Mohr

mardi 27 juin

On sait bien que Nicolas Bourbaki n’était pas le nom d’une personne mais le pseudonyme d’un groupe. L’équivalent en informatique théorique est Claude Livercy, auteur de la théorie des programmes. Roger Mohr était un des membres de Claude Livercy.

À travers les labyrinthes : algorithmes et fourmis

dimanche 1er septembre 2013

Quand les chercheurs mettent au point des modèles d’optimisation et de recherche de plus court chemin qui s’inspirent du comportement de masse de colonies de fourmis...
À écouter : Sur les Épaules de Darwin, émission diffusée sur France Inter samedi 31 août 2013.

Rencontres Mondiales du Logiciel Libre à St-Joseph

mardi 20 août 2013

Les RMLLd se dérouleront pour la 2e fois à Saint-Joseph du 22 au 25 août.
C’est une opportunité pour les élèves qui suivent la spécialité ISN et les passionnés d’informatique.

Voici pour le samedi et le dimanche quelques interventions choisies :
- http://2013.d.rmll.info/Raspberry-votre-ordinateur-au-format-carte-de-credit?lang=fr
- http://2013.d.rmll.info/Materiel-libre-et-DIY?lang=fr
- http://2013.d.rmll.info/Arduino-de-l-electronique-libre?lang=fr

Noter aussi les conférences Art et Culture du dimanche, ainsi qu’une conférence plus engagée.

Le programme complet se trouve ici. Une radio sera ouverte pour l’occasion.
Des plaquettes à distribuer se trouvent ici.

Hyper-vidéos pour l’algorithmique au lycée

dimanche 19 août 2012

Olivier Roizès, à la demande de l’ADIREM, a réalisé une collection d’hyper-vidéos de présentation de logiciels et environnements de programmation. Ces hyper-vidéos, c’est-à-dire des vidéos contenant des éléments clicables, devraient être utiles aux enseignants désireux de se familiariser avec Python, CaRMetal, R, Rurple, Scilab ou Xcas.

Ouverture du SILO

mardi 1er novembre 2011

Le SILO (Science Informatique au Lycée : Oui !) est un espace collaboratif documentaire de partage et de formation collégiale, à destination des professeurs appelés à enseigner l’informatique au lycée.

Une initiative du CNDP, de l’INRIA et de Pasc@line, à laquelle se sont associés SPECIF, fuscia, EPI et ePrep.

Sur le Web : Site du SILO

Introduction à la science informatique

lundi 12 septembre 2011

Le CRDP de Paris publie le premier ouvrage destiné aux professeurs chargés d’enseigner la nouvelle spécialité « Informatique et sciences du numérique » en Terminale S à la rentrée 2012. Cet ouvrage a été coordonné par Gilles Dowek, directeur de recherche à l’INRIA.

Sur la création de la spécialité ISN, on pourra également consulter l’interview donnée au Café pédagogique par l’inspecteur général Robert Cabanne.

Sur le Web : CRDP de Paris

Deux publications sur l’algorithmique

samedi 17 octobre 2009

L’IREM d’Aix-Marseille publie une brochure de 73 pages, téléchargeable librement, intitulée Algorithmes et logique au lycée. Ces notions sont illustrées et déclinées sur des exercices du programme de spécialité mathématique en série L, mais sont adaptables aux programmes à venir.

Le hors série thématique n° 37 du magazine Tangente, disponible actuellement en kiosque, s’intitule « Les algorithmes. Au cœur du raisonnement structuré ». Extrait de l’éditorial : « La rédaction de Tangente a conçu la quasi-totalité de ce hors série thématique pour qu’il puisse être lu par des élèves de Seconde ».

Une carte mentale pour l’algorithmique

jeudi 10 septembre 2009

Sur son site, Jean-Jacques Dhénin a publié une carte mentale géante qui renvoie vers plus de 30 documents en ligne sur l’algorithmique. Tout ce qu’il faut — et même davantage — pour faire face au nouveau programme de Seconde !

Un catalogue libre d’algorithmes pour le lycée

dimanche 30 août 2009

Guillaume Connan, de l’IREM de Nantes, publie un catalogue libre de 119 pages d’algorithmes pour le lycée. Sur son site très riche, on trouvera d’autres documents en rapport avec l’algorithmique, notamment sur l’utilisation des langages fonctionnels au lycée et sur la comparaison programmation fonctionnelle/programmation impérative.

L’algorithmique à l’IREM de Lille

vendredi 26 juin 2009

Le groupe AMECMI de l’IREM de Lille vient de mettre en ligne des ressources importantes au service des professeurs de Seconde :

- Algorithmique et programmation (Emmanuel Ostenne)
- Bibliographie amoureuse de l’algorithmique (Alain Juhel)

Statistiques

Dernière mise à jour

mercredi 9 août 2017

Publication

760 Articles
Aucun album photo
133 Brèves
11 Sites Web
132 Auteurs

Visites

413 aujourd'hui
385 hier
2073862 depuis le début
5 visiteurs actuellement connectés