# coding: utf-8 # # Des dates qui font des nombres premiers ? # # Ce petit [notebook Jupyter](https://www.jupyter.org/), écrit en [Python](https://www.python.org/), a pour but de résoudre la question suivante : # # > *"En 2017, combien de jours ont leur date qui est un nombre premier ?"* # # Par exemple, en 2017, le 23 février donne `23022017` est premier, mais le 24 février donne `24022017` qui ne l'est pas. # On veut trouver toutes les dates en 2017 qui sont des nombres premiers. # ---- # ## 1. Il faut bien poser le problème # - *Q:* Qu'entends-on par *"date qui est un nombre premier"* ? # - Ça dépend de l'écriture de la date, que ce soit `12012017` pour le 12 janvier ou `01122017`. # - Dans le doute, la solution présentée ici sera adaptable aux deux cas. # - *Q:* Pourquoi se restreindre à 2017 ? # - Parce que j'écris ce document en 2017... # - Parce que c'est un nombre impair, et donc un nombre de la forme `12012017` a une chance d'être premier ! # - Mais dans le doute, la solution présentée ici sera adaptable à n'importe quelle année. # - *Q:* Quelles années ont le plus de dates premières ? # - *Q:* Est-ce qu'on peut inverser la question et chercher quel jour donne le plus de dates premières ? # ---- # ## 2. Une première solution, naïve # - On va d'abord écrire (ou importer) une fonction pour tester si un entier est premier, # - Puis on va écrire une fonction qui transforme une date en son nombre, # - Et enfin une boucle sur les 365 (ou 366) jours de l'année suffira à afficher les jours ayant une date première. # ### 2.1. Tester la primalité, version tricheur # [`sympy`](http://www.sympy.org/) propose une fonction [`sympy.isprime`](http://docs.sympy.org/latest/modules/ntheory.html#sympy.ntheory.primetest.isprime). # In[1]: from sympy import isprime # Elle marche très bien, et est très rapide ! # In[2]: [isprime(i) for i in [2, 3, 5, 7, 10, 11, 13, 17, 2017]] # Pour des nombres de 8 chiffres (c'est tout petit), elle est vraiment rapide : # In[3]: from numpy.random import randint get_ipython().run_line_magic('timeit', 'sum([isprime(i) for i in randint(1e8, 1e9-1, 10**4)])') # $\implies$ $65 ~\text{ms}$ pour 10000 nombres à tester, ça me semble assez rapide pour ce qu'on veut en faire ! # ---- # ### 2.2. Transformer une date en nombre # On va utiliser le module [`datetime`](https://docs.python.org/3/library/datetime.html) de la bibliothèque standard : # In[4]: from datetime import datetime # In[5]: today = datetime.today() YEAR = today.year print("On va travailler avec l'année", YEAR, "!") # C'est ensuite facile de transformer une date en nombre, selon les deux formats. # On utilise [le formatage avec `.format()`](https://pyformat.info/#datetime) (en Python 3) : # In[6]: def date_vers_nombre(date): return int("{:%d%m%Y}".format(date)) def date_vers_nombre_2(date): return int("{:%m%d%Y}".format(date)) # In[7]: date = datetime(YEAR, 1, 12) print(date_vers_nombre(date)) print(date_vers_nombre_2(date)) # Le 0 initial est ignoré # ### 2.3. Tester tous les jours de l'année # On peut partir du 1er janvier de cette année, et ajouter des jours un par un. # On utilise un itérateur (avec le mot clé `yield`), pour pouvoir facilement boucler sur tous les jours de l'année en cours : # In[8]: from datetime import timedelta def tous_les_jours(year=YEAR): date = datetime(year, 1, 1) un_jour = timedelta(days=1) for i in range(0, 366): yield date date += un_jour if date.year > year: # On est allé trop loin raise StopIteration # On peut vérifier que ça donne ce qu'on voulait : # In[9]: for date in tous_les_jours(): print("Le jour {:%d/%m/%Y} donne l'entier {:>8} au format jour-mois-année et {:>8} au format mois-jour-année.".format(date, date_vers_nombre(date), date_vers_nombre_2(date))) # Maintenant, il suffit de boucler, de tester si l'entier est premier, et de n'afficher que ceux qui le sont : # In[11]: def date_premieres(conversion=date_vers_nombre, year=YEAR): for date in tous_les_jours(year): if isprime(conversion(date)): yield date # On peut aussi facilement trouver la prochaine date qui sera première : # In[12]: def prochaine_date_premiere(date=datetime.today(), conversion=date_vers_nombre): year = date.year un_jour = timedelta(days=1) for i in range(0, 366): if isprime(conversion(date)): return date date += un_jour if date.year > year: # On est allé trop loin return None return None # In[13]: date = datetime.today() prochain = prochaine_date_premiere(date) print("Pour le jour d'aujourd'hui ({:%x}), le prochain jour ayant une date première dans l'année {} est : {:%x} !".format(date, date.year, prochain)) # #### Pour les dates écrites "jour mois année" : # In[14]: for date in date_premieres(date_vers_nombre): print("Le jour {:%d/%m/%Y} donne l'entier {:>8} qui est premier !".format(date, date_vers_nombre(date))) # #### Pour les dates écrites "mois jour année" : # In[15]: for date in date_premieres(date_vers_nombre_2): print("Le jour {:%d/%m/%Y} donne l'entier {:>8} qui est premier !".format(date, date_vers_nombre_2(date))) # #### Comparaison # Il y a 71 jours, en 2017, qui ont une date première si on les écrit "jour mois année", et 69 si on les écrits "mois jour année". # In[16]: len(list(date_premieres(date_vers_nombre))) # In[17]: len(list(date_premieres(date_vers_nombre_2))) # ---- # ## 3. Résolvons le problème pour toutes les années entre 0 AC et 2500 AC # # On aimerait afficher une courbe montrant l'évolution du nombre de dates premières au cours des années, selon les deux formats. # In[18]: def nombres_dates_premieres(year=YEAR): if year % 2 == 0: return [0, 0] else: return [len(list(date_premieres(date_vers_nombre, year=year))), len(list(date_premieres(date_vers_nombre_2, year=year)))] # In[19]: nombres_dates_premieres() # On vérifie que pour les années paires il n'y a pas de dates premières : # In[20]: len(list(date_premieres(date_vers_nombre, year=2016))) # On peut donc récupérer toutes ces nombres, jusqu'à l'année 3000. # (On pourrait gagner du temps en ne considérant que les années impaires, et l'année 1) # In[21]: import numpy as np def intervale_nombres_dates_premieres(year1=1, year2=3000): nombres = np.zeros((year2 - year1 + 1, 2)) for i, year in enumerate(range(year1, year2 + 1)): nombres[i, :] = nombres_dates_premieres(year) return nombres # On essaie sur un intervale de 11 ans : # In[22]: get_ipython().run_cell_magic('time', '', 'nombres = intervale_nombres_dates_premieres(year1=2010, year2=2020)\nprint(nombres)') # In[23]: get_ipython().run_cell_magic('time', '', 'nombres = intervale_nombres_dates_premieres(year1=1, year2=3000)\nprint(nombres)') # In[24]: np.shape(nombres) # Quelques statistiques : # In[25]: print("- Au format jour-mois-année, il y a en moyenne {:.3g} jours premiers par an.".format(np.mean(nombres[:, 0]))) print("- Et en moyenne {:.3g} jours premiers par an, en enlevant les années paires.".format(np.mean(nombres[:, 0][nombres[:, 0] > 0]))) print("- Au format mois-jour-année, il y a en moyenne {:.3g} jours premiers par an.".format(np.mean(nombres[:, 1]))) print("- Et en moyenne {:.3g} jours premiers par an, en enlevant les années paires.".format(np.mean(nombres[:, 1][nombres[:, 1] > 0]))) # On va afficher tout ça : # In[28]: get_ipython().run_line_magic('matplotlib', 'inline') import matplotlib.pyplot as plt import seaborn as sns sns.set(context="notebook", style="darkgrid", palette="hls", font="sans-serif", font_scale=1.4) # In[37]: def affiche_nombres_dates_premieres(nombres): plt.figure() plt.plot(nombres[:, 0], 'b.', label="Format jour-mois-année") plt.plot(nombres[:, 1], 'g*', label="Format mois-jour-année") plt.title("Nombres de dates premières par an") plt.legend(loc='best', numpoints=1, fancybox=True, shadow=True, framealpha=0.8) plt.xlabel("Année") plt.ylabel("Nombre de dates premières") # In[38]: affiche_nombres_dates_premieres(nombres) # Avec un histogramme : # In[39]: def hist_nombres_dates_premieres(nombres, ind=0): nbs = nombres[:, ind] nbs = nbs[nbs > 0] plt.figure() plt.hist(nbs, bins=100, label="Format %s-année" % ('jour-mois' if ind==0 else 'mois-jour'), color='bg'[ind]) plt.title("Répartition du nombres de dates premières par an") plt.legend(loc='best', numpoints=1, fancybox=True, shadow=True, framealpha=0.8) plt.xlabel("Nombres de dates premières") plt.ylabel("Nombres") # In[40]: hist_nombres_dates_premieres(nombres, 0) hist_nombres_dates_premieres(nombres, 1) # ## 4. Quels jours donnent le plus de nombres premiers ? # # On peut se poser une autre question : quelle date donne le plus de nombres premiers ? # # On a vu que le 23 février donne `23022017` qui est premier, et `24022017` ne l'est pas. # Mais en sur 3000 années successives, est-ce que le 23 février donne plus souvent un nombre premier que le 24 février ? # In[49]: def meme_jour_toutes_les_annees(days=0, year1=1, year2=3000): date = datetime(year1, 1, 1) date += timedelta(days=days) for i, year in enumerate(range(year1, year2 + 1)): yield date.replace(year=year) # In[52]: list(meme_jour_toutes_les_annees(days=31+22, year1=2017, year2=2019)) # In[53]: def nombre_annees_qui_donnent_date_premiere(days=0, year1=1, year2=3000, conversion=date_vers_nombre): for date in meme_jour_toutes_les_annees(days=days, year1=year1, year2=year2): if isprime(conversion(date)): yield date # Par exemple, pour mon anniversaire, entre ma naissance et maintenant, une seule année a donné une date `1201YEAR` qui soit première : # In[59]: list(nombre_annees_qui_donnent_date_premiere(days=11, year1=1993, year2=2017)) # Le 23 février a plus de chance : # In[61]: list(nombre_annees_qui_donnent_date_premiere(days=31+22, year1=1993, year2=2017)) # On peut récupérer ces données pour tous les jours de l'année : # In[62]: def histogramme_par_jours(year1=1, year2=3000, conversion=date_vers_nombre): jours = np.zeros(366) for days in range(366): jours[days] += len(list(nombre_annees_qui_donnent_date_premiere(days=days, year1=year1, year2=year2, conversion=conversion))) return jours # In[68]: get_ipython().run_cell_magic('time', '', 'jours = histogramme_par_jours(year1=1993, year2=2017)\njours') # In[73]: get_ipython().run_cell_magic('time', '', 'jours_format1 = histogramme_par_jours(year1=1, year2=3000, conversion=date_vers_nombre)\njours_format1 /= 3000') # In[74]: get_ipython().run_cell_magic('time', '', 'jours_format2 = histogramme_par_jours(year1=1, year2=3000, conversion=date_vers_nombre_2)\njours_format2 /= 3000') # ### 4.1. Visualisations, jour par jour # Exploitons ces données : # In[75]: def hist_nombres_dates_premieres(jours, ind=0): plt.figure() plt.plot(jours, label="Format %s-année" % ('jour-mois' if ind==0 else 'mois-jour'), color='bg'[ind]) plt.title("Répartition du nombres de dates premières selon la date\nEntre l'an 1 et l'an 3000") plt.legend(loc='best', numpoints=1, fancybox=True, shadow=True, framealpha=0.8) plt.xlabel("Jour dans l'année") plt.ylabel("Fréquence") # In[76]: hist_nombres_dates_premieres(jours_format1, ind=0) hist_nombres_dates_premieres(jours_format2, ind=1) # In[94]: def txt_date_de_jour(days): date = datetime(year=1, day=1, month=1) + timedelta(days=int(days)) return "{:%d/%m}".format(date) # ### 4.2. Quelle jour donne le plus de dates premières ? # Sans trop de surprise, c'est le 1er janvier qui gagne, pour les deux cas : # In[98]: txt_date_de_jour(np.argmax(jours_format1)) txt_date_de_jour(np.argmax(jours_format2)) # Mais en enlevant le 1er janvier et le dernier jour de l'année, on trouve une différence : # In[100]: np.argmax(jours_format1[1:-1]) txt_date_de_jour(_) np.argmax(jours_format2[1:-1]) txt_date_de_jour(_) # ---- # ## 5. Conclusions # - Pour les années impaires, il y a en moyenne une soixantaine de jours qui ont une date première !s, # - Le nombre est quasiment identique selon les deux formats, `jour-mois` ou `mois-jour`. # # Ce n'était pas très dur à calculer, mais intéressant. # # - Et en moyenne, un certain jour a entre 6% et 8% de donner une date première, entre l'an 1 et l'an 3000. # - Avec les deux formats, le 1er janvier est le jour qui donne le plus de dates premières, et puis le 31 décembre, puis le 31 août pour le format `jour-mois` et le 8 janvier pour le format `mois-jour`. # > C'est tout pour aujourd'hui les amis, [allez voir d'autres notebooks si vous êtes curieux !](https://github.com/Naereen/notebooks/). # # > [See this repository for other Python notebook doing numerical simulations](https://github.com/Naereen/notebooks/tree/master/simus/).