Conjecture amusante sur les nombres premiers

[TFaurot]

Bonjour,

En m'amusant avec des suites récurrentes je suis tombé sur un truc rigolo qui m'amène à formuler la conjecture suivante :

Soit racine positive dans du polynôme défini sur .
Soit racine positive dans du polynôme défini sur .
Soit la fonction de vers qui projette tout élément de sur l'élément de le plus proche.

pour tout de :

si et seulement si et , alors est un nombre premier.



et sont respectivement et et leurs puissances arrondies forment des suites récurrentes que j'utilise pour tester la conjecture avec cet algorithme ( en Python ):

SuitePhi = [1,2] # Contient les derniers éléments de la suite des puissances arrondies de phi avec A(phi^0) = 1 et A(phi^1) = 2
SuitePsi = [0,0,0,0,1,2] # Contient les derniers éléments de la suite des puissances arrondies de psi avec A(psi^0) = 1 et A(psi^1) = 2
nCible = 500
Solutions = []
n = 1

while n <= nCible:
    #la suite des puissances arrondies de phi est une suite récurrente d'ordre 2 et de facteurs {1,1} donc S(n+1) = S(n) + S(n-1)
    SuitePhi.append( SuitePhi[-1]+SuitePhi[-2] )
    SuitePhi.pop(0)
    #la suite des puissances arrondies de psi est une suite récurrente d'ordre 6 et de facteurs {1,1,1,0,0,1} donc S(n+1) = S(n) + S(n-1) + S(n-2) + S(n-5)
    SuitePsi.append( SuitePsi[-1]+SuitePsi[-2]+SuitePsi[-3]+SuitePsi[-6])
    SuitePsi.pop(0)
    n += 1

    #des actions "d'accordage" sont nécessaires lors des premiers n pour mettre les suites sur les "bonnes tonalités"
    #Pour la suite de Phi il faut -1`à n = 3
    #Pour la suite de Psi il faut -1 à n = 6 et +1 à n = 3 , 5, 10, 12, et 14.
    if n == 3 :
        SuitePhi[-1] += -1
        SuitePsi[-1] += 1
    elif n == 6 :
        SuitePsi[-1]+=-1
    elif n in [ 5,  10, 12, 14 ]:
        SuitePsi[-1]+=1

    #A partir de là, les derniers éléments des listes SuitePhi et SuitePsi sont respectivement A(phi^n) et A(psi^n), on regarde les modulos.
    if SuitePhi[-1]%n == 1 and SuitePsi[-1]%n == 2:
        Solutions.append( n )

En comparant ensuite la liste des solutions avec une liste générée par un crible classique, j'ai testé jusqu'à n = 5000000 et aucun contre-exemple n'est sorti jusque là.
il faudrait arranger l'algorithme pour tester vraiment loin parce qu'il est lent ( +1h30s pour tester jusque là ! ).

J'ai cherché sur internet si ce résultat était connu, je n'ai rien trouvé à part que ça a l'air d'être une variante du Petit théorème de Fermat avec deux "a" irrationnels particuliers qui se corrige mutuellement vis-à-vis des pseudo-premiers, comme si les 2 suites générées à partir d'eux étaient "intriqués" de manière à ne jamais "sortir de pseudo-premiers" simultanément quand on les "teste modulo n".

voilà ! Pour ceux parmi vous qui s"intéressent aux nombres premiers il y a peut-être quelque chose à creuser de ce côté.

Merci de votre attention.
-----

[Médiat]

Bonjour,

Vous êtes sûr que cela marche pour n = 5 ?

[gg0]

Bonjour.

Les puissances de arrondies sont les nombres de Lucas, qui servent dans certains algorithmes de recherche de grands nombres premiers, me semble-t-il. Il est possible que ait des propriétés analogues.
Connais-tu les suites de Lucas et leurs propriétés ?

Cordialement.

Comment fais-tu pour éviter les problèmes d'arrondi

[gg0]

Pour 5, il y a effectivement un problème (restes 1 et 3) ; pour 113, les restes modulo n sont 95 et 1, or 113 est premier.

Cordialement.

[A voir en vidéo sur Futura]

[gg0]

Problème encore pour 31 et 37.

Comme ce ne sont pas vraiment les puissances qui sont utilisées, mais des suites d'entiers, ce qui est calculé dans l'algorithme n'est probablement pas les arrondis des puissances de phi et psi, mais autre chose (pour 5, ce n'est pas le nombre le plus proche, mais l'entier par défaut).

[Médiat]

Pour 113 je trouve bien 1 et 2, mais pour 137 et 139 je trouve 1, 9 et 1, 26, mais je soupçonne avoir atteint les limites de calcul de mon système

PS 31 et 37 sont ok pour moi

[gg0]

J'ai utilisé les puissances de phi et psi, arrondies au plus proche, modulo n, avec Maple. Il semble que ça ne pose pas trop de problème pour phi, mais ça dérape pour psi.

Mais comme l'algorithme n'utilise pas le calcul des puissances, ce sont les suites utilisées qui sont à considérer.
Ça me fait fortement penser aux techniques sur la primalité des nombres de Mersenne.

Cordialement.

[Médiat]

J'ai utilisé sql Oracle avec 38 chiffres significatifs, mapple je ne connais pas la précision ...

Cordialement

[TFaurot]

Vous êtes sûr que cela marche pour n = 5

Non ça ne marche pas pour 5 mais j'ai bien marqué strictement plus grands que 5

Les puissances de arrondies sont les nombres de Lucas, qui servent dans certains algorithmes de recherche de grands nombres premiers, me semble-t-il. Il est possible que ait des propriétés analogues.
Connais-tu les suites de Lucas et leurs propriétés ?

Non mais je vais fouiller, merci pour l'info.

Pour 113 je trouve bien 1 et 2, mais pour 137 et 139 je trouve 1, 9 et 1, 26, mais je soupçonne avoir atteint les limites de calcul de mon système

Justement, je n'y connais pas grands chose sur les possibilité de calcul des différents langages au niveau de la taille des nombres, j'utilise python parce que si on reste dans les entiers il n'y a pas de limite à part l'espace mémoire.