Forum de mathématiques - Bibm@th.net

LEG

Membre

Inscription : 19-09-2012

Messages : 790

Re : Problème avec un programme Python

Bonjour
N = 100000000000000000000000000000000000000000000000011
Record : 87123163749385631861110543148208953735435014848000 avec 18 119 393 280 diviseurs
Temps : 0.8617 s

Bonne soirée

Dernière modification par LEG (30-08-2025 16:14:54)

Ernst

Membre

Inscription : 30-01-2024

Messages : 339

Re : Problème avec un programme Python

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.

Ernst

Membre

Inscription : 30-01-2024

Messages : 339

Re : Problème avec un programme Python

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 ;-)