En 2014, point de carré

Une nouvelle année commence… Que nous réserve 2014 ? Sera-t-elle une année intéressante ? Bien entendu, quand je dis « intéressante », c’est d’un point de vue mathématique car je n’ai (malheureusement) toujours pas de méthode pour prédire l’avenir (mais j’y travaille, je prévois d’ailleurs bientôt le lancement de blogdenumérologie).

Avec ou sans carré ?

La décomposition en produits de facteurs premiers de 2014 est:

2014 = 2 \times 19 \times 53

donc l’année 2014 s’écrit comme le produit de (trois) nombres premiers. On appelle cela un nombre sans facteur carré. L’année 2014 sera donc une année sans facteur carré (ou ne sera pas). Youpi !

« Mais au fait pourquoi il nous parle de carrés l’autre ? ». Reprenons. Par définition, un nombre sans facteur carré est un nombre qui n’est pas divisible par un carré, c’est-à-dire par un nombre (autre que 0 et 1) qui est de la forme k^2 . Un nombre sans facteur carré est donc un nombre qui n’est pas divisible par 4, 9, 16, 25, 36… vous avez compris. Mais quel est le rapport avec la décomposition en produits de facteurs premiers ? Si un nombre est sans facteur carré, alors, en particulier, il n’est divisible par aucun nombre premier au carré. Ainsi, sa décomposition en produits de facteurs premiers ne contient aucun nombre premier qui est à une puissance égale à 2 ou plus: sa décomposition est donc un simple produit de nombres premiers distincts (et réciproquement, si un nombre est un produit de nombres premiers, il n’est pas divisible par un carré).

  • Exemple 1: 14 est un nombre sans facteur carré car 14 = 2 \times 7.
  • Exemple 2: le nombre 192 se décompose en 192 = 2^6 \times 3. Le nombre 2 apparaît à la puissance 6, et en particulier, 192 = 2^2 \times 2^4 \times 3 est divisible par 2^2=4. Il n’est donc pas sans facteur carré. On dira plus simplement qu’il est avec facteur carré.

2014 sera-t-elle exceptionnelle ?

Bon, 2014 est sans facteur carré, c’est bien beau, mais, est-ce que ça arrive souvent qu’une année soit sans facteur carré ? Ou bien 2014 est une rareté ? Y a-t-il eu beaucoup d’années sans facteur carré avant 2014 ? Voilà les questions essentielles auxquelles nous allons répondre dans cet article…

Avant ça, il nous faudrait un petit test simple pour savoir si un nombre est sans/avec facteur carré. Un truc qui simplifierait leur recherche. Une condition nécessaire quoi… Heureusement, le Père Noël avait ça en stock le 25 Décembre dernier ! La voici cette condition nécessaire:

Si n>1 est un entier avec facteur carré, alors il existe un nombre premier p inférieur ou égal à \sqrt{n} tel que p^2 divise n.

Cette petite propriété (facile à prouver) possède une double utilité:

1) Si un nombre est sans facteur carré, elle permet (par contraposée) de l’affirmer à coup sûr. Par exemple, si on souhaite montrer que 35 est sans facteur carré, on ferait le petit raisonnement suivant:

  • \sqrt{35} \simeq 5,91...
  • Les nombres premiers inférieurs à 5,91 sont 2, 3, 5.
  • Leurs carrés sont 4, 9 et 25.
  • Ni 4, ni 9, ni 25 ne divisent 35.
  • Donc, par contraposée de la petite propriété, 35 ne peut pas être un nombre avec facteur carré !

Remarque: on sait bien que 35=5\times 7 et qu’il est donc sans facteur carré, alors pourquoi s’emm… avec cette méthode ? La réponse est simple: si au lieu de 35 j’avais pris un très grand nombre, trouver sa factorisation en produit de facteurs premiers peut être long et difficile…

2) Elle permet de donner une méthode pour trouver tous les nombres avec facteur carré qui sont inférieurs ou égaux à un nombre donné. C’est que nous appellerons la méthode du crible, qui se base sur le fait que les nombres avec facteur carré inférieurs ou égaux à n sont les multiples de p_1^2, p_2^2, …, p_k^2 pour tous les nombres premiers p_i inférieurs à \sqrt{n}.

Pour mieux comprendre, décrivons cette méthode sur un exemple. Au hasard, je choisis le nombre 40. Pourquoi 40 ? Parce qu’il paraît que tout le monde s’en tamponne de l’an 40. Et bien pour une fois, on ne va pas s’en tamponner ! Alors, combien y a-t-il eu d’années sans facteur carré entre l’an 1 et l’an 40 ?

Pour compter le nombre d’entiers compris entre 1 et 40 qui sont sans facteur carré, on commence par compter le nombre d’entiers qui sont avec facteur carré et on fait « 40 moins le résultat » (astuce de ouf!). Comme \sqrt{40} \simeq 6,32... , et comme 2, 3 et 5 sont les seuls nombres premiers inférieurs à 6,32, alors un nombre inférieur ou égal à 40 est avec facteur carré si, et seulement s’il est divisible par 4, 9 ou 25. Faisons la liste:

  • Multiples de 4 inférieurs ou égaux à 40: 4, 8, 12, 16, 20, 24, 28, 32, 36, 40
  • Multiples de 9 inférieurs ou égaux à 40: 9, 18, 27,  36
  • Multiples de 25 inférieurs ou égaux à 40: 25

Comme vous le constatez, il se peut que certains entiers soient comptés plusieurs fois (ici, 36). Faisons un petit diagramme de Venn pour visualiser ça:

Diagramme_de_Venn_pour_40

Le nombre d’entiers avec facteur carré est donc de 14 (l’union des trois patates). Une façon plus mathématique d’utiliser ce diagramme est la suivante: si on note A_4 l’ensemble des multiples de 4, A_9 l’ensemble des multiples de 9 et A_{25} l’ensemble des multiples de 25 alors le nombre d’entiers avec facteur carré est donné par la formule du crible de Poincaré (appelé principe d’inclusion/exclusion):avec_facteur_carre_40Donc le nombre d’entiers sans facteurs carrés inférieurs ou égaux à 40 est 40-14=26 !

2014 passée au crible

Revenons au cas de 2014, et sur le même principe que précédemment, comptons le nombre d’années sans facteur carré qu’il y a eu depuis l’an 1. Comme \sqrt{2014} \simeq 44,87 , et comme les nombres premiers inférieurs à 44,87 sont 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41 et 43, les années avec facteur carré seront les multiples de 4, 9, 25, 49, 121, 169, 289, 361, 529, 841, 961, 1369, 1681 et 1849. Cela fait beaucoup, donc on ne va pas faire de (champ de) patates mais un décompte à l’aide de la méthode du crible. Pour ne pas trop alourdir cet article (qui est assez dense déjà), j’ai mis tout ça dans le fichier ci-dessous:

Dénombrement des nombres sans facteur carré inférieurs ou égaux à 2014

Nous avons donc 790 nombres avec facteur carré inférieurs ou égaux à 2014. Il y a ainsi eu 2014-790 =1224 années sans facteur carré avant 2014 (inclus) ! Si on fait une proportion, cela fait \dfrac{1224}{2014} \times 100 \simeq 60,77 \% des années qui étaient sans facteur carré depuis l’an 1. La majorité des années étaient sans facteur carré: 2014 n’a donc rien d’exceptionnel. Quelle déception…

Raréfaction ?

On peut se demander si la proportion d’années sans facteur carré va augmenter ou diminuer à l’avenir. Y aura-t-il eu une proportion moins importante d’années sans facteur carré en l’an 10 000 ? Et en l’an 1 000 000 ?

Pour ne pas refaire le dénombrement un peu long que nous avons fait pour 2014 (mais dénombrement très utile !), j’ai écrit un petit programme (sous-optimal) en Python qui compte le nombre d’années sans facteur carré:

Calcul du nombre d’entiers sans facteur carré

Voici le résultat:

\begin{array}{c|c|c}  \text{ann\'ee} & \text{Nb d'ann\'ees sans facteur carr\'e} & \text{proportion} \\  100 & 61 & 0,61 \\  500 & 306 & 0,612 \\  1000 & 608 & 0,608 \\  2014 & 1224 & 0,60775 \\  3000 & 1824 & 0,608 \\  4000 & 2433 & 0,60825 \\  5000 & 3042 & 0,6084 \\  7500 & 4561 & 0,60813 \\  10000 & 6083 & 0,6083 \\  25000 & 15197 & 0,60788 \\  50000 & 30401 & 0,60802 \\  \end{array}

Hum… Etrange. Une certaine proportion semble se dégager. Et si on allait au-délà pour s’en assurer ? Est-ce qu’en l’an 1 000 000, cette proportion sera encore la même (environ 0,6) ? Pour le savoir, il faudrait pousser les calculs plus loin mais, déjà que mon petit programme a mis un peu de temps pour aller jusque 50 000, alors pour 1 000 000, il m’aurait fallu le faire tourner des jours et des jours… Plutôt que d’essayer d’optimiser mon programme (je ne suis pas programmeur voyons, je fais des mathématiques, le fait de savoir que ça marche me suffit !), je me suis dit qu’on pourrait faire une petite estimation probabiliste, à la manière des sondages…

Sondage exclusif IFOP/CSA/OpinionWay/TNS-Sofres (non biaisé)

On va estimer le nombre m de nombres sans facteur carré compris entre 1 et 1 000 000. L’idée est la suivante: si on tire un nombre au hasard entre 1 et 1 000 000, il a une probabilité p:=\frac{m}{1 000 000} d’être sans facteur carré. Si on répète plusieurs fois de suite ce tirage, on est alors en présence d’une loi binomiale et, à partir d’un échantillon généré aléatoirement, on pourra obtenir un intervalle de confiance, par exemple en utilisant une approximation de cette loi binomiale par une loi normale (on pourrait utiliser d’autres méthodes pour déterminer un intervalle de confiance mais restons simples). Je ne rentre pas dans les détails  mais en termes plus compréhensibles, on va faire un sondage et demander à plusieurs nombres: « Monsieur, êtes-vous sans facteur carré ? » en espérant qu’ils répondent le plus honnêtement possible sur leurs opinions politiques sur le fait qu’ils sont avec ou sans facteur carré.

J’ai donc écrit un autre programme en Python pour faire ce sondage sur un échantillon de 100 nombres pris au hasard entre 1 et 1 000 000. Afin d’avoir des nombres vraiment aléatoires (et non pas pseudo-aléatoires), j’ai fait appel au site http://www.random.org (honnêtement, je ne sais pas si le fait que les nombres soient pseudo-aléatoires change grand chose ici, mais ça faisait classe). Voici le programme:

Estimation du nombres d’entiers sans facteur carré

Et voici ce qu’on obtient:

Sondage_intervalle_de_confiance

Donc, l’intervalle [0,494 ; 0,686] est un intervalle de confiance au niveau de confiance de 95%. Mais ça veut dire quoi ? Ca ne veut pas dire que la proportion p de nombres sans facteur carré possède 95% de chances d’être dans cet intervalle précis (comme j’ai pu le lire à différents endroits… paraît qu’on enseigne ça au lycée. Déjà, foutre des intervalles de confiance au lycée, c’est du foutage de gueule, mais passons…). Non. Cela signifie que si on reproduit un grand nombre de fois ce sondage, et bien la proportion p appartiendrait à environ 95% des intervalles qu’on obtiendrait. Pour bien comprendre cette nuance, j’ai effectué 100 fois de suite ce sondage (sur des échantillons de 100 nombres à chaque fois) et voici les intervalles de confiance obtenus:

On a fait 100 sondages de 100 nombres chacun. Chaque intervalle de confiance correspond à un sondage. On voit que la proportion estimée appartient à environ 95 des 100 intervalles de confiance.

On a fait 100 sondages. Chaque sondage consiste à choisir au hasard 100 nombres entre 1 et 1 000 000. Chaque intervalle de confiance (en rouge) correspond à un sondage. On voit (ligne bleue) que la proportion estimée de nombres sans facteur  carré appartient à environ 95 des 100 intervalles de confiance.

En bleu, on voit que la proportion (réelle) de nombres sans facteur carré appartient à environ 95 des 100 intervalles de confiance. On peut l’estimer à vue de nez à environ p=0,6. Donc, en l’an 1 000 000, il y aura eu environ 60% des années qui auront été sans facteur carré. Magnifique !

Cela étant dit, cette valeur de 0,6 est bien mystérieuse… D’où vient-elle ?

Zêta(2) est arrivé ! Sans se presser !

Si n>1 est un entier naturel, et si on note Q(n) le nombre de nombres sans facteur carré inférieurs à n, on peut démontrer le résultat suivant:

\dfrac{Q(n)}{n} \sim \dfrac{6}{\pi^2}

Le nombre \dfrac{6}{\pi^2} vaut environ 0,60792…. ce qui représente ce qu’on appelle la densité des nombres sans facteurs carré. Une façon de l’intepréter serait de dire que si je choisis un nombre entier naturel « au hasard », alors j’ai 60,7% de chances qu’il soit sans facteur carré.

Mais d’où vient ce \pi ? Il a l’air sorti de nulle part… En fait, le nombre \dfrac{6}{\pi^2} est l’inverse du nombre bien connu \dfrac{\pi^2}{6} qui n’est autre que la somme \sum 1/k^2. « K carré ». « Facteur carré ». Démonstration par la rime.
Plus rigoureusement, on montre que cette série apparaît naturellement quand on reprend la méthode du crible que j’ai exposée plus haut pour 40 et 2014 et en la généralisant pour un entier quelconque. Eh ouais, on s’était fait chier à faire ce dénombrement avec des patates quand un simple programme informatique suffisait, mais ce que le programme n’apportera (probablement) jamais, c’est une méthode générale !

Bonne et heureuse année 2014 à tous !

Advertisements
Cet article, publié dans Arithmétique, Dénombrement, Nombres, est tagué , , , , , , . Ajoutez ce permalien à vos favoris.

12 commentaires pour En 2014, point de carré

  1. Sereina dit :

    Merci pour cet article très intéressant et bonne année !

  2. Gédéon dit :

    J’ai pas tout compris, mais ça m’amuse quand même… 2014, année de la culture, y compris mathématique !

  3. Ping : 2014 or not 2014 | C'π'rquet

  4. Yannick dit :

    Et pour 2014, on peut faire le décompte pour la nouvelle année avec un séquence astucieuse d’entier, en vidéo https://vimeo.com/83021046 et expliqué ici http://oeis.org/A083074. Bonne année.

  5. Une élève de PCSI dit :

    Super article et surtout très compréhensible ! Merci, et bonne année!

  6. luxiole dit :

    un article très bien détaillé et on retrouve l’importance des nombres premiers notemment dans la décomposition en facteurs premiers.

  7. Ping : Trèfle à quatre feuilles | Blogdemaths

  8. Ping : Trèfle à quatre feuilles | Actumaths

  9. Ping : 2015, année palindromique | Blogdemaths

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s