Forum de mathématiques - Bibm@th.net

Ernst

Membre

Inscription : 30-01-2024

Messages : 352

nombre de nombres premiers

Amis des défis amusants, bonjour.

Tiens, rigolo, pour un nombre de chiffres donnés, il s'agit de trouver un nombre qui contient le plus de 'sous-nombres' premiers - des nombres formés de chiffres consécutifs.

▼Exemple

1373
Sous-nombre | Premier ?
--------------------
1          | Non
3          | Oui
7          | Oui
3          | Oui
13         | Oui
37         | Oui
73         | Oui
137        | Oui
373        | Oui
1373       | Oui
--------------------
4 chiffres, 9 nombres premiers

31373
Sous-nombre | Premier ?
--------------------
3          | Oui
1          | Non
3          | Oui
7          | Oui
3          | Oui
31         | Oui
13         | Oui
37         | Oui
73         | Oui
313        | Oui
137        | Oui
373        | Oui
3137       | Oui
1373       | Oui
31373      | Non
--------------------
5 chiffres, 13 nombres premiers

Glozi

Invité

Re : nombre de nombres premiers

Bonjour,
Merci pour l'amusement,
Avec un code naïf j'arrive à aller jusqu'à 8 chiffres en base 10 (et ça prend plusieurs minutes dont une bonne partie pour faire un crible et trouver les nombres premiers).

▼j'obtiens

Avec 2 chiffres, maximum = 3 [23, 37, 53, 73]
Avec 3 chiffres, maximum = 6 [373]
Avec 4 chiffres, maximum = 9 [1373, 3137, 3373, 3733, 3797]
Avec 5 chiffres, maximum = 13 [31373, 37337]
Avec 6 chiffres, maximum = 17 [337397, 373373, 373379]
Avec 7 chiffres, maximum = 22 [3733797]
Avec 8 chiffres, maximum = 26 [20037337, 30373379, 37337397, 70373379]

En regardant les premiers nombres on se dit qu'il est peut-être possible d'obtenir un max avec $n+1$ chiffres en choisissant bien un max avec $n$ chiffres et en lui collant un chiffre bien choisi à droite. Ex : 37 -> 373 -> 3733 -> 37337 -> 373379 -> 3733797 mais cela s'écroule à partir de  8 chiffres. De même en regardant les premiers résultats on a l'impression qu'il n'y aura essentiellement que des chiffres impairs dans les nombres obtenus. Mais pour 8 chiffres on trouve par exemple 20037337 avec 3 chiffres pairs (dont deux zéros qui ne sont pas premiers...).

Bref une belle machine à détruire les conjectures !

▼code

##input
B=10 # base
N=6 #nb chiffres

from time import time

t1=time()
#crible
print("calcul des nombres premiers...")
P=[True for i in range(B**N)]
P[0]=False
P[1]=False
for i in range(len(P)):
    if P[i]:
        for j in range(2*i,len(P),i):
            P[j]=False

print("...crible terminé.")

L=[None for i in range(B**N)]
for i in range(B):
    L[i]=1 if P[i] else 0

for n in range(N-1):
    maxgen=0
    candidats=[]
    for u in range(B**n, B**(n+1)): #u a n+1 chiffres
        for digit in range(B):
            nouv=u*B+digit #nouv a n+2 chiffres
            tot=0
            for k in range(n+2):
                if P[B*(u%B**k)+digit]:
                    tot+=1
            L[nouv]=L[u]+tot
            if L[nouv]>maxgen:
                maxgen=L[nouv]
                candidats=[nouv]
            elif L[nouv]==maxgen:
                candidats.append(nouv)
    print("Avec", n+2, "chiffres, maximum =", maxgen, candidats)

t2=time()
print("durée : ", t2-t1)
 

Bonne journée

Ernst

Membre

Inscription : 30-01-2024

Messages : 352

Re : nombre de nombres premiers

Mais pour 8 chiffres on trouve par exemple 20037337 avec 3 chiffres pairs (dont deux zéros qui ne sont pas premiers...).

Bonsoir,

Ah oui, très bien ! J’ai été surpris de ces zéros à partir de huit chiffres, et je me suis rendu compte que j’ai oublié de préciser qu’il ne fallait pas les utiliser, sinon on obtient une sorte de ‘séparateur’ qui va valider un 37, un 037, un 0037 alors qu’on se les interdit en début de nombre parce qu’ils n’ont plus la bonne longueur.

Donc reformulation, désolé, pour un entier de longueur L composé de chiffres différents de zéro, on génère tous les nombres possibles formés à partir de ses chiffres consécutifs et on compte combien de ces sous‑nombres sont premiers.

Exemple pour 1373 :

1 chiffre → 1, 3, 7, 3
2 chiffres → 13, 37, 73
3 chiffres → 137, 373
4 chiffres → 1373

À part le 1, tous sont premiers, le score de 1373 est donc de 9.

Je suis en train de développer un code plus performant basé sur deux-trois idées :
- pré-calcul d'une table de nombres premiers (2, 3, puis les premiers parmi les multiples de 6±1, perte d'un peu de temps au début, mais plus rapide ensuite sur des milliers d'évaluations)
- construction des nombres dans un certain ordre ( 3, 7, 1, 9, 2, 6, 5, 4, 8) parce que je pense que ce sont les chiffres les plus prometteurs au début pour obtenir rapidement des records
- élagage en fonction des records déjà obtenus, c'est-à-dire que quand on construit un nombre, si le score partiel n'est pas assez élevé pour que le record soit accessible même si tout le reste est premier, autant arrêter cette construction et passer à la suivante

Avec ces ruses la longueur 9 devrait passer, la 10 peut-être aussi, après cela va quand même se gâter...

Rossignol

Membre

Inscription : 19-06-2015

Messages : 308

Re : nombre de nombres premiers

Ce problème distrayant a piqué par curiosité.
Le module sympy a une fonction isprime bien commode.
Pour afficher les sous-nombres, j'ai donc programmé ça :

#!/usr/bin/env python
# coding: utf-8

from sympy import isprime

def test(nombre):
    strnombre = str(nombre)
    n = len(strnombre)
    for i in range(1, n+1):
        for j in range(0, n+1-i):
            sous_nombre = int(strnombre[j:j+i])
            print(sous_nombre, 'OUI' if isprime(sous_nombre) else 'NON')      

test(12345)

Il est facile de montrer que les seuls nombres dont tous les sous-nombres sont premiers sont 2, 3, 5, 7, 23, 37, 53, 73, 373.

@+

Ernst

Membre

Inscription : 30-01-2024

Messages : 352

Re : nombre de nombres premiers

Bonjour,

En implémentant les diverses optimisations dont j’avais parlé, on arrive à aller plus loin, yé !

▼L = 9

Avec 9 chiffres, maximum = 30 [113733797, 233133733, 373373977, 733133733]

Je suis d’ailleurs surpris de ce '2', pensant qu'au fil de la progression il ne resterait plus que des 1, 3, 7 et 9...

Pour ceux que cela intéresse :

▼Python

import time

# ============================================================
# BLOC 1 : PRÉ-CALCULS
# ============================================================

def preparer_outils(L):
    limite_crible = int((10**L)**0.5) + 1
    crible = [True] * (limite_crible + 1)
    crible[0] = crible[1] = False
    for p in range(2, int(limite_crible**0.5) + 1):
        if crible[p]:
            for i in range(p * p, limite_crible + 1, p):
                crible[i] = False
   
    liste_p = [p for p, est_p in enumerate(crible) if est_p and p > 0]
    cache = {p: True for p in liste_p}
    cache.update({0: False, 1: False, 4: False, 6: False, 8: False, 9: False})
   
    puissances = [10**i for i in range(L + 2)]
    return liste_p, cache, puissances

# ============================================================
# BLOC 2 : TEST DE PRIMALITÉ
# ============================================================

def est_premier(n, liste_p, cache):
    if n in cache: return cache[n]
    limite = int(n**0.5)
    for p in liste_p:
        if p > limite: break
        if n % p == 0:
            cache[n] = False
            return False
    cache[n] = True
    return True

# ============================================================
# BLOC 3 : MOTEUR DE RECHERCHE
# ============================================================

def chercher(nombre_actuel, longueur, score_parent):
    global record_max, debut_chrono
   
    # Ordre optimisé
    for chiffre in (3, 7, 9, 1, 2, 5, 4, 6, 8):
        nouveau_nombre = nombre_actuel * 10 + chiffre
        nouvelle_long = longueur + 1
       
        points_gagnes = 0
        for i in range(1, nouvelle_long + 1):
            suffixe = nouveau_nombre % TABLES_10[i]
            if est_premier(suffixe, PREMIERS, CACHE):
                points_gagnes += 1
       
        nouveau_score = score_parent + points_gagnes
       
        # ÉLAGAGE
        total_max_possible = L_CIBLE * (L_CIBLE + 1) // 2
        deja_faits = nouvelle_long * (nouvelle_long + 1) // 2
        reste_a_faire = total_max_possible - deja_faits
       
        if nouveau_score + reste_a_faire < record_max:
            continue

        if nouvelle_long == L_CIBLE:
            if nouveau_score >= record_max:
                record_max = nouveau_score
                elapsed = round(time.time() - debut_chrono, 1)
                print(f"[{elapsed}s] {nouveau_nombre} [Score : {nouveau_score}]")
        else:
            chercher(nouveau_nombre, nouvelle_long, nouveau_score)

# ============================================================
# BLOC 4 : LANCEMENT
# ============================================================

L_CIBLE = 9  # C'est parti pour le défi !
record_max = 0
PREMIERS, CACHE, TABLES_10 = preparer_outils(L_CIBLE)

print(f"--- Recherche Longue Durée (L={L_CIBLE}) ---")
debut_chrono = time.time()

chercher(0, 0, 0)

print("-" * 30)
print(f"Terminé en {round(time.time() - debut_chrono, 2)} s")

Marrant, il semblerait que l'ordre des chiffres n'ait aucune incidence alors que je pensais vraiment élaguer plus vite...

Ernst

Membre

Inscription : 30-01-2024

Messages : 352

Re : nombre de nombres premiers

Bonjour,

Je reviens là-dessus, parce qu’en abandonnant l’exhaustif et en implémentant deux heuristiques on arrive à aller plus loin.

1) on supprime le 8 des chiffres à utiliser : gain 12,5 %

2) un élagage agressif : l'idée est d'abandonner une branche quand le score partiel ne permet plus d'atteindre le record même si tous les nombres restants étaient premiers.

On peut même faire un peu mieux en observant que quand L augmente, les records progressent de 5 ou 6 unités, jamais plus. En fixant le score max du niveau L comme étant le score du niveau (L-1) + 7, le programme peut valider des branches sans chercher davantage de score supérieur.

L = 9, [30], 0.7 s, (113733797, 233133733, 373373977, 733133733)
L = 10, [35], 1.7 s, (2113733797, 3733133733, 7331337337)
L = 11, [40], 4.4 s, (17331337337, 37331337337, 37337937337, 52379337397, 73312373373)
L = 12, [45], 10.4 s, (337331237337, 361373371973, 373312373373, 373313373379, 373363733797, 379719337397, 523793373973, 733123733739)
L = 13, [51], 16.3 s, (1117331337337, 3373312373373)
L = 14, [56], 42.1 s, (11173313373373, 31379719337397, 33733123733739)

Bon, cela dépend bien sûr de la machine, mais c'est quand même un progrès substantiel et le programme n'est pas si gros que cela. À suivre...

▼Python

import gmpy2, time

def res():
    L = int(input("L: "))
    chf, est_prem = [4, 6, 5, 2, 9, 1, 7, 3], gmpy2.is_prime
    t0, max_s, rec = time.time(), -1, []
    pile = [(0, [], 0, 0)]

    while pile:
        val, suf, sc, d = pile.pop()
        if sc + (L - d) * 7 < max_s: continue

        if d == L:
            if sc > max_s: max_s, rec = sc, [val]
            elif sc == max_s: rec.append(val)
            if sc >= max_s: print(f"{val}, [{sc}], {time.time()-t0:.1f} s")
            continue

        for c in chf:
            n_val, n_sc, n_suf = val * 10 + c, sc, [c]
            if est_prem(c): n_sc += 1
            for s in suf:
                comb = s * 10 + c
                if est_prem(comb): n_sc += 1
                n_suf.append(comb)
            if n_sc + (L - d - 1) * 7 >= max_s:
                pile.append((n_val, n_suf, n_sc, d + 1))

    print(f"\nL = {L}, [{max_s}], {time.time()-t0:.1f} s\n{', '.join(map(str, sorted(rec)))}")

if __name__ == "__main__":
    res()