Racines carrées et nombres premiers

[Malefix]

Bonjour,

J'ai établi une conjecture concernant les nombres premiers et je l'ai testée numériquement jusqu'à de grands nombres. J'aimerais avoir votre avis, c'est-à-dire : est-ce facile à démontrer ou pas, est-ce déjà existant, la conjecture est-elle vraie ?

---

Définitions :

Soit la somme des carrés des diviseurs de n. Par exemple
Maintenant que nous avons défini il nous reste à définir la fonction de compte de nombres premiers que l'on nommera
Plus précisément est le nombre de nombres premiers inférieurs ou égaux à n.
Pour finir on utilisera aussi la fonction somme des diviseurs de n, notée

Conjecture :

On pose l'expression A suivante :


Lorsque le nombre retourné se finit par un 2, on lui soustrait 1 et on obtient donc un nombre se finissant par 1.
On prend ensuite la racine carrée de ce nombre finissant par 1 et si on tombe sur un nombre entier alors ce nombre serait toujours un nombre premier.

Exemple :

On pose et on a donc
On a
On a ensuite qui est bien un nombre premier.
-----

[Malefix]

erratum : c'est bien et non

[Médiat]

Simple curiosité : qu'appelez-vous "grand nombre" (La conjecture de Syracuse a été vérifiée jusqu'à des nombres de l'ordre de ).
Quelle est la proportion de cas où est congru à 2 modulo 10 ?
Comment en êtes-vous arrivé à cette expression ?

[Biname]

Salut,
La conjecture suivante qui inclut la conjecture de l'énoncé est vraie pour 1 <= n <=1000000 (30 s de calcul avec le code ci-dessous)
Conjecture :

avec est la somme des carrés des diviseurs de n
Lorsque le nombre retourné se termine par un chiffre 2, on lui soustrait 1 et on obtient un nombre se terminant par 1.
On prend ensuite la racine carrée de ce nombre finissant par 1 et si on tombe sur un nombre entier alors ce nombre serait toujours un nombre premier.

Code Python vérifiant cette conjecture pour 1 <= n <= 1000000

 Cliquez pour afficher

import sympy
import math
import time

def sigma_2(n):
    """Calcule la somme des carrés des diviseurs de n en utilisant sympy."""
    diviseurs = sympy.divisors(n)
    return sum(d**2 for d in diviseurs)

def verifier_conjecture(n):
    global count_True, n_ok
    A = sigma_2(n)
    if A % 10 == 2:
        A -= 1     # avec A -= 3 retourne une conjecture FAUSSE pour n = 4655, 1 <= n <= 10000
        racine_A = int(math.sqrt(A))
        if racine_A * racine_A == A:
            resultat = sympy.isprime(racine_A)
            if resultat == True:  # conjecture vérifiee
                count_True += 1
                n_ok.append(n)
            return resultat
        else:
            return True     # A - 1 n'est pas un carré parfait, on considère que la conjecture ne s'applique pas
    else:
        return True         # Si A ne se termine pas par 2, on considère que la conjecture ne s'applique pas

# Test
n_min = 1
n_max = 1000000
count_True = 0
flag_false = False
n_ok =[]

start_time = time.time()

for n in range(n_min, n_max + 1):
    if not verifier_conjecture(n):
        print(f"La vérification de la conjecture pour n = {n} est FAUSSE")
        flag_false = True
        break
end_time = time.time()



if not flag_false:
    print(f"La vérification de la conjecture pour n >= {n_min} à n <= {n_max} est VRAIE {count_True} fois")

# option 
# print (f"\nValeurs de n verifiant la nouvelle conjecture\n{n_ok}")

elapsed_time = end_time - start_time
print(f"\nTemps de calcul : {elapsed_time:.6f} secondes")

print(f"\nFINISHED")

Sauf erreursss

[A voir en vidéo sur Futura]

[Malefix]

Merci à vous pour vos réponses et à Biname pour son code et son test.
Simple question : peux-tu tester avec de plus grands nombres ? Je suis nul en programmation.

La conjecture que je présente ici est-elle déjà existante ? Intéressante ?

[Malefix]

Finalement j'ai réussi à tester avec un compilateur en ligne. Mais je ne peux pas monter plus haut, sans doute à cause de la puissance limitée de nos ordinateurs.

[Ernum]

Salut,

Finalement j'ai réussi à tester avec un compilateur en ligne. Mais je ne peux pas monter plus haut, sans doute à cause de la puissance limitée de nos ordinateurs.

Sur mon portable avec 10⁶ (le maxi du programme initial) ça me prend 25s, avec 10⁷ :

La vérification de la conjecture pour n >= 1 à n <= 10000000 est VRAIE 332136 fois

Temps de calcul : 427.546771 secondes

Et on est encore loin de ce qu'on appelle un grand nombre (voir le post de Médiat).

[Malefix]

Salut Ernum,

Je trouve que c'est déjà un bon début. Peut-on en faire une démonstration ou bien c'est trop difficile ?

[Biname]

Salut,
Conjecture :

avec est la somme des carrés des diviseurs de n
Lorsque le nombre retourné se termine par un chiffre 2, on lui soustrait 1 et on obtient un nombre se terminant par 1.
On prend ensuite la racine carrée de ce nombre finissant par 1 et si on tombe sur un nombre entier alors ce nombre serait toujours un nombre premier.

Démo :

Le code montre que cette conjecture est vérifiée pour tous les nombres premiers se terminant par 1 ou 9, c'est trivial :

Le carré de ces nombres se termine toujours par 1 (1 × 1 = 1 et 9 × 9 = 81) ; étant des nombres premiers,
ils n'ont que deux diviseurs : 1 et eux-mêmes, donc la somme des carrés des diviseurs de ces est se termine toujours par 2

Ensuite, la conjecture soustrait 1 à , il reste ,
si la racine est un entier, alors est premier,
en effet, n est premier par définition.

CQFD

[Malefix]

En fait je viens de m'apercevoir qu'on ne parle pas de la même conjecture que celle de mon post.

En utilisant ma conjecture avec n=100547 :

On a :
On enlève 1 et on prend donc la racine de 8264809921, qui vaut 90911 qui est premier.

En utilisant ta conjecture avec n=100547 :


Il ne se termine pas par 2.

[Biname]

Salut,
Démo plus complète :

 Cliquez pour afficher

### Conjecture :

où est la somme des carrés des diviseurs de .

Lorsque le nombre retourné se termine par un chiffre 2, on lui soustrait 1 et on obtient un nombre se terminant par 1. On prend ensuite la racine carrée de ce nombre finissant par 1 et, si on tombe sur un nombre entier, alors ce nombre serait toujours un nombre premier.

### Réécriture avec des congruences :

Pour que soit la racine entière et première de , qui se termine toujours par 1 car A doit se terminer par 2, doit se terminer par 1 ou par 9. En termes de congruences, cela signifie que :



Il faut également que ce nombre soit premier. Donc, tous les nombres premiers se terminant par 1 ou 9 vérifient la conjecture.

### Raisonnement :

1. Si est un nombre premier se terminant par 1 ou 9, alors:
.

2. La somme des carrés des diviseurs de , qui est premier, est :

- Donc, .

3. Si se termine par 2 (ce qui se produit si se termine par 1), alors :
(car et ).

4. On soustrait 1 de :


5. Pour que soit la racine entière de , on a .

6. Si est un entier et est premier, alors est aussi un nombre premier.

Ainsi, le raisonnement est exact. Tous les nombres premiers se terminant par 1 ou 9 vérifient la conjecture, car leurs carrés se terminent par 1, ce qui conduit à étant un carré parfait dont la racine est un nombre premier.

### Démonstration que seuls ces nombres vérifient la conjecture :

Pour démontrer qu'aucun autre nombre ne vérifie la conjecture, considérons les autres cas où ne se termine pas par 1 ou 9.

- Si se termine par 0, 2, 3, 4, 5, 6, 7, ou 8, alors ne se termine pas par 1. En effet :
-
-
-
-
-
-
-
-

Puisque se termine par 2, cela ne peut arriver que si . Les seules valeurs de pour lesquelles sont celles se terminant par 1 ou 9.

Ainsi, aucun autre nombre ne vérifie la conjecture. CQFD.

Ce qui est vrai pour est aussi vrai à fortiori pour la conjecture d'origine .

Sauf erreursss

[gg0]

Bonjour Biname.

J'ai l'impression que tu fais ici un petit exercice d'arithmétique élémentaire, mais comme tu mélanges un peu tout, je suis perdu dans ta "démonstration". Quand je dis que tu mélanges, je veux dire que la preuve n'est pas construite depuis la ou les hypothèses pour arriver à une conclusion ("Ainsi la conclusion est exacte" n'est pas la conclusion, et d'ailleurs on n'a pas besoin de le dire, on rédige une preuve exacte ou ça ne sert à rien).
Inutile de perdre du temps sur les évidences (comme le fait que seuls les nombre finissant par 1 ou 9 ont un carré qui se termine par 9 - niveau fin d'école primaire), mais une rédaction organisée, de la forme (si j'ai bien compris ton sujet) :
* Soit n un entier finissant par 1 ou 9. Soit S la somme des carrés de ses diviseurs. On suppose ... (là je ne sais plus ce que tu ajoutes comme hypothèse, j'ai l'impression que tu as utilisé le fait que n est premier).
*.... (le corps de la preuve, où chaque ligne est une conséquence des précédentes)
* donc n est premier.

Évidemment, si ce n'est pas cette conclusion, à toi de changer, idem pour la première ligne, celle des hypothèses.

Sans ce type de rédaction, on ne fait pas des maths, on ne cherche pas vraiment à prouver aux autres.
Cordialement.

[Biname]

Salut,

Bonjour Biname.

J'ai l'impression que tu fais ici un petit exercice d'arithmétique élémentaire, mais comme tu mélanges un peu tout, je suis perdu dans ta "démonstration". Quand je dis que tu mélanges, je veux dire que la preuve n'est pas construite depuis la ou les hypothèses pour arriver à une conclusion ("Ainsi la conclusion est exacte" n'est pas la conclusion, et d'ailleurs on n'a pas besoin de le dire, on rédige une preuve exacte ou ça ne sert à rien).
Inutile de perdre du temps sur les évidences (comme le fait que seuls les nombre finissant par 1 ou 9 ont un carré qui se termine par 9 - niveau fin d'école primaire), mais une rédaction organisée, de la forme (si j'ai bien compris ton sujet) :
* Soit n un entier finissant par 1 ou 9. Soit S la somme des carrés de ses diviseurs. On suppose ... (là je ne sais plus ce que tu ajoutes comme hypothèse, j'ai l'impression que tu as utilisé le fait que n est premier).
*.... (le corps de la preuve, où chaque ligne est une conséquence des précédentes)
* donc n est premier.

Évidemment, si ce n'est pas cette conclusion, à toi de changer, idem pour la première ligne, celle des hypothèses.

Sans ce type de rédaction, on ne fait pas des maths, on ne cherche pas vraiment à prouver aux autres.
Cordialement.

L'énoncé n'est pas de mon cru, j'ai repris l'énoncé initial. Et, oui, c'est vrai c'est assez confus, mais si on veut comprendre, on peut comprendre.

Le plus simple :
Liste informatique des nombres correspondants à la conjecture, tous vérifient la conjecture pour 1<= n <= 1000000, n est ci-dessous limité à 1000

[11, 19, 29, 31, 41, 59, 61, 71, 79, 89, 101, 109, 131, 139, 149, 151, 179, 181, 191, 199, 211, 229, 239, 241, 251, 269, 271, 281, 311, 331, 349, 359, 379, 389, 401, 409, 419, 421, 431, 439, 449, 461, 479, 491, 499, 509, 521, 541, 569, 571, 599, 601, 619, 631, 641, 659, 661, 691, 701, 709, 719, 739, 751, 761, 769, 809, 811, 821, 829, 839, 859, 881, 911, 919, 929, 941, 971, 991]

On vérifie que tous sont premiers. On a tous les nombres premiers se terminant par 1 ou 9

[Biname]

Salut,
La conjecture est triviale elle dit en fait :
la racine carrée du carré d'un nombre premier est un nombre premier
==> la racine carrée du carré d'un nombre premier se terminant par 1 ou 9, est un nombre premier
==> le carré de ce nombre premier se termine par 1
==> si j'ajoute 1 au carré de ce nombre, le carré de ce nombre se termine par 2

... je vous laisse continuer, vous devriez arriver à la conjecture

[GBZM]

Bonjour,
Biname, relis le premier message, et en particulier l'exemple donné. Tu verras que tu te fourvoies complètement.

[MissJenny]

On pose l'expression A suivante :

il se peut que soit négatif. Comment définis-tu la valeur de sigma2 dans ce cas?

[Malefix]

Bonjour à tous et merci pour vos réponses.

@MissJenny : dans ce cas je prends la valeur absolue.

[Biname]

Salut,

Bonjour,
Biname, relis le premier message, et en particulier l'exemple donné. Tu verras que tu te fourvoies complètement.

Non, 'pour moi' n est la valeur du contenu de la parenthèse, quelle que soit la fonction dans la parenthèse, ce qui fait de 'ma' conjecture un cas général qui contient l'originale.

A = sigma²(n) pour tout n variant de 1 à l'infini.

Si tu penses qu'une fonction quelconque peut ajouter des entiers à cette plage ... ? En plus, s'il ne s'agit pas d'entiers, la conjecture les rejette.

[Biname]

Bonjour à tous et merci pour vos réponses.

@MissJenny : dans ce cas je prends la valeur absolue.

IIRC, la valeur dans la parenthèse est toujours négative jusqu'à un n fini ???n<=10000???

[Biname]

Salut,
Voici la liste des différences (A) toujours negative de la conjecture initiale pour n < 100 et le code

 Cliquez pour afficher

Liste des differences (=A) :
 [-4, -6, -4, -10, -5, -12, -9, -14, -8, -24, -9, -19, -18, -25, -12, -33, -13, -35, -24, -28, -16, -52, -22, -33, -31, -47, -21, -63, -22, -53, -37, -43, -37, -80, -27, -49, -44, -78, -30, -84, -31, -71, -64, -58, -34, -110, -42, -78, -57, -83, -39, -105, -56, -104, -64, -74, -44, -152, -45, -79, -86, -109, -66, -126, -50, -108, -77, -125, -53, -176, -54, -94, -103, -119, -75, -147, -59, -165, -99, -104, -62, -202, -85, -109, -97, -157, -67, -211, -88, -144, -104, -120, -96, -228, -74, -147, -131, -192, -77, -191]

import sympy
import math
import time

def est_premier(num):
    """Vérifie si un nombre est premier en utilisant sympy."""
    return sympy.isprime(num)

def sigma(n):
    """Calcule la somme des diviseurs de n en utilisant sympy."""
    diviseurs = sympy.divisors(n)
    return sum(diviseurs)

def pi(n):
    """Calcule le nombre de nombres premiers inférieurs ou égaux à n en utilisant sympy."""
    return sympy.primepi(n)

def verifier_conjecture(n):
    global list_A
    pi_n = pi(n)
    sigma_n = sigma(n + 2)
    difference = pi_n - sigma_n
    abs_difference = difference
    list_A.append(difference) 
    return difference

# Mesurer le temps d'exécution
debut_temps = time.perf_counter_ns()

# Tester la conjecture pour les valeurs de 100000 à 102000
list_A = []
n_min = 1
n_max = 100
for n in range(n_min, n_max + 1):
    difference = verifier_conjecture(n)
    if difference > 0:
        print (f"Difference > 0 trouvée pour n = {n}")
        break
# Fin de la mesure du temps
fin_temps = time.perf_counter_ns()
temps_ecoule = (fin_temps - debut_temps) / 1000

if n_max - n_min < 201:   # eviter une liste de 1000000 de valeurs
    print(f"Liste des differences (=A) :\n {list_A}")

print(f'Temps de calcul : {temps_ecoule/1000:.3f} millisecondes')
print("FINI")

Jusqu'à 20000, aucune valeur positive de la parenthèse n'est calculée.

[GBZM]

A = sigma²(n) pour tout n variant de 1 à l'infini.

Alors tu devrais montrer que pour tout entier , en posant , si se termine par 1 et est le carré d'un entier, alors cet entier est premier.
Ce n'est pas du tout ce que tu fais : tu remarques juste que si est premier, alors .

[Biname]

Alors tu devrais montrer que pour tout entier , en posant , si se termine par 1 et est le carré d'un entier, alors cet entier est premier.
Ce n'est pas du tout ce que tu fais : tu remarques juste que si est premier, alors .

C'est exactement ce que je fais, il faudrait relire et faire l'effort de comprendre. Commence par la liste msg #13, là, c'est lumineux.
Et puis msg #9 et/ou 11#

[Biname]

En ajoutant les conditions de l'énoncé initial,
A = sigma²(n'importe quelle fonction, Somme, Produit de n entier ici) est vérifiée pour toutes valeurs de 1 <= n <= infini

[GBZM]

C'est exactement ce que je fais,

Non, j'ai bien relu et ce n'est absolument pas ce que tu fais.
Ce que tu fais, je répète, c'est de dire que si est un premier qui se termine par 1 ou 9, alors en posant , se termine par et est un entier premier (égal à ).
Ce qu'il faudrait faire, c'est de montrer que pour tout entier , en posant , si se termine par 2 et est un entier, alors cet entier est premier.
Tu ne vois vraiment pas la différence ?

[Biname]

Non, j'ai bien relu et ce n'est absolument pas ce que tu fais.
Ce que tu fais, je répète, c'est de dire que si est un premier qui se termine par 1 ou 9, alors en posant , se termine par et est un entier premier (égal à ).
Ce qu'il faudrait faire, c'est de montrer que pour tout entier , en posant , si se termine par 2 et est un entier, alors cet entier est premier.
Tu ne vois vraiment pas la différence ?

Ah, déjà tu as admis que A = sigma²(n), plus les conditions 'initiales' est 'majorant' de la conjecture (je te laisse trouver un mot mieux adapté), on progresse.
Faut que je relise ...

[GBZM]

Ben oui, fais un effort pour relire et comprendre ...

[GBZM]

J'ai fait un petit test avec Sagemath : je prends les entiers tels que , je regarde si se termine par le chiffre et si est entier et dans ce cas je regarde si est premier.

def test(N,f) :
    s=0 ; t=0
    for n in range(2,N) :
        A=sigma(n,2)
        if (A%10==f and is_square(A-1)) :
            s+=1
            e=sqrt(A-1)
            if not(is_prime(e)) :
                   t=n
                   break
    if t>0 :
                   print("échec pour n = {}, sqrt(A-1) = {}".format(n,e)) 
    else :
                   print("Testé jusqu'à {} :\n\
OK pour {} entiers vérifiant les conditions".format(N,s))

Maintenant :

%time test(10000000,2)

Testé jusqu'à 10000000 :
OK pour 332136 entiers vérifiant les conditions
CPU times: user 2min 13s, sys: 67.3 ms, total: 2min 13s
Wall time: 2min 13s

Les 332136 entiers vérifiant les conditions sont en fait les premiers se terminant par 1 ou 9 plus tetits que 10000000.

Par contre :

%time test(1000000,0)

échec pour n = 2696, sqrt(A-1) = 3107
CPU times: user 46.4 ms, sys: 12 µs, total: 46.4 ms
Wall time: 45.9 ms

[Biname]

Il faut prouver que si n n'est pas premier, la conjecture le rejette.
La liste les rejette tous, ça ne prouve rien, mais c'est encourageant

n non premier ==> n = a * b * 1 avec a = b possible, on s'occupera de a^n plus loin
A = sigma²(n) = a² + b² + 1
Si A mod 10 = 2 on soustrait 1 à A (si non, n est hors conjecture)

On a A - 1 = a² + b²

il faut que sqrt(a² + b²) soit entier et premier pour être 'dans' la conjecture

3 et 4 ==> 5 mais 25 + 1 = 26 ne se termine pas par 2

???? à continuer

Pour n = a^n
sqrt(a^n - 1) n'est jamais entier n = a^n est donc hors conjecture

Il reste à prouver que si sqrt(a² + b²) est entier a² + b² + 1 ne se termine jamais par 2

Sauf erreurs

[Biname]

[QUOTE=GBZM;7227020]
Les 332136 entiers vérifiant les conditions sont en fait les premiers se terminant par 1 ou 9 plus petits que 10000000.
/QUOTE]
Ce n'est pas un scoop, Biname msg #9

[GBZM]

Bon, on progresse, tu as compris que tu n'avais pas montré ce qu'il fallait.
Après, ça part plutôt mal. Si avec et premiers distincts, alors .