Interlude
Rien que pour le plaisir, voici quelques exercices mathématiques. On pourra en imaginer beaucoup d'autres. Et n'hésitez pas à nous les proposer via l'onglet Contact.
Calcul de la racine carrée de 2
Pour calculer la racine carrée de 2, on peut simplement procéder par des encadrements "naïfs" successifs de plus en plus rapprochés.
On part de l'intervalle [1, 2] dans lequel on sait que se trouve la racine carrée de 2. Car, en effet, 1² = 1 est inférieur à 2 tandis que 2² = 4 est supérieur à 2.
On prend ensuite le milieu de l'intervalle = 1,5, Or, 1.5² = 2.25 est supérieur à 2. On passe donc à l'intervalle [1, 1.5]. Etc.
La fonction rac2 ci-contre qui procède ainsi montre qu'il faut une 50aine d'itérations pour trouver 15 décimales.
La méthode de Newton consiste à calculer les valeurs successives de la suite dans laquelle un terme est obtenu à partir du terme précédent x en faisant la moyenne de x et de 2/x. Ecrit autrement, on a : x(i+1) = (x(i) + 2/x(i)) / 2
La nouvelle fonction rac2newton que nous avons définie converge beaucoup plus rapidement puisque dès la 5ème itération, on obtient le même résultat.
rac2 (N:int);
var a = 1;
var b = 2;
for var i = 1 to N do
var c=(a+b)/2;
write i ++ ": " ++ c;
if c*c<2 then a = c else b = c fi
done
rac2newton (N:int);
var x = 2;
for var i=1 to N do
x = (x + 2/x)/2;
write i ++ ": " ++ x
done
Calcul des nombres entiers a, b et c tels que a² + b² = c²
On connaît bien cette égalité qui, d'après le théorème de Pythagore, caractérise les triangles rectangles où le carré de la longueur de l'hypoténuse (c) est égal à la somme des carrés des longueurs des deux autres côtés (a et b).
L'égalité 3² + 4² = 5² est un cas particulier où les 3 longueurs (a, b et c) sont des nombres entiers. Elle est assez pratique pour dessiner un beau triangle rectangle sur une feuille à carreaux.
Mais y a-t-il beaucoup de tels triplets d'entiers (a, b, c) qui respectent cette propriété ?
Pour le savoir, rien de plus simple ! Il suffit d'écrire un programme.
Avant de vous laisser chercher, rappelons ces quelques points de langage :
- a² peut être calculé simplement en écrivant a*a ou a**2 (** est l'opérateur de puissance),
- Math.sqrt(c) fournit la racine carrée de c (généralement non entière),
- Math.round(p) donne le nombre entier le plus proche de p.
A noter, en important le module Math dans le module courant grâce à la commande : import Math
on peut écrire ces appels sans préciser leur module : sqrt(c) et round(p)
A vous de jouer, maintenant ! Ensuite, vous pourrez lire ce qui suit...
Dans un 1er temps, on peut calculer tous les couples (a, b) tels que a<b et b inférieur à un seuil N, la somme des carrés a² + b² et vérifier si c'est un carré.
Voir ci-contre, la définition de cette procédure que nous avons appelée pythagore.
En faisant tourner notre petit programme, on s'aperçoit qu'on a tout de même un bon nombre de solutions : 63 avec des valeurs de a et b inférieures à 100 !
En réalité, ce n'est pas si étonnant qu'il y ait pas mal de solutions car il suffit de multiplier a et b par un facteur (supérieur à 1) pour trouver une autre solution. Exemple : 6² + 8² = 10² , 9² + 12² = 15² , 12² + 16² = 20² etc. découlent directement de 3² + 4² = 5².
Alors, modifions notre procédure pour ne garder que les solutions qui ne sont pas multiples d'une autre. Pour cela, on pourra utiliser la fonction pgcd définie précédemment ainsi que l'opérateur '&&' de conjonction de deux conditions (le "et").
On n'obtient alors plus que 18 solutions pour des valeurs de a et b inférieures à 100. Mais c'est probablement encore plus que ce que l'on pouvait penser au départ !
Remarque : dans notre solution, nous vérifions que c est un nombre entier par la condition round(c)==c. Avec notre programmatrice, cela fonctionne bien mais il faut savoir que ça ne sera pas nécessairement le cas dans tous les langages. En effet, la fonction sqrt donne un résultat qui n'est pas nécessairement entier et, dans certains langages, même si le résultat doit être normalement un entier, il est possible qu'on obtienne un nombre approché non strictement égal (par exemple : 2.0000000001 pour la racine carrée de 4).
Alors pour être vraiment sûr de l'égalité, on utilisera plutôt une condition comme round(c)**2 == a*a + b*b
pythagore (N:int);
var c;
for var a=1 to N-1 do
for var b=a to N do
c = Math.sqrt(a*a+b*b);
if Math.round(c) == c then
write a++" "++b++" "++c
fi
done
done
pythagore (N:int);
var c;
for var a=1 to N-1 do
for var b=a to N do
c = Math.sqrt(a*a+b*b);
if (Math.round(c)==c) && (pgcd(a,b)==1) then
write a++" "++b++" "++c
fi
done
done
Nombres parfaits et amis
Un nombre entier naturel est dit parfait si somme de ses diviseurs stricts (c'est-à-dire lui exclu) est égale à lui-même. Par exemple, 6 est un nombre parfait car 1 + 2 + 3 = 6.
Nous nous proposons de rechercher tous les nombres parfaits jusqu'à un certain seuil.
Pour commencer, nous définissons une fonction calculant la somme des diviseurs d'un nombre N.
Dans une 1ère version, nous parcourons tous les nombres de 2 à N-1 à la recherche des diviseurs et nous ajoutons chaque diviseur trouvé (pour lequel le reste de la division est 0).
A noter que le résultat est initialisé à 1 car 1 est nécessairement un diviseur.
Dans une 2nde version optimisée, on stoppe la recherche des diviseurs à la racine carrée de N et, pour chaque diviseur d trouvé, on ajoute également le diviseur associé N/d à moins que celui-ci soit égal à d (dans le cas où N = d²).
Maintenant, trouver les nombres parfaits est facile. Voir la définition ci-contre.
Il ne nous reste plus qu'à exécuter notre procédure pour constater que les nombres parfaits ne sont pas nombreux. En dessous de 10000, on ne trouve que 6, 28, 496 et 8128.
Et ne cherchez pas à trouver le suivant qui est... 33550336, la programmatrice n'arriverait sans doute pas au bout de ce calcul !
Néanmoins, on peut vérifier que ce nombre est bien égal à la somme de ces diviseurs.
Passons maintenant aux nombres amis.
Deux nombres sont dits amis si la somme des diviseurs stricts de l’un est égale à l’autre et réciproquement.
En essayant la solution proposée ci-contre, vous remarquerez que les nombres amis sont guère plus nombreux que les nombres parfaits.
sommediviseurs (N:int):int
var res=1;
for var i=2 to N-1 do
if N%i == 0 then
res += i
fi
done;
res
sommediviseurs (N:int):int
var res=1;
for var i=2 to Math.round(Math.sqrt(N)) do
if N%i == 0 then
res += i;
if i*i < N then
res += N//i
fi
fi
done;
res
nombresparfaits (N:int);
for var i=2 to N do
if sommediviseurs(i)==i then
write i
fi
done
nombresamis (N:int);
var j=0;
for var i=2 to N do
var j = sommediviseurs(i);
if i != j && i==sommediviseurs(j) then
write j ++ " et " ++ i ++ " sont amis"
fi
done