Factoriser sans difficultés, N = P1 . P2 produit de deux nombres premiers impairs (P2>P1), est une quête, fil rouge de tous mes calculs depuis 2005.
Un de mes angles d'attaque (2010-2011) a été de considérer que plutôt que de s'acharner sur le nombre N, il pourrait être plus intéressant de chercher un nombre N' avec lequel il aurait un facteur commun permettant un calcul du PGCD <> 1.
Après avoir pensé au difficilement calculable N!, puis à | N^(1/2) |!,
Il m'apparut évident que le produit des nombres impairs successifs inférieurs à la racine carré de N, était le meilleur candidat à soumettre à ma quête d'algorithme efficace et donc polynômial... Ce produit passait nécessairement par le plus petit des deux facteurs, voire dans le cas d'un nombre composé de plus de deux facteurs par le plus petit des deux produits de facteurs pouvant être issus d'une répartition au sein d'un de mes premiers "amours" de calculs ( avec les suites PJBOADL), à mon sens intrigants:
- L'équation du IInd degré X^2 +/- (S).X + N = 0,
mais sous la forme X^2 +/- (DeltaNOIR).X - N = 0, avec le DeltaNOIR = (P2 - P1) que j'entrevoyais même légitimer la normalité de la nature de l'équation de Frey intervenue comme une des étapes de la démonstration du Grand Théorème de Fermat par Wiles. Cette équation ayant été montrée comme étant non modulaire par Ken Ribet...
La répartition des facteurs en deux produits de facteurs, au sein des deux solutions de l'équation du IInd degré, crée toujours un équilibre de telle sorte que le DeltaNOIR soit le plus petit possible. Une caractéristique que je mis à contribution lorsque je chercha à résoudre le problème du TSP réduit à un problème de factorisation...
Comme souvent, j'aime partir de choses simples (voire même "bêtes") et notamment d'un exercice qui revient souvent, en l'occurrence, la recherche de règles au sein d'une succession de valeurs numériques déjà connues ou mises en évidence par la déstructuration d'un "amas" numérique, même ordonné mais sans transparence, que l'on cherche à "aligner" au sein d'un polynôme dont les coefficients seraient faciles à calculer. il est permis de rêver. Non?
J'eu un beau frisson en atteignant, sur la base d'analyses faite jusqu'à n=21 en étant conscient que l'algorithme atteint serait censé fonctionner, du fait de la structure observée et traitée, pour une valeur n (impair)>15:
Produits de impairs (=>n) =
45045 * (n^2 - 2.n ) * ( 2 . 3^((3*n-49)/2) + 3^(n-16) - 3^((n-15)/2) ) / (n-15)
Avec évidemment, vu les 2 premiers multiplicandes, ce que j'appellerai la structure (A) :
3 * ( Prod des impairs de (15) à (n-4) ) =
( 2 . 3^((3*n-49)/2) + 3^(n-16) - 3^((n-15)/2) ) / (n-15)
Un frisson qui dura le temps de vérifier le calcul pour (n)={17,19,21}
Autant dire que le sort du monde fut sauvé (rien à craindre! je suis chrétien...) lorsque l'algorithme devint inexacte dès la valeur impaire "23" en finissant rapidement par trop sous-estimer la valeur du produit avec n qui augmentait.
Après avoir cru à une erreur de ma part, il était clair que l'algorithme ne pouvait être généralisé. La factorisation d'une succession de résultats obtenus par des "Solve", connaissant la valeur du produit à atteindre, mis en évidence le fait que la structure (A) n'était pas conservée.
Mais l'échec était trop beau pour que la solution, selon moi, ne soit pas dans les parages. Le genre de pensées qu'il ne faut pas avoir si l'on est un "gros dormeur"; ce que je ne suis absolument pas...
Je me mis, à l'instar...d'Einstein, à la recherche d'une valeur correctrice!
Une variable qui rétablirait l'ordre, si je puis dire. Connaissant les valeurs que peut prendre (A), je testa l'inconnue partout entre et en dehors des parenthèses dans l'espoir de créer une succession de valeurs numériques qui répondrait à une récurrence évitant notamment le calcul de factorielles; sûrement la "mauvaise herbe" en théorie des nombres.
Allant jusqu'à me poser une question qui donnera naissance à une belle formule (B) qui ne résout rien et ne diminuera pas le degré de complexité mais qui est du genre à entériner l'idée de l'existence de structures cachées à découvrir et à exprimer:
Pourquoi ces puissances de 3? Une autre valeur était-elle possible? Puisque l'algorithme fonctionnait pour trois valeurs (17,19,21), peut-être existait-il, avec un pas de trois, un cycle de variables?
Ainsi naquît pour n = 17 + k.6 :
(le produit des impairs => n +/- {2 ou 4} étant ajusté par une multiplication ou une division)
45045 * (n^2-2.n) * 3^(k+1) * Prod( Som (429 + 394.x + 360.y + 432.z ) )
avec Produit pour (x) de 1 à k = (n-17)/6 ; y = x.(x+1)/2 et z = somme des triangulaires (1 à x) dont formule dépend de la parité de (x).
Afin d'obtenir cela, j'ai dû mettre en récurrence les valeurs que prenait une variable remplaçant "3":
x={3,14535,175510125,4260157264125,182057820682381875,...}
correspondant à n={17, 23,29,35,41,...}
avec x2=x1.(3.1615) ; x3=x2.(3.4025) ; x4=x3.(3.8091) ; x5=x4.(3.14245) ...
Exemple avec n=29. Rq: En testant g2=0 on évite numérateur nul avec x<>1
- A la rechercher de la variable correctrice pour n impair > 39
au sein de (A): ( 2 . 3^((3*n-49)/2) + 3^(n-16) - 3^((n-15)/2) ) / (n-15)
1ère solution intéressante mais qui reste approximative à cause de b moins stable que a:
Considérer deux variables (a,b) notamment pour n impair >39
( (2+a).3^((3.n - 49 + b)/2) + 3^(n-16) - 3^((n-15) /2)) / (n-15)
a = 3,3 + 1,2 * x + 0,4 * y + 0,1 * z
avec la même idée de triangulaire (en y) et somme de triangulaires (en z)
b = 19.10^(-3) + h.9.10^(-2) + 10^(-1).h.(h-1)/2
h = ( n - 41 ) / 2
Algo pour la variable (a) de la 1 ère solution. Pour n=43=2.i+1 et g =z , a0 = 5,1
2ème Solution
Produit des impairs =
45045 * ( n^2 - 2.n + c ) * ( 2.3^( (3.n - 49)/2 ) + 3^(n-16) - 3^(n-15)/2 ) / (n-15)
Créer une variable "c", ma préférée, car la première à m'avoir donné de grandes espérances. Elle ne conduit cependant pas à des résultats suffisamment exacts mais génère une suite de valeurs que j'aie cru un temps avoir mis en récurrence par un calcul très séduisant que j'appelle le "ruisseau" mais qui a fini par s'écarter du bon chemin.
Mais je suis sur une piste... Du moins quand cela me dit (..ces calculs datent de 2011). Difficile à confirmer, elle demande de générer une pyramide de nombres (heureusement par sommation où intervient la pyramide de Pascal) ayant n-étages et qui croît plus rapidement que ma précédente tentative et dont le résultat final sous-estimera nécessairement beaucoup moins le produit d'impairs attendu.
Ces solutions ne sont que des angles d'attaques qui n'atteignent pas l'exactitude numérique nécessaire au calcul d'un PGCD "utile".
Qu'en est-il à l'infini
FRANCILLETTE Thierry Jules
