Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#76 Re : Entraide (collège-lycée) » Petit calcul de probas concrètes » 18-09-2025 09:12:13
Bonjour
Je me dis qu’il n’y a qu’une chance sur 10 que le chiffre de ton code se trouve à la première place, quel qu’il puisse être. Une fois que celui-ci est à la première place, il reste encore neuf chiffres disponibles pour la deuxième place, donc une chance sur 9 pour que le chiffre à la deuxième place corresponde à celui de ton code. De proche en proche, j’évalue cette probabilité à $\dfrac{1}{10}\times \dfrac{1}{9}\times \dfrac{1}{8}\times \dfrac{1}{7}\times \dfrac{1}{6}\times \dfrac{1}{5}=\dfrac{1}{604800}$
#77 Re : Enigmes, casse-têtes, curiosités et autres bizarreries » 15 boules à classer » 09-09-2025 10:03:46
Bonjour,
Oui, dans le rail final les configurations qui résistent demandent encore deux tris. Je suis en train de regarder un truc, dans un premier temps ne pas trier la ligne centrale, on gagne quatre opérations, et quand on a dégagé les coins et qu'il ne reste plus que trois éléments dans cette ligne, alors on la trie, on perd donc une opération à ce moment-là, mais il nous reste un différentiel positif de trois opérations à utiliser plus tard. Par contre on se retrouve avec des éléments incongrus dans le rail, faut utiliser des tris pour les rapprocher de leur position finale, donc pas sûr qu'on y gagne quoi que ce soit...
#78 Re : Enigmes, casse-têtes, curiosités et autres bizarreries » 15 boules à classer » 08-09-2025 21:28:14
Au boulot.
Bonsoir renéb,
Voilà une nouvelle approche en essayant de coller au mieux à tes explications. Honnêtement, ta méthode marche super bien, même si elle n’est pas parfaite, je suis toujours aussi admiratif pour quelque chose que j'ai été incapable d’approcher :
https://sites.google.com/view/ernst01/boules2
Suffit de relancer la session (F5 sur mon PC) pour avoir d’autres configurations. Il arrive que le rail final ne soit pas dans l’ordre, un point vert ou rouge permet de le voir plus vite. Un bouton ‘auto’ permet de trouver plus facilement les configurations qui résistent, histoire de décortiquer ce qui s’est passé et d’analyser le pourquoi du comment.
N’empêche, impressionné je reste, t’as vraiment mis le doigt sur quelque chose, y a sans doute pas grand-chose qui coince (mais je n’en ai aucune idée, je le dis tout de suite).
#79 Re : Enigmes, casse-têtes, curiosités et autres bizarreries » 15 boules à classer » 08-09-2025 14:59:59
Argh, j'ai dû me tromper quelque part, il y a des mélanges pour lesquels ça ne marche pas :
15-16-23-21-12
24-18-20-14-11
25-22-19-17-13
Quand c'est terminé, le rail donne 11-12-14-13... donc pas top.
J'ai forcé cette grille histoire de vérifier :
https://sites.google.com/view/ernst01/boules1
J'ai dû me gourer dans les cases à trier. Le fait que je place par exemple en R 2-3-4 les boules en attente que tu tries à part et que tu places ensuite à cette même place, ou que je cherche directement les cases sans déplacer les lignes ne devrait pas changer grand chose, et même le fait de pouvoir vérifier avant/après ne m'a pas permis de trouver l'erreur...
(désolé)
#80 Re : Enigmes, casse-têtes, curiosités et autres bizarreries » 15 boules à classer » 08-09-2025 13:54:49
c'est long l'explication.
Cette méthode est à toutes épreuves.
J'en ai pondu un programme python qui restitue à 100 % le classement des 15 boules en tous points identiques (sauf par leur poids qui est inique) en 25 recours à l'appareil.
Bonjour,
Absolument magnifique.
Allez hop, ta méthode (nombres de 11 à 25 pour ne pas confondre avec les indices) détaillée visuellement :
https://sites.google.com/view/ernst01/boules
Strictement aucun test, cases déplacées ou triées sans regard sur leur contenu, moi je dis chapeau !!!
#81 Re : Enigmes, casse-têtes, curiosités et autres bizarreries » Encore une boucle ?? » 07-09-2025 07:12:38
L'idée des "fantômes" était la pierre angulaire de la question, mais j'attendais juste que tu dises exactement pourquoi on retombe sur ses pieds, ce qui n'est pas trivial. En somme quitter un peu l'algorithmique et la programmation (*) pour aborder la question mathématique pure.
(*) domaines pour lesquels je tire mon chapeau ! Ce genre d'animation est faite en javascript ? en python (style Tkinter très pratique par exemple) ? Autre langage ?
Bonjour,
Ce programme est principalement écrit en JavaScript, avec une structure de base en HTML et une mise en forme en CSS. Voici la répartition :
HTML définit la structure de la page :
- Le titre et les informations de la page
- Les éléments du vélodrome : cadran, contrôles, infos
- Les balises <script> pour inclure le code JavaScript
CSS (dans la section <style>) gère l’apparence visuelle :
- La disposition des éléments
- Les couleurs et le style des cyclistes
- La taille du canvas et des cyclistes
- Le style général des boutons, sliders et tableaux
(L’animation elle-même est gérée par JavaScript)
JavaScript est le cœur du programme :
- Création et gestion des cyclistes (position, direction, maillot)
- Animation des déplacements sur le vélodrome
- Détection des rencontres et gestion des interactions (demi-tour ou échange de maillots)
- Mise à jour du compteur d’étapes et du tableau des tours
- Démarrage, arrêt et contrôle de la vitesse de l’animation
- Vérification du retour à la position initiale
- Interaction avec l’interface utilisateur (boutons, curseur, case à cocher)
En résumé : HTML fournit la structure, CSS le style, et JavaScript l’interactivité et la logique de la simulation.
Pour ceux que cela intéresse, voici un modèle interactif qui permet de choisir le nombre de cyclistes et le nombre de ceux qui iront dans un sens. La disposition est aléatoire, mais cela permet quand même de se faire une bonne idée des mécanismes mis en jeu. En mode lent avec rebonds, on voit les cyclistes osciller en d’interminables va-et-vient. En mode rapide, on voit comment l’œil se plaît à suivre les mouvements continus et passe d’un cycliste à l’autre. Ce que propose le mode fantôme, c’est justement ce suivi.
https://sites.google.com/view/ernst01/velodrome1
Sur ce, j’ai bien compris que ce n’était pas ce que tu attendais ni en termes de rigueur ni en termes de preuve et donc en ce qui me concerne je m’arrêterai là.
#82 Re : Enigmes, casse-têtes, curiosités et autres bizarreries » Encore une boucle ?? » 04-09-2025 08:34:09
Bonjour,
On se sera mal compris, voilà tout. Pour moi l’idée était de trouver un truc pour résoudre un casse-tête, un peu comme avec la mouche qui fait des va-et-vient entre deux trains qui se rapprochent et dont on évalue la longueur de trajet par le temps de vol plutôt que par une sommation de distances. Mon histoire de fantômes qui échangent leurs maillots réduisait le problème à des cyclistes qui continuent de tourner dans le même sens et qui se retrouvent finalement comme au début, c’était rigolo.
#83 Re : Enigmes, casse-têtes, curiosités et autres bizarreries » Encore une boucle ?? » 03-09-2025 22:22:07
Au bout d'un tour, deux cyclistes donnés qui ont échangé leurs dossards quand ils se sont croisés deux fois, ne se retrouvent pas nécessairement tous les deux avec leur dossard initial. Il y en a d'autres avant la fin du tour avec qui ils ont échangés.
Bonsoir,
Bien sûr, on voit très bien dans la simulation que $a$ va endosser à plusieurs reprises le maillot de $b$ et de $c$ au fil de ses déplacements.
En fait c'est l'utilisation du mot 'tour' qui te gêne, c'est ça ? J'aurais dû parler de cycle complet ou préciser 'tour de jeu' pour ne pas laisser entendre tour de piste, c'est vrai. Fondamentalement, surtout avec la simulation, ça change quelque chose au raisonnement ?
#84 Re : Enigmes, casse-têtes, curiosités et autres bizarreries » Encore une boucle ?? » 03-09-2025 16:28:05
Deux choses "clochent" dans l'idée de Ernst.
Ne pas avoir peur non plus de bien lire l'énoncé, afin de ne pas faire d'hypothèses inexistantes.
On peut prendre aussi éventuellement de petits nombres de coureurs, par exemple 3, du papier, un crayon, pour mieux visualiser.
Bonjour,
Tiens, je serais curieux de savoir lesquelles. Voici une animation de trois cyclistes qui permet de comparer les deux versions sur un cycle complet.
https://sites.google.com/view/ernst01/velodrome
Si tu pouvais expliquer ce qui ne va pas alors que les résultats sont identiques, cela m'éclairerait.
#85 Re : Programmation » Problème avec un programme Python » 03-09-2025 14:33:42
Explications :
Normalement, le programme teste tous les exposants de tous les nombres premiers jusqu’à dépassement. Pour 10^50 il n’y en avait besoin que de 28, et aucun exposant ne dépassait 10.
Pour aller plus loin, il faut à la fois augmenter le nombre de facteurs premiers et la valeur des exposants, toutes choses qui rendent la recherche vraiment chronophage. L’idée a donc été d’une part de déterminer le nombre de facteurs premiers nécessaires, 48, et d’autre part de repérer l’exposant max pour chaque facteur : 13, 8, 4, 4, 3, 2, 2, 2, 2
Cela veut dire que jamais on n’a besoin de plus de $2^{13}$, de $3^{8}$, de $5^{4}$, etc. Au delà des neuf premiers termes tous les autres sont les nombres premiers eux-mêmes. Inutile de préciser que l’élagage est alors optimal, on ne fait que les combinaisons susceptibles de faire un record, on élimine dès que le résultat dépasse N, très efficace.
(par contre déterminer précisément ces valeurs m’a quand même pris un sacré bout de temps ;-)
#86 Re : Programmation » Problème avec un programme Python » 03-09-2025 13:53:37
Bonjour,
On en était donc à un programme qui doit trouver, dans un intervalle donné, l’entier ayant le plus grand nombre de diviseurs.
Grâce à un élagage bien plus efficace de l’arbre de recherche, voici maintenant un programme en Python de base, donc sans bibliothèque externe, qui cette fois obtient le bon résultat sur une plage de 1 à 10^100 en quelques dixièmes de secondes.
import time
PRIMES = [
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, 101, 103, 107, 109, 113,
127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
179, 181, 191, 193, 197, 199, 211, 223
]
EXP_LIMITS = [13, 8, 4, 4, 3, 2, 2, 2, 2]
MAX_EXP_COUNT = len(EXP_LIMITS)
MAX_PRIME_INDEX = len(PRIMES)
MAX_LIMIT = 10**100 - 1
best_n, best_divs = 1, 1
def parse_limit(text: str):
t = text.strip()
if not t:
return MAX_LIMIT
if t.lower() == 'q':
return None
try:
if "^" in t:
a, b = t.split("^")
return min(int(a) ** int(b), MAX_LIMIT)
return min(int(t), MAX_LIMIT)
except Exception:
return "invalid"
def explore(idx, last_exp, n, divs, used_exps, Nmax):
global best_n, best_divs
if n > Nmax: return
if divs > best_divs or (divs == best_divs and n < best_n):
best_n, best_divs = n, divs
if idx >= MAX_PRIME_INDEX: return
limit = min(last_exp, EXP_LIMITS[idx] if idx < len(EXP_LIMITS) else 1)
p = PRIMES[idx]
powp = 1
for e in range(1, limit+1):
powp *= p
if n * powp > Nmax: break
new_used = used_exps + (1 if e > 1 else 0)
if new_used > MAX_EXP_COUNT: break
explore(idx+1, e, n*powp, divs*(e+1), new_used, Nmax)
# --- Boucle interactive ---
while True:
print("entier, a^b, vide=10^100-1, q pour quitter")
N_input = input("N : ")
if N_input.lower() == 'q':
print("Fin du programme.")
break
Nmax = parse_limit(N_input)
if Nmax == "invalid":
print("❌ Entrée invalide, recommencez.")
continue
if Nmax is None:
print("Fin du programme.")
break
best_n, best_divs = 1, 1
t0 = time.time()
explore(0, 60, 1, 1, 0, Nmax)
t1 = time.time()
print(" ")
print(f"N = {Nmax}")
print(f"Record : {best_n}")
print(f"Nombre de diviseurs : {best_divs}")
print(f"Temps : {t1 - t0:.3f} s")
print(" ")
Toujours plus, telle est ma devise.
#87 Re : Enigmes, casse-têtes, curiosités et autres bizarreries » Encore une boucle ?? » 03-09-2025 11:05:49
Bonjour,
Si on imagine que les cyclistes ne font jamais demi-tour en se croisant, mais qu’ils se traversent comme des fantômes, chacun continue tranquillement son chemin à vitesse constante. Au bout d’un tour de piste, chaque cycliste est donc revenu exactement à sa place de départ, dans la même direction qu’au début.
Dans la vraie règle, deux cyclistes qui se croisent échangent en réalité leurs « rôles » : c’est comme si leurs maillots passaient de l’un à l’autre, tandis que leurs corps poursuivent leur route fantôme. Ainsi, les positions des corps restent celles du scénario des fantômes, et tout ce qui change, ce sont les maillots qui circulent de rencontre en rencontre.
Chaque paire de cyclistes de sens opposé se croise deux fois pendant un tour complet : au premier croisement, ils échangent leurs maillots ; au second, ils les récupèrent. Chaque maillot subit donc un nombre pair d’échanges et de changements de sens, ce qui fait qu’à la fin du tour, tout le monde retrouve son maillot et roule dans le même sens qu’au départ.
#88 Re : Enigmes, casse-têtes, curiosités et autres bizarreries » Une farce avec le carburant » 02-09-2025 14:35:38
ce qui me vient à l'idée c'est une question de "densité"
Hello lamexstyle,
Ton idée de densité me plaît bien. Plus le carburant se raréfie sur certaines parties du parcours, plus il se condense sur d’autres, par construction même. Peu importe alors le sens de déplacement, il suffit de commencer par une zone qui permet de récupérer suffisamment d’excédent pour le répartir sur les zones qui en sont dépourvues, c’est tout.
Pour illustrer ton idée de densité, partons d’un tableau circulaire de cases dans lesquelles il y aurait des billes. S’il y a autant de billes que de cases, densité 1, le tour est complet.
Si on enlève des billes pour les mettre ailleurs, il suffit de compter le déficit ou l’excédent cumulé case après case en partant de n’importe où, et cela va nous dire d’où partir. On additionne les valeurs des cases (nombres de billes par case moins un) et on part juste après le cumul le plus négatif, de la sorte on est sûr de ne jamais avoir de dette, autrement dit les excédents du parcours permettront toujours d’en faire le tour complet.
Exemple, un parcours de douze cases douze billes :
Le cumul vaut :
[ 0, 0,-1,-2,-1,-2,-2, 0, 2, 1, 1, 0]
On peut donc partir de :
[ 1, 1, 0, 0,*2, 0,*1,*3, 3, 0, 1, 0]
#89 Re : Enigmes, casse-têtes, curiosités et autres bizarreries » Une farce avec le carburant » 01-09-2025 23:19:40
Amis des problèmes amusants, bonsoir.
Avant tout je remercie lamexstyle d'avoir compris mon image.
L'idée était de représenter l'itinéraire total par un cercle et d'assimiler le carburant permettant de parcourir le trajet à ce cercle, et remarquer que fractionner le carburant revenait à fractionner le cercle, tout simplement - cela ne changeait pas la nature du problème.
Si on déplace une portion de cercle, on crée un espace vide d'un côté et une superposition de l'autre, sauf si la portion qu'on déplace ne se superpose pas à la portion suivante, mais la pousse. Dans ce cas, la portion suivante glisse aussi et de proche en proche le cercle reste jointif.
D'où mon expression de 'poussoir' attribué au réservoir de la voiture, trop compliquée pour certains j'en conviens.
Alors je vais dire que la partie correspondant à la superposition correspond à la partie vide que l'on a créée - jusque là rien de difficile - et que le réservoir de la voiture permet de la récupérer et de la reporter sur la partie vide, ça marche aussi.
#90 Re : Programmation » Problème avec un programme Python » 29-08-2025 21:39:05
Explications : en fait ici, on ne va plus chercher les records, on va les créer grâce à une formule multiplicative. Si $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ est la factorisation en nombres premiers de $n$, alors le nombre de diviseurs est donné par $\tau(n) = (a_1 + 1)(a_2 + 1) \cdots (a_k + 1)$. La recherche de records revient cette fois à explorer des combinaisons d'exposants $(a_1,a_2,\dots,a_k)$. La contrainte $a_1 \ge a_2 \ge a_3 \ge \dots \ge a_k \ge 1$ évite les doublons et ne considére que les factorisations pertinentes.
L'algorithme est implémenté de façon récursive :
- On part de $n=1$, $\tau(1)=1$.
- À chaque étape, on choisit un nouveau premier $p_i$ et un exposant $e$.
- Les contraintes sont :
1. $e \le e_{\text{précédent}}$ (monotonicité)
2. $n \cdot p_i^e \le N$ (ne pas dépasser la borne)
- On calcule $\tau(n)$ immédiatement et on stocke le couple $(n,\tau(n))$.
- On poursuit récursivement jusqu'à ce qu'aucune extension ne soit possible.
Sélection des records
- On garde en mémoire le meilleur $\tau(n)$ rencontré.
- Si $\tau(n) > \text{record}_{\text{courant}}$, on met à jour le record et la liste des nombres.
- Si $\tau(n) = \text{record}_{\text{courant}}$, on ajoute $n$ à la liste des ex aequo.
- À la fin, on obtient tous les nombres $n \le N$ qui battent un record de diviseurs.
Contrairement à la méthode naïve $O(N\sqrt{N})$ ou au crible $O(N \log N)$, le coût dépend uniquement du nombre de combinaisons d'exposants explorées. Pour $N=10^6$, quelques milliers de combinaisons, et même pour $N=10^{50}$ le programme en Python de base met moins de deux secondes.
Tadaa !
#91 Re : Programmation » Problème avec un programme Python » 29-08-2025 20:32:49
Amis de la programmation, bonsoir.
Pour mémoire, il s’agit de trouver le(s) nombre(s) ayant le maximum de diviseurs dans une tranche donnée de 1 à N avec un programme en Python.
Première approche, on essaie tous les diviseurs sur tous les nombres de la plage. Bon, c’est pas mal, en Python cela permet de couvrir plus de 10 000 nombres en quelques secondes.
Ceci dit, ça plafonne quand même assez vite. Pour gagner du temps, on peut considérer qu’au-delà de la racine carrée du nombre on obtient des valeurs déjà trouvées, et on peut donc s’arrêter à celle-ci. Grâce à cela, Python permet maintenant de dépasser les 100 000 nombres sans problème particulier.
Le système s’avère efficace pour les petites valeurs, mais au-delà de quelques centaines de milliers les temps deviennent de plus en plus prohibitifs. Comment faire mieux ?
La solution est plutôt inattendue : un simple crible. L’idée va être d’ajouter systématiquement comme diviseur celui que l’on teste à tous ses multiples. Au départ on a l’impression de calculs dissuasifs, mais c’est tout l’inverse qui se produit : en fait on élimine l’ensemble des tests et de toutes les tentatives inutiles, on n’utilise que l’addition, ce qui permet de dépasser le million en quelques secondes.
Eh bien de façon tout à fait étonnante, on peut faire nettement mieux. Et quand je dis nettement, c’est même invraisemblable. Terminé, game over, réponse instantanée :
import time
# --- Config ---
primes = [
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,101,103,107
]
MAX_EXP = 10
# --- Génération récursive ---
def generate_all(limit):
result = []
def dfs(idx, num, divs, prev_exp):
if idx >= len(primes):
return
p = primes[idx]
pow_p = 1
for e in range(1, min(prev_exp, MAX_EXP)+1):
pow_p *= p
next_num = num * pow_p
if next_num > limit:
break
next_divs = divs * (e+1)
result.append((next_num, next_divs))
dfs(idx+1, next_num, next_divs, e)
dfs(0, 1, 1, MAX_EXP)
return result
# --- Lecture de l'entrée ---
def parse_limit(text):
text = text.strip()
if not text:
return 10**6
if '^' in text:
base, exp = text.split('^')
return int(base)**int(exp)
return int(text)
# --- Main ---
if __name__ == "__main__":
N_text = input("Limite N (max 10^51 - 1) : ").strip()
limit = parse_limit(N_text)
if limit > 10**51-1:
raise ValueError("Limite max : 10^51-1")
t0 = time.perf_counter()
numbers = generate_all(limit)
numbers.sort(key=lambda x: x[0])
# --- Extraction des records ---
best_divs = 1
records_list = []
for n, divs in numbers:
if divs > best_divs:
best_divs = divs
records_list = [n]
elif divs == best_divs:
records_list.append(n)
t1 = time.perf_counter()
main_record = records_list[0]
print(f"N = {limit}")
print(f"Record : {main_record} avec {best_divs} diviseurs")
if len(records_list) > 1:
print(f"(même nombre de diviseurs pour {len(records_list)} entiers)")
print(f"Liste complète : {records_list}")
print(f"Temps : {t1-t0:.4f} s")
(j’ai limité à 999999999999999999999999999999999999999999999999999 parce qu’il faut bien s’arrêter quelque part)
Pour les curieux :
https://sites.google.com/view/ernst01/records
#92 Re : Programmation » Problème avec un programme Python » 29-08-2025 08:14:25
Bonjour yoshi,
Content de voir que d’autres partagent mon goût pour la programmation et l’optimisation, pour le plaisir uniquement.
Tu as écrit :
Vouloir progresser en comparant ses programmes avec ce qui serait produit par un programmeur de métier ou une IA serait vouloir monter de niveau […]
et
où il recevrait des conseils, pourrait analyser […] avec un être humain qui serait capable de s'adapter. Toutes choses qu'un professeur virtuel ne serait pas capable de faire
Sur ce point, il est possible que tu ne mesures pas tous les progrès qui ont été faits en la matière. Dès l’introduction du numérique grand public, des chercheurs ont tout fait pour qu’il serve à l’apprentissage, pour le rendre plus convivial, plus didactique aussi, bref pour le mettre au service des apprentissages et non pas pour les remplacer.
Pour te montrer l’état des lieux aujourd’hui, en 2025, et comme tu avais écrit
en matière de temps à 100 000, je suis largué...
Donc je vais tâcher de revoir la recherche des diviseurs.
je me suis permis de demander à une IA (ici ChatGPT en accès libre) de me proposer des améliorations, et surtout de me les expliquer :
https://chatgpt.com/share/68b14dd8-9a4c … b41698d2b8
J’aimerais vraiment avoir ton avis sur ses conseils, parce qu’à mes yeux on est très loin d’un Stockfish capable effectivement de débiter des lignes de jeu hyper pointues, mais sans jamais d’autres explications qu’un score potentiel sorti de ses calculs internes.
#93 Re : Programmation » Problème avec un programme Python » 27-08-2025 10:28:22
N = 15000000
Record : 14414400 avec 504 diviseurs
Liste complète : [14414400]
Temps : 0.95 s (multi-workers par plages) plus rapide
Bonjour,
En fait les 15 millions en 1.47 s c'était avec le programme C sur un seul thread. Avec Javascript multi-threads j'obtiens :
N = 15000000
Record : 14414400 avec 504 diviseurs
Liste complète : [14414400]
Temps : 0.28 s (multi-workers par plages)
De façon étonnante, en C avec multi-threading je ne gagne plus rien, c’est dire si Javascript est maintenant optimisé pour certaines opérations, et l'avantage du html, c'est que le programme peut tourner sur n'importe quel navigateur de façon sécurisée.
(50 millions ≃ 3 s sur mon PC, 8 s sur mon smartphone et 19 s sur ma tablette)
#94 Re : Programmation » Problème avec un programme Python » 26-08-2025 14:00:17
Bonjour,
Juste pour le fun, je me suis amusé à faire un programme en C pour obtenir la même chose, sur mon ordinateur c'est cette fois quinze millions en moins de deux secondes :
N = 15000000
Record : 14414400 avec 504 diviseurs
Liste complète : [14414400]
Temps : 1.47 s
Encore mieux, Javascript et parallélisme (PC multicœur), plutôt pas mal, trente millions en moins de deux secondes :
N = 30000000
Record : 21621600 avec 576 diviseurs
(même nombre de diviseurs pour 5 entiers)
Liste complète : [21621600, 24504480, 27387360, 28274400, 28828800]
Temps : 1.39 s (multi-workers par plages)
Puisque cela dépend beaucoup du matériel, chacun pourra se faire une idée avec le sien :
https://sites.google.com/view/ernst01/crible_1
Bref, on voit que :
- l’algorithme fait une différence
- le langage fait une différence
- le matériel fait une différence
#95 Re : Programmation » Problème avec un programme Python » 25-08-2025 14:50:10
Bonjour,
Le problème posé est plutôt intéressant pour aborder les enjeux de la programmation. J’utilise Basthon pour avoir une base identique à tous mes programmes, et conserver un code sans bibliothèque externe.
Première mouture, le test de tous les diviseurs possibles pour chaque nombre :
import time
def diviseurs(n):
d = []
for i in range(1, n + 1):
if n % i == 0:
d.append(i)
return d
def records(N):
max_div = 0
records = []
for n in range(1, N + 1):
nb = len(diviseurs(n))
if nb > max_div:
max_div = nb
records = [n]
elif nb == max_div:
records.append(n)
return max_div, records
N = 10_000 # méthode brute limitée
start = time.perf_counter()
max_div, recs = records(N)
end = time.perf_counter()
print(f"N = {N}")
print(f"Record : {recs[0]} avec {max_div} diviseurs")
if len(recs) > 1:
print(f"(même nombre de diviseurs pour {len(recs)} entiers)")
print(f"Liste complète : {recs}")
print(f"Temps : {end - start:.2f} s")
Résultat :
N = 10000
Record : 7560 avec 64 diviseurs
(même nombre de diviseurs pour 2 entiers)
Liste complète : [7560, 9240]
Temps : 3.91 s
On peut faire mieux en constatant qu’à chaque fois qu’on a un diviseur, on a aussi un résultat. Cela permet de s’arrêter à la racine carrée et donc de pouvoir aller environ dix fois plus loin dans un temps raisonnable :
import time, math
def diviseurs(n):
d = []
limite = int(math.isqrt(n))
for i in range(1, limite + 1):
if n % i == 0:
d.append(i)
autre = n // i
if autre != i:
d.append(autre)
return d
def records(N):
max_div = 0
records = []
for n in range(1, N + 1):
nb = len(diviseurs(n))
if nb > max_div:
max_div = nb
records = [n]
elif nb == max_div:
records.append(n)
return max_div, records
N = 100_000
start = time.perf_counter()
max_div, recs = records(N)
end = time.perf_counter()
print(f"N = {N}")
print(f"Record : {recs[0]} avec {max_div} diviseurs")
if len(recs) > 1:
print(f"(même nombre de diviseurs pour {len(recs)} entiers)")
print(f"Liste complète : {recs}")
print(f"Temps : {end - start:.2f} s")
Résultat :
N = 100000
Record : 83160 avec 128 diviseurs
(même nombre de diviseurs pour 2 entiers)
Liste complète : [83160, 98280]
Temps : 1.17 s
Peut-on encore faire mieux ? Oui, nettement, en partant du principe que chaque multiple d’un diviseur est donc divisé par ce diviseur. Autrement dit si on considère 3, eh bien on peut le rajouter comme diviseur à 3, 6, 9, 12, …. Avantage, on ne fait ni test, ni division, ni modulo, on n’a plus que des incrémentations :
import time
def records(N):
div_count = [0] * (N + 1)
for i in range(1, N + 1):
for j in range(i, N + 1, i):
div_count[j] += 1
max_div = max(div_count)
records = [i for i, nb in enumerate(div_count) if nb == max_div]
return max_div, records
N = 1_000_000
start = time.perf_counter()
max_div, recs = records(N)
end = time.perf_counter()
print(f"N = {N}")
print(f"Record : {recs[0]} avec {max_div} diviseurs")
if len(recs) > 1:
print(f"(même nombre de diviseurs pour {len(recs)} entiers)")
print(f"Liste complète : {recs}")
print(f"Temps : {end - start:.2f} s")
Résultat :
N = 1000000
Record : 720720 avec 240 diviseurs
(même nombre de diviseurs pour 5 entiers)
Liste complète : [720720, 831600, 942480, 982800, 997920]
Temps : 1.34 s
Calcul en Python de base de tous les diviseurs d’un million de nombres en moins de deux secondes, qui dit mieux ?
#96 Re : Programmation » Problème avec un programme Python » 24-08-2025 19:33:41
Est-ce que quelqu'un pourrait s'il vous plaît clairement m'expliquer ce qu'il faudrait faire pour répondre à la question ? Je veux vraiment comprendre.
Bonjour,
J'ai proposé ton programme à une IA, voici sa réponse :
- La fonction 'nombre_de_diviseurs' fonctionne, mais dans 'nombreux_diviseurs', après avoir trouvé le maximum dans la liste des nombres de diviseurs, elle ne fait pas le lien pour retrouver le nombre qui a ce nombre maximal de diviseurs.
- Le code inclut un morceau mort après le 'return r', qui ne sera jamais exécuté.
- La condition 'if diviseurs(x) == r:' ne compare pas la bonne chose (compare une liste de diviseurs à un entier).
Elle a aussi proposé ce code :
def diviseurs(n):
L = []
for i in range(1, n+1):
if n % i == 0:
L.append(i)
return L
def nombre_de_diviseurs(n):
return len(diviseurs(n))
def nombreux_diviseurs():
max_div = 0
nombre_avec_max_div = 0
for i in range(1, 1000):
nb_div = nombre_de_diviseurs(i)
if nb_div > max_div:
max_div = nb_div
nombre_avec_max_div = i
return nombre_avec_max_div, max_div
resultat = nombreux_diviseurs()
print(f"Le nombre < 1000 avec le plus grand nombre de diviseurs est {resultat[0]} avec {resultat[1]} diviseurs.")
En comparant, tu pourras étudier les différences, un excellent moyen je pense pour assimiler le pourquoi des dysfonctionnements.
#97 Re : Programmation » Problème avec un programme Python » 24-08-2025 19:22:49
C'est la plus grande puissance de $2$, c'est à dire $2^9=512$ qui possède $11$ diviseurs.
Bonjour,
840 a 32 diviseurs. (1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 15, 20, 21, 24, 28, 30, 35, 40, 42, 56, 60, 70, 84, 105, 120, 140, 168, 210, 280, 420, 840)
#98 Re : Café mathématique » Générateur de mots de passe » 21-08-2025 09:43:57
Mais tu peux chercher la petite bête si tu as du temps à perdre ! :-)
Bonjour,
On se sera mal compris, c’était plus une amélioration que je proposais qu’une critique. Dans mon esprit cela ne coûte rien d’y mettre par défaut au moins un caractère accentué, au moins un chiffre, au moins un caractère spécial puisque ce sont les attendus actuels.
Quant au craquage lui-même, la théorie qui associe « taille de l’alphabet + longueur » à la résistance d’un mot de passe ne tient aucun compte de la méthode d’encryptage, ce qui en soi est quand même problématique :
MD5 : Utilisé pour l’intégrité des fichiers et des communications, il est aujourd’hui trivialement cassable via des attaques de type collision.
SHA-1 : Comme MD5, SHA-1 était utilisé pour signer et authentifier de nombreux échanges sur Internet, mais il est vulnérable à des attaques de collision depuis 2017 et son usage est déconseillé.
RC4 : Cet algorithme de chiffrement en flux a été abandonné car de nombreuses attaques permettent de retrouver la clé à partir de suffisamment de texte chiffré. Il était notamment utilisé dans les suites SSL/TLS.
Diffie-Hellman sur petits groupes : Certains échanges Diffie-Hellman utilisant de petits paramètres sont aujourd’hui dépréciés pour la négociation de clés dans TLS en raison de nouvelles attaques computationnelles.
Mais bon...
#99 Re : Café mathématique » Générateur de mots de passe » 20-08-2025 18:37:43
Salut à tous,
Je viens de créer celui-ci.
La question de la difficulté à cracker un MDP a été traitée par GPT-5, dont j'ai ajouté les explications afin que chacun sache ce qu'il risque en utilisant des mots de passe de faible longueur. Mais comme j'ai tendance à ne pas faire une confiance absolue à ChatGPT, serait-il possible à ceux qui sont compétents en la matière de confirmer (ou non) ses dires ? Merci d'avance ! :-)
Bonjour,
En dehors même du craquage, ce générateur me pose un problème : l’absence de choix possible quant à l’alphabet. Pas mal de sites demandent aujourd’hui la présence d’une majuscule, d’un chiffre, d’un caractère spécial. Il m’a fallu moins d’une dizaine de tirages pour obtenir ceux-ci :
A42spG9qBQDfBHD
TMUgrg7fmtJ9HEr
QqghJPcEtFCEmGg
…
sans caractères spéciaux et donc me faire jeter des sites dont je parle.
Perso j’utilise ce site et en validant 'Avec des caractères spéciaux' je peux même les choisir.
Pour ce qui est du craquage lui-même, la seule possibilité est de disposer de fichiers récupérés et protégés, là on peut utiliser la force brute et pour le particulier bien équipé, des logiciels hyper spécialisés comme hashcat peuvent le faire, ils disposent d’une quantité impressionnante d’algorithmes très pointus.
Pour les sites en ligne, s’ils sont bien faits ils n’accepteront jamais des milliers d’essais à la seconde, donc c’est sans objet, le plus grand risque étant le piratage de leur banque de données, quelques exemples :
— CHU de Brest : Attaque par rançongiciel en 2024 ayant paralysé les soins et la gestion des dossiers médicaux, impactant fortement les patients et le personnel.
— Ville de Lille : Cyberattaque en février 2024 ayant forcé la fermeture temporaire de plusieurs services municipaux.
— Intersport : En 2024, une intrusion majeure a volé 52 Go de données sensibles des clients et employés, soulevant de graves inquiétudes sur la protection des données.
— Viamédis et Almerys (prestataires santé) : Fuites massives des données d’assurés début 2024.
— Free et SFR : Grandes fuites de données clients en 2024, notamment des millions d’IBAN (Free) et d’autres données personnelles, largement exposées sur le dark web.
— Bouygues Telecom : En 2025, piratage et fuite de données de millions d’abonnés, avec une communication compliquée suite à l’envoi d’un SMS aux clients qui a inquiété plus d’un.
— France Travail et CAF : Attaques massives avec compromission des données de millions d’usagers en 2024-2025.
(et cela uniquement pour ceux qui communiquent à ce sujet bien sûr)
À ce propos, alors que l’utilisateur ne devait PAS écrire quelque part ses mots de passe, maintenant qu’on lui impose d’utiliser les services en ligne il DOIT en choisir d’impossible à mémoriser, cherchez l'erreur…
#100 Re : Café mathématique » des cubes et des puissances supérieures » 19-08-2025 08:13:48
Je ne sais pas si cela présente vraiment de l'intérêt
Bonjour jelobreuil,
Pour moi, cela présente au moins l’intérêt de devoir programmer le truc. (je suis toujours fasciné de voir avec quelle facilité le numérique permet de trouver des solutions inaccessibles à la main)
Même avec une recherche bourrin, le balayage de toutes les valeurs a, b et c, je trouve déjà toute une tripotée de solutions, la vie est belle. Bon, N = 10 ok, puis 30, 50, 100, ok, à partir de N = 200 ça ralentit, et au-delà de N = 500 ça peine sévère.
Résultats pour N = 1000
Mode : a, b, c ∈ [1, N] (primitifs uniquement)
Nombre de solutions (d³ > 0) : 975
Temps total : 187.9 s
On en est déjà à trois minutes. Normal, on a trois valeurs indépendantes à décliner et informatiquement, on est O(N³).
Sauf que.
Au lieu de traiter a³ + b³ + c³ = d³, on peut aussi traiter d³ – c³ = a³ + b³. On peut par exemple calculer tous les résultats a³ + b³, les mettre dans une table de hashage, calculer ensuite toutes les combinaisons d³ – c³, et pour chacune regarder si le résultat se trouve dans la table.
Tu vas me dire, quel intérêt ?
Eh bien l’intérêt, c’est de ne plus traiter que deux valeurs indépendantes, et même si on doit le faire deux fois, c’est bien plus rapide que de devoir en traiter trois. Informatiquement, c'est passer de O(N³) à O(N²), et informatiquement toujours, c’est un gain tout à fait sérieux.
Pour bien comprendre l’efficacité du truc, le nouveau programme fait maintenant N = 1000 en 4.5 s, tadaa !