Arithmétique en Python avec la Numworks

samedi 28 avril 2018
par  Alain BUSSER , Emmeric ÉTHÈVE

Dans cet article, on racontera comment a été créé ce script ; ce que font les fonctions qu’il contient ; et ce qu’on peut faire avec en classe. Et les herpétophobes pourront prendre l’R en annexe.

Programmation de la Numworks sans Numworks

Pourquoi donc ?

Le programme de Seconde recommande l’usage du clavier pour programmer (« programmation textuelle »). Le clavier des calculatrices étant nettement moins pratique que celui des ordinateurs, programmer en Python sur une calcularice est un véritable exploit pour qui a des doigts un peu gros, ou souffre de presbytie (quand ce n’est pas les deux). Pour remédier à ces problèmes, les calculatrices sont dotées de menus déroulants où on peut choisir des instructions ou blocs d’instructions tout faits [1], mais également de la possibilité de communiquer avec l’ordinateur, l’idée étant de programmer la calculatrice depuis l’ordinateur. À ma connaissance, la Numworks est la première calculatrice permettant de communiquer avec n’importe quel ordinateur (pas nécessairement du type Microsoft ou Mac) par le biais du logiciel Chrome, disponible sur toutes plateformes. Cela permet de programmer ses modules Python sur tout ordinateur, puis de les transférer vers la Numworks afin de les y utiliser. En respectant toutefois une limite de place : L’ensemble des modules Python ne doit pas occuper plus de 4096 octets. Ceci dit on peut aussi transférer et utiliser des modules Python créés par d’autres personnes (collègues, chercheurs, élèves). En voici quelques exemples.

Comment donc ?

S’il n’est pas nécessaire d’acheter une Numworks© ni un Windows© avec Edge©, deux prérequis sont nécessaires. Mais ils sont gratuits :

  1. le logiciel Chrome, à télécharger sans frais puis installer ;
  2. créer un compte sur le site Numworks. Le mien est ici

Une fois mon compte créé, pour programmer un module Python sur la Numworks, je n’ai plus qu’à cliquer sur « nouveau script » en bas de ma page d’accueil, et je me trouve alors sur une page comprenant un éditeur Python en ligne, à gauche, et un simulateur de Numworks à droite. En haut de ladite page, j’ai la possibilité de nommer mon script (ici, comme il s’agit des diviseurs d’un entier, j’ai choisi de l’appeler divisors.py ) et après avoir, pour une première fois, cliqué sur « sauvegarder », chaque fois que je relance ce simulateur (en cliquant sur « relancer ») il importe automatiquement le module en cours d’édition :

Ceci fait que chacune des fonctions que j’aurai créée dans le module pourra être utilisée dans la console (directement en mode interactif, dans la calculatrice). Par exemple, si on entre dans cette console, « gcd(12,16) », on a un message d’erreur parce que Python ne possède pas par défaut de fonction gcd (calculant le pgcd de deux entiers). Mais une fois le module divisors.py importé, comme celui-ci comprend une telle fonction, « gcd(12,16) » affiche 4.

Cette philosophie est très proche des recommandations de l’inspection générale : Il est pénible de créer une boucle dans la console, alors si on veut faire des choses compliquées, on les fait dans des définitions de fonctions (à l’intérieur du module) et on réserve les utilisations de fonctions (affichages par exemple) à la console.

repl

L’acronyme REPL signifie

  • Read (attendre une entrée par l’utilisateur)
  • Eval (évaluer ce qui a été entré, et qui est supposé être une expression)
  • Print (afficher sur la console le résultat de l’évaluation)
  • Loop (et recommencer le cycle R-E-P en boucle)

C’est ainsi que fonctionnent les consoles Python des calculatrices ou autres. Souvent on appelle cela « utiliser Python comme calculatrice » et l’utilité du repl pour apprendre un langage de programmation par essais et erreurs, est telle qu’un site internet y est consacré : repl.it lequel a évidemment sa version Python. Là encore, il est mieux d’avoir un compte, mais on peut programmer en ligne, avec un Python à la fois léger et puissant, sans problèmes d’installation donc.

Intersection de listes

Pour la suite on aura besoin de calculer l’intersection de deux listes l1 et l2. Une manière rapide est d’utiliser une compréhension de liste : La liste intersection est formée des éléments x de l1 qui sont aussi dans l2. En Python cela s’écrit :

  1. def inter(l1,l2):
  2.   return [x for x in l1 if x in l2]

Télécharger

intersection d’intervalles

Avec cette fonction, on peut explorer les objets range de Python, en calculant les intersections de tels objets :

Cela permet de vérifier expérimentalement la commutativité de l’intersection, mais aussi le sens de range et accessoirement, de constater que l’intersection de deux intervalles est toujours un intervalle, éventuellement vide.

Diviseurs et divisibilité

diviseurs

Pour calculer la liste des diviseurs d’un entier n, on part de 2 constatations :

  • La définition : « on dit que a est un diviseur de b (ou que b est un multiple de a) s’il n’y a aucun reste lorsqu’on divise euclidiennement a par b. Comme le reste euclidien de a par b se note a%b, en Python, le fait que a est divisible par b se note a%b==0 ;
  • Un diviseur de n ne peut pas être plus grand que n, donc les diviseurs potentiels de n ne sont à chercher que parmi les entiers entre 1 et n compris.

La liste des diviseurs de n peut donc se décrire en compréhension comme formée des entiers d entre 1et n tels que la division de n par ces entiers ne laisse aucun reste :

  1. def divisors(n):
  2.   return [d for d in range(1,n+1) if n%d==0]

Télécharger

En guise d’application, le script suivant (exécuté sur la Numworks, réelle ou virtuelle) permet de vérifier que le millésime 2017 était premier mais qu’il faudra attendre un peu avant d’avoir de nouveau une année « première ». Le script

for n in range(2017,2025): print(divisors(n))

produit l’effet suivant :

Arithmétique

Primalité

En affichant la liste des diviseurs de plusieurs entiers (voir ci-dessus de 2017 à 2024), on constate qu’aucun entier n’a moins que deux diviseurs (1 et l’entier lui-même) mais que certains entiers atteignent ce minimum. Les premiers d’entre eux étant 2, 3, 5, 7, 11, 13, 17 et 19. Cette propriété remarquable (avoir peu de diviseurs) justifie une définition : Un tel entier est appelé premier. Comme, en Python, le nombre de diviseurs est appelé longueur de la liste (abrégé len comme length), on propose alors ce test de primalité :

  1. def isPrime(n):
  2.   return len(divisors(n))==2

Télécharger

Remarque : Ce test de primalité (traduction directe de la définition en Python) n’est pas le meilleur, en terme d’efficacité, qui soit. On qualifie en général de naïf un tel algorithme. La recherche de tests de primalité efficaces est un domaine assez pointu des mathématiques, toujours en développement. On pense notamment à Derrick Lehmer...

On peut alors s’intéresse au nombre pi(n) de nombres premiers inférieurs à n (répartition des nombres premiers), avec ce préambule

  1. from kandinsky import *

et ces rajouts au script

  1. def pi(n):
  2.   return [isPrime(k) for k in range(2,n+1)].count(True)
  3. def courbe():
  4.   for x in range(2,320):
  5.     set_pixel(x,200-pi(x),color(0,0,255))

Télécharger

Il faut ...un certain temps, à la Numworks, pour dessiner la répartition :

Perfection et amitié

Python possédant une fonction sum, il est très facile de définir la fonction « somme des diviseurs » en appelant sum(divisors(n)). L’affichage de telles sommes permet de constater (avant preuve) que

  • la somme des diviseurs de n est au minimum n+1 (minimum obtenu pour n premier)
  • par conséquent la somme est toujours supérieure à n.
  • Mais elle peut être
    • inférieure à 2n (nombre déficient)
    • égale à 2n (nombre parfait)
    • supérieure à 2n (nombre abondant).

D’où le test de perfection suivant :

  1. def isPerfect(n):
  2.   return sum(divisors(n))==2*n

Télécharger

Si on incorpore le test dans le script divisors.py, on peut chercher les nombres parfaits inférieurs à 1000 en entrant successivement

  1. l = [n for n in range(2,1000) if isPerfect(n)]
  2. print(l)

Télécharger

Ce qui affiche que seuls trois nombres inférieurs à 1000 sont parfaits :

Autre définition : On dit que a et b sont amicaux si sum(divisors(a))=a+b et sum(divisors(b))=a+b aussi. Cette notion aussi peut être explorée expérimentalement avec le script divisors.py

pgcd

Puisqu’on dispose maintenant de la liste des diviseurs et de l’intersection, on peut assez naturellement envisager de parler de diviseurs communs à deux entiers :

  1. def cd(a,b):
  2.   return inter(divisors(a),divisors(b))

Télécharger

Cela permet de parler de plusieurs notions :

  1. nombres premiers entre eux
  2. probabilité que deux nombres soient premiers entre eux
  3. pgcd

Il arrive assez souvent que deux entiers n’aient qu’un diviseur commun (le nombre 1). En ce cas on les dit premiers entre eux. Ce qui suggère une nouvelle fonction pee (comme « premiers entre eux ») :

  1. def pee(a,b):
  2.   return len(cd(a,b))==1

Télécharger

Avec le préambule

  1. from kandinsky import *
  2. from random import *

Télécharger

et l’affichage

  1. def premiers():
  2.   s,t = 0,0
  3.   for x in range(320):
  4.     t += 1
  5.     if pee(randint(2,1001),randint(2,1001)):
  6.       s += 1
  7.     set_pixel(x,200-int(200*s/t),color(255,0,0))

Télécharger

le code premiers() produit ce genre d’affichage, montrant une stabilisation vers la « probabilité que deux nombres soient premiers entre eux » :

Au fait quelle est cette probabilité ?

Enfin, afficher de grands nombres d’exemples d’appels à la fonction cd montre que les diviseurs communs à a et b sont les diviseurs d’un nombre qui est le plus grand de la liste cd(a,b). Le plus grand (« greatest ») des diviseurs communs peut donc être défini par cette fonction :

  1. def gcd(a,b):
  2.   return max(cd(a,b))

Télécharger

Là encore il s’agit d’une simple traduction en Python de la définition « le pgcd de a et b est le plus grand des diviseurs communs à a et b » et peut donc être qualifié d’algorithme « naïf » de calcul du pgcd. L’algorithme d’Euclide est nettement plus efficace par exemple.

Conclusion

L’idée de programmer des fonctions Python dans un (ou plusieurs) module vu comme une collection d’algorithmes, et de n’aller dans la console (en mode repl) que pour utiliser ces fonctions (affichage de valeurs) rend la Numworks très conforme à l’esprit du programme de mathématiques du lycée. De plus, la limite de 4096 octets au total incite à produire du code court et concis, avec des fonctions imbriquées, ce qui permet de se concentrer sur l’algorithme et non les détails n’en faisant pas partie comme les subtilités de matplotlib et autres tkinter. Et l’occasion est belle de découvrir les listes en compréhension, chères aux mathématiciens [2]. On ne peut alors qu’espérer que Casio, au hasard, permette également une programmation Python de sa calculatrice, qui soit accessible à tout le monde et pas seulement aux victimes de Gafam...


Annexes

La version R

On remarque que R est par défaut en mode « repl » (pas besoin de print pour afficher la valeur d’une expression) et qu’il n’est pas nécessaire d’y définir l’intersection de listes, puisque celle-ci existe déjà :

  1. library(ggplot2)
  2.  
  3. divisors<-function(n){
  4.    l<-seq(1:n)
  5.    return(l[ n%%l ==0 ])
  6. }
  7.  
  8. isPrime<-function(n){
  9.    return( length(divisors(n)) == 2)
  10. }
  11.  
  12. pi<-function(n){
  13.    l<-seq(1:n)
  14.    return(sum(sapply(l,isPrime)))
  15. }
  16.  
  17. courbePi<-function(n){
  18.    x<-seq(1:n)
  19.    y<-sapply(x,pi)
  20.    df<-data.frame(x,y)
  21.    graphe<-ggplot(df, aes(x,y))
  22.    graphe+geom_point(aes(colour=y))+scale_color_gradient(low="green", high="red")
  23. }
  24.  
  25. isPerfect<-function(n){
  26.     return( sum(divisors(n)) == 2*n)  
  27. }
  28.  
  29. parfaitInf<-function(n){
  30.    l<-seq(1:n)
  31.    return(Filter(isPerfect,l))
  32. }
  33.  
  34. cd<-function(n,p){
  35.    return( intersect( divisors(n),divisors(p) ) )
  36. }
  37. gcd<-function(a,b){
  38.    return(max(cd(a,b)))
  39. }
  40.  
  41. #Tests
  42. divisors(15)
  43. isPrime(15)
  44. pi(15)
  45. courbePi(1000)
  46. isPerfect(3)
  47. parfaitInf(100)
  48. intersect(seq(1:10),c(2,5))
  49. cd(20,15)
  50. gcd(20,15)

Télécharger

Le script ci-dessus peut être exécuté sans installation de R, par exemple en le copiant-collant sur ce site. Ce qui produit, pour la partie sur la représentation graphique de la fonction de compte des nombres premiers, ceci :

La version haskell

Le langage haskell est célèbre pour ses compréhensions, et donc parfaitement adapté à la présente activité. Voici le source :

  1. import Data.List
  2.  
  3. diviseurs n = [d | d <- [1..n], n `mod` d == 0]
  4. isPrime n = length (diviseurs n) == 2
  5. isPerfect n = sum (diviseurs n) == 2*n
  6. cd a b = (diviseurs a) `intersect` (diviseurs b)
  7. pgcd a b = maximum (cd a b)
  8.  
  9. cm a b = [m | m <- [1..], m `mod` a == 0, m `mod` b == 0]
  10. ppcm a b = head (cm a b)

Télécharger

Et quelques exemples d’utilisation :

  1. > [n | n <- [1..100], isPrime n]
  2. [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

Télécharger

  1. > pgcd 24 36
  2. 12

Télécharger

  1. > [n | n <- [6..1000], isPerfect n]
  2. [6,28,496]

Télécharger

Le module divisors.py

Voici l’intégralité du code du module :

  1. def inter(l1,l2):
  2.   return [x for x in l1 if x in l2]
  3. def divisors(n):
  4.   return [d for d in range(1,n+1) if n%d==0]
  5. def isPrime(n):
  6.   return len(divisors(n))==2
  7. def cd(a,b):
  8.   return inter(divisors(a),divisors(b))
  9. def gcd(a,b):
  10.   return max(cd(a,b))

Télécharger

On peut s’en servir dans toute distribution Python, pas nécessairement celle de la Numworks.

Le vrai algorithme du vrai Euclide

Malgré le lien entre Euclide et la division euclidienne, le premier n’utilisait pas la seconde pour calculer un pgcd, mais des soustractions, avec cet algorithme :

  1. def pgcd(a,b):
  2.         while a!=b:
  3.                 a,b = max(a,b)-min(a,b),min(a,b)
  4.         return a

Télécharger

L’activité présentée ici est maintenant disponible parmi les activités Numworks :

Les deux documents sont téléchargeables au format pdf sur le site Numworks, dans les pages ci-dessus.


[1Ces menus sont très similaires à la console JavaScript de CaRMetal, à part qu’on y navigue avec le clavier de la calculatrice, CaRMetal faisant usage de la souris. On peut aussi faire l’analogie avec les blocs de la programmation visuelle, dans l’économie de clavier que ces outils permettent.

[2mais apparemment pas aux informaticiens...


Commentaires