Overblog Suivre ce blog
Editer l'article Administration Créer mon blog

yoyoSpire

yoyoSpire

La résolution d'une gestion des très grands nombres est une des clés d'un futur vers l'Espace pour l'humain. Nombres premiers obligent... Toutefois, si un rêve se construit au jour de nos vies, nos vies ne sont pas plus des décharges publiques que notre belle planète bleue. Et les bleues des coups qu'elle reçoit, moi, j'en peux plus ! Aussi j'agrémente le rêve d'un ciel plus haut, de quelques véhementes objections


Nombre Premier

Publié par yoyospire sur 21 Juin 2012, 08:48am

Catégories : #Science, #Nombres Premiers, #Math, #Informatique, #Programmation, #Algorithme

Nombre Premier

THEORIE DES NOMBRES 

 

Ce travail propose une nouvelle approche de l’observation des nombres et principalement des nombres premiers.

Il repose également la façon d’aborder la factorielle.

Ce travail dépend d’un axiome inédit.

 

Je vous fais part de ce travail car la conclusion est :

- résolution de la factorielle en temps polynomial exécutable.

- détermination de tous facteurs premiers en temps polynomial exécutable.

 

PLAN

 

-           l’axiome

-           les nombres premiers

-           extension du théorème de Wilson (sans les modulo)

-           programme de décomposition en facteurs premiers (avec la factorielle)

-           résolution du problème de la factorielle en temps polynomial exécutable

-           conclusion

 

 

L’AXIOME

 

L’axiome inédit repose sur un interdit.

Ordinairement           na ≠ an ≠ n * a

Cette vérité n’est pas remise en cause.

Mais lorsque je rencontre la formule           N / a = p          où        (N,a) Є N* et p est premier

Alors je considère que           a * p = pa

De même, lorsque je rencontre        N = pa                            , j’utilise judicieusement la formule  a * p.

 

_____________________________________

 

Le bénéfice de l’utilisation judicieuse de cet interdit m’est apparu alors que j’explorais Fermat (x2 + v2 = z2) et Gauss (Un = U0 + n * r) sur les termes consécutifs d’une suite arithmétique.

J’en ai déduit deux nouvelles équations et une constante fonctionnant parfaitement avec cet interdit. Equations que j’ai appelées Gauss 1 et 2.

------------------------------------

 

Gauss 0 :         Un  = Up + ( n – p ) * r            Un + 1 = Un + 1

 

------------------------------------

                             pair jusqu’à (n – 1) membres

Gauss 1 :         Un = ∑ + ( n – 1 )                   Un + 1 = Un + 2n + 1  

                             2

 

-----------------------------------

                            6 (n-n)

Gauss 2 :         Un = ∑                + 1 

                             6(n-1)

 

------------------------------------

 

Pour Gauss 2, Un est différent selon n = pair ou n = impair

=>  Un(pair) = [ 7 + 7 ( n – 2 )] + [ C ] * [ ( n – 1 ) + ( n / 2 )2 + 2 [ 2 ( n – 2 ) + 3 ( n – 3 ) + … + ( n2 / 4 – 1 )]]

 

=>  Un (impair) = [ 7 + 7 ( n – 2 )] + [ C ] * [ ( n – 1 ) + 2 [ 2 ( n – 2 ) + 3 ( n – 3 ) + 4 ( n – 4 ) + … + (( n2 – 1) / 4 )]]

 

=>  Ou C est la constante pour quelque soit nx               C nx = x * nx-1             S C nx = ( x – 1 ) !

Si ce travail vous intéresse, faites m’en part et je vous le communiquerais.

 

_________________________________________

 

Ce qu’il faut donc comprendre c’est que :

Quelquesoit N Є N*               N = p1a * p2b * p3c * … * pxz

 

Où ordinairement le plus grand facteur de N est :

P1a       si           p1a > p2b > …

P2b       si         p2b > p1a > …

P3c        si         p3c > p2b > …

pxz        si         pxz > p2b > …

Devient ici, le plus grand facteur de N est :

a * p1              pour    p1a      

b * p2              pour    p2b      

c * p3               pour    p3c

z * px               pour    pxz                   

 

 

Cet axiome « interdit » se révèle très opérationnel dans le programme que j’utilise pour la décomposition en facteurs premiers, issu d’une extension du théorème de Wilson.

 

 

LES NOMBRES PREMIERS

 

1° /   Quelquesoit   N, un nombre,    N  Є  N  *         et Ni un nombre impair,        Ni  Є N*         

N est pair ou impair

Si N est pair                N = 2n * Ni                              où        n   *

Si N est impair            Ni =      - ni1 * ni2

                                ou        - ni1ni2

                                ou        - ni2ni1

Bien sûr          ni1 * ni2  ≠ ni1ni2 ≠  ni2ni1

 

En fait, il faut comprendre que quelque soit Ni il est uniquement composé de facteurs premiers, d’où

            -    p1  * p2

Ni =      -    p1p2

           -    p2p1

 

plus généralement,  le nombre de facteurs premiers :

Ni = p1 * p2 * … * px

Ni = p1a * p2b * … * pxz

 

Donc le plus grand facteur de Ni n’est pas forcément premier, pourtant… il l’est effectivement mais de façon discrète, sous la forme ( a * p ) pour ( pa ) ou ( ap ).

 

Note : si le plus grand facteur de Ni est pair, cela est aussi vrai :

N.gif

 

le plus grand facteur pair est de la forme :  ( 2n * p ), donc (n2.gif )

 

 

 

 

2°/ Donc,

Quelquesoit Ni Є N*, on sait que Ni est de la forme p1a * p2b * … * pxz        où { a, b, …, z } Є N*

Et que le plus grand facteur de Ni est de la forme ( a * p1 ) ou ( pm ), si pm > a * p1

[ ici pm est un facteur premier à la puissance 1 ]

Note :

il se peut que a * p1 > b * p2 > … > z * px                                 

ou bien que     a * p1 < b * p2 > … > z * px

=> b * p2 est alors le plus grand facteur de Ni

ou bien que                a * p1 < b * p2 < … < z * px

=> z * px est alors le plus grand facteur de Ni

 

3°/ Attention,

Il ne faut pas confondre un facteur premier avec sa puissance impaire ; soit 37 ≠ 73

Cet axiome inédit / interdit, je ne l’utilise que dans mon programme de décomposition où le plus grand facteur est forcément de la forme ( a * p ) quand a * p = pa     et où    a Є  N*

a peut être égal à 1 comme il peut être égal à 157, 157 étant premier lui-même.

Or,       a * p = pa         ou       a * p =  ap                   jamais les deux à la fois

Il est facile de vérifier :         si         N / ap = décimal         a * p = pa

                                       Si         N / pa = entier            a * p = pa

 

Bien sûr, dans un nombre N quelconque on rencontrera souvent que N est composé autant de ab que de ba

Il n’est pourtant pas utile de s’inquiéter puisque nous travaillons sur le plus grand facteur de N,

ab > ba             ou        ba > ab             mais jamais égal.

 

 

 

THEOREME DE WILSON

 

Reprenons le théorème originel de Wilson, c’est-à-dire sans la forme modulo, soit :

( x – 1 ) ! + 1 = y * x               où        x est premier              et         y est impair

 

En reprenant la construction de la factorielle qui vérifie cette équation, on remarque qu’il est possible de considérer deux extensions à ce théorème :

a/        ( x – 1 ) ! = ( y – 1 ) * x + ( x – 1 )

b/        ( x – 2 ) ! = { [ ( y – 1 ) / ( x – 1 ) ] * x } + 1

Je trouve cette seconde formule très intéressante parce qu’elle introduit une constante + 1 à l’équation, quelque soit le nombre premier x.

 

Voilà le raisonnement que je me suis tenu ; il est approximatif, mais donne un résultat très fonctionnel

Soit un nombre Ni = p1a * p2b * p3c

-           Considérons que ce nombre Ni est de la forme ( y * x ) avec x premier et y impair

-           Considérons maintenant que x premier est  présent en y impair :

un nombre a de fois pour p1,             soit      a * p1

un nombre b de fois pour p2,            soit      b * p2

un nombre c de fois pour p3,             soit      c * p3

-           Cherchons le plus grand facteur de y pour un x premier :

a * p1 < c * p3 < b * p2

-           Utilisons ce facteur dans la formule b/ ( x – 2 ) ! et divisons le par Ni

Soit      ( b * p2 ) ! / Ni

=>        le résultat est un entier

 Tout facteurs inférieurs [ ici, ( a * p1 ) et ( c * p3 ) ] utilisés comme factorielle divisée par Ni résulte un décimal.

 Tout [ ( b * p2 ) ! + n ] / Ni résulte un entier.

=>        le plus grand facteur de Ni de forme ( a * p ) est la limite entre entier et décimal sur la factorielle.

Ceci rejoint la démonstration de Adrien-Marie Legendre ( ∑ [ n / pi ], n > pi, pour n ! ).

 

 

PROGRAMME DE DECOMPOSITION EN FACTEURS PREMIERS

 

 

A         Soit :    =>        n / x = a

            Et       =>        E (a) ! / n = b

 

Si :       b est un entier            =>        (E (a) – 1) ! / n = c

Si :       c est un entier            =>        ( E (a)  – 2) ! / n = d               etc.

Reprendre avec (E (a) – x) ! , toujours sur n, jusqu’à ce que l’équation résulte un décimal non entier. (c’est pas le même x que pour l’équation de départ. x = nombre inconnu dans tous les cas).

Le plus grand nombre premier composant le nombre n est alors le nombre du factoriel précédent ce résultat . Soit : b – x + 1.

 

(11 – 1) ! / 35 = 103680

(11 – 2) ! / 35 = 10368

(11 – 3) ! / 35 = 1152

(11 – 4) ! / 35 = 144

(11 – 5) ! / 35 = 20.571…

Soit : 11 – 4 = 7,         7 est donc le plus grand premier du nombre n.

=>  35 / 7 = 5        =>        7 * 5 = 35

 

B          Soit :    =>        n / x = a

            Et :       =>        E (a) ! / n = b

Deux résultats pour b sont alors possibles :

 ou b est un entier, ou b est un décimal non entier.

Si b est un entier, il faut augmenter x et reprendre les deux opérations

Si b est un décimal non entier, il faut diminuer x et reprendre les deux opérations

Les deux membres premiers du nombre n s’affichent quand a de l’équation n / x = a est un entier, le dernier résultat entier avant que cette même équation (à : n / x + 1 ou n / x – 1, selon que tu montes ou descendes la progression) ne sorte un décimal non entier.

 

 

187 / 3 =  62.3333….

62 ! / 187 = entier                                         augmentons x de 3

187 / 6 =  31.16666….

31 ! / 187 = entier                                         augmentons x de 3

187 / 9 = 20.7777…..

20 ! / 187 = entier                                         augmentons x de 3

187 / 12 = 15.5888….

15 ! / 187 = décimal non entier                       diminuons x de 1

187 / 11 = 17                          la formule est trouvée !!

( ci-joint un autre dossier nommé Formule A & B, proposant en exemple d’autres cas)

 

Important :    ce programme sort tous les facteurs premiers possibles de n’importe quel nombre

Tout nombre quelconque se compose uniquement de facteurs premiers.

Ces facteurs premiers composant un nombre n quelconque sont en nombre inconnu. Lorsqu’ils appartiennent à la composition du nombre n quelconque, ils peuvent de surcroit se répéter chacun un nombre indéfini de fois.

Ex :      35 = 5 * 7                   2 facteurs premiers à la puissance 1 chacun

            45 = 3 * 3 * 7             2 facteurs premiers, 3 à la puissance 2, 5 à la puissance 1, soit 32 * 5

            97755 = 3 * 5 * 7 * 7 * 7 * 19                       31 * 51 * 73 * 191

 

=>  N = {p1a, p2b, …, pxx }   ou        N = p1a * p2b * (…) * pxx

 

=>  La difficulté réside donc, non pas dans le nombre de facteurs premiers puisqu’il ne s’agit que d’appliquer une itération à la résolution; mais dans le choix du diviseur de N, dans l’équation n / x de départ.

=>  Or, il existe une loi qui permet de contourner ce souci :

A/        le nombre factoriel que nous recherchons possède trois propriétés :

=>  Il est toujours le plus grand facteur du nombre N               ( axiome  pa = a * p)

=>  Il est de puissance 1, jusqu’à l’infini (ou dit x), soit px

=>  Il est lui-même composé d’un nombre inconnu de chiffre

 

B/        il faut jouer sur ces propriétés pour adapter x de n / x

=>  Si le plus grand facteur premier est de puissance 1, alors x s’adapte en fonction du nombre de chiffre qui le compose. En rapport avec N.

 

Procédure :     N est composé de y chiffres  =>       la factorielle recherchée est composée ≈ y / 2 chiffres

                        1/ Commencer avec 10 y/2     pour N / 10 y/2 = a       et E (a) ! / N    (formule B)

                        2/recommencer ensuite avec 10 puissance (y – 1 ) / 2

                        3/ recommencer ensuite avec 10 y/2 / 2

                        4/ recommencer ensuite avec 10 y/2 / 2 + 10 y/2 / 4

                        selon les résultats : entier ou décimal non entier, recommencer à varier y

Note 1 :           y peut être impair, 10 E (y/2) + 1

Note 2 :           Une fois le nombre de chiffre composant la factorielle recherchée trouvé, peut-être devient t-il plus judicieux d’augmenter ou diminuer la factorielle elle - même (formule A).

Soit      N / 10y/2 = a    =>        [ E ( a ) + x ] ! / N       ou        [ E ( a ) – x ] ! / N

 

=>  Si le plus grand facteur premier est de puissance supérieur à 1, alors il y a une astuce ….

 

Ici il faut réfléchir comme suit :        si le facteur le plus grand du nombre est un facteur premier à une puissance x, alors la résolution factorielle qui donne le facteur donne, et le facteur premier et sa puissance, sous la forme de l’ interdit, soit :  21 = 3 * 7, il faut comprendre alors 73 ou 37, là c’est       N / 73 ou N / 37 qui résulte un entier ou pas, et vérifie la formule.

Donc, si le plus grand facteur premier est de puissance supérieur à 1, il faut chercher x comme précédemment mais ne pas s’étonner de trouver un factoriel encore divisible, notamment par 2x, donc  un factoriel pair…, ou impair si la puissance du facteur premier est impair.

 

Note :  le RSA qui repose sa stratégie d’incassabilité par l’écart important entre un très très grand facteur et un beaucoup plus petit, devient avec ce programme tout à fait inopérationnel.

En effet, si N est composé de beaucoup de facteurs premiers, le programme recherche en commençant par le plus grand jusqu’au plus petit.

Mais quand N n’est composé que de deux uniques facteurs, le programme trouve l’un par l’autre, en même temps !

 

L’étude suivante élimine le problème de complexité algorithmique que pose la factorielle.

 

 

RESOLUTION DE LA FACTORIELLE EN TEMPS POLYNOMIAL EXECUTABLE

 

FACTORIELLES

 

Passer par la factorielle est de complexité super-exponentielle ( et non de complexité factoriel comme l’utilisation de Wilson par les modulo), ce qui rend tout programme rédhibitoire.

Pourtant, il existe un moyen de réduire considérablement le temps polynomial nécessaire au calcul de la fonction factorielle, en la construisant mécaniquement sans aucune opération multiplicatrice.

La mécanique est une fonction itérative qui ne fait appel qu’à la dernière écriture ( = derniers termes trouvés). Elle est composée d’identification de valeurs, les facteurs premiers, et d’additions sur leurs puissances (soit jamais plus de deux termes qui s’additionnent).

De plus, les facteurs utiles à l’opération sont identifiables de façon aussi simple qu’une autre addition à seulement deux termes, pour tout nombre pair et tout nombre premier.

Pour les nombres impairs, le programme précédent est utile, mais sans avoir à calculer la factorielle !

 

Voici le raisonnement

 

Tableau 1 de la factorielle

1                1          
2                2                                                               2
3                6                                                               2          3
4                24                                                             23         3
5                120                                                           23         3          5
6                720                                                           24         32         5
7                5040                                                         24         32         5          7
8                40320                                                        27         32         5          7
9                362880                                                      27         34         5          7
10              3628800                                                     28         34         52         7
11              39916800                                                   28         34         52         7          11
12              479001600                                                 210       35         52         7          11
13              6227020800                                               210       35         52         7          11        13
14              87178291200                                              211       35         52         72         11        13
15              1307674368000                                         211       36         53         72         11        13
16              20922789888000                                       215       36         53         72         11        13
17              355687428096000                                    215       36         53         72         11        13        17
18              6402373705728000                                  216       38         53         72         11        13        17
19              121645100408832000                             216       38         53         72         11        13        17        19

 

Tableau 2 de la factorielle

 

1      1
2      2
3      3 ≠ 2                                                                   21         31
4      4 = 2 * 2 = 22                                                     21 + 2     31
5      5 ≠ 2 ≠ 3                                                             23         31         51
6      6 = 21 * 31                                                          23 + 1     31 + 1     51
7      7 ≠ 2 ≠ 3 ≠ 5                                                      24         32         51         71
8      8 = 2 * 2 * 2 = 23                                               24 + 3     32         51         71
9      9 = 3 * 3 = 32                                                     27         32 + 2     51         71
10    10 = 21 * 51                                                       27 + 1     34         51 + 1     71
11    11 ≠ 2 ≠ 3 ≠ 5 ≠ 7                                             28         34         52         71         111
12   12 = 2 * 2 * 3 = 22 * 31                                      28 + 2     34 + 1     52         71         111
13   13 ≠ 2 ≠ 3 ≠ 5 ≠ 7 ≠ 11 ≠ 13                            210       35         52         71         111       131
14   14 = 21 * 71                                                         210 + 1    35         52         71 + 1     111       131
15   15 = 31 * 51                                                         211       35 + 1     52 + 1     72         111       131
16    16 = 2 * 2 * 2 * 2 = 24                                       211 + 4    36         53         72         111       131
17    17 ≠ 2 ≠ 3 ≠ 5 ≠ 7 ≠ 11 ≠ 13 ≠ 17                  215       36         53         72         111       131       171
18    18 = 2 * 3 * 3 = 21 * 32                                     215 + 1    36 + 2     53         72         111       131       171
19    19 ≠ 2 ≠ 3 ≠ 5 ≠ 7 ≠ 11 ≠ 13 ≠ 17 ≠ 19         216       38         53         72         111       131       171       191

 

( un dossier joint : Factorielle, continue ce tableau comme exemple jusqu’à la valeur 53 ! )

L’astuce :        N   <       N !

Donc si N n’est pas premier lui-même les facteurs premiers qui le composent sont déjà connus.

 

Procédure :

On sait que le résultat de la factorielle ( n ! ) du plus grand facteur de N divisée par N est le dernier entier.

Or, on ne connait pas  n .Traditionnellement on situe n < √N .

Il ne sert à rien d’utiliser √N  (racine carré de N), N / 2 est suffisant.

Il n’est donc pas nécessaire de calculer la factorielle, puisqu’il s’agit de  ( N / 2 ) !

où  N / 2  <  N , par conséquent strictement inférieur à sa factorielle aussi.

Il suffit donc d’aller la chercher dans la table factorielle, ou d’aller chercher directement la décomposition de N / 2, si l’on a pensé à l’inclure dans la mémoire.

 

Note : pour rendre l’écriture plus lisible, je l’ai simplifiée.

 

{ N } ! signifie, en fait, les facteurs premiers composant la factorielle N. Et plus précisément encore, les puissances de ces facteurs premiers, puisque se sont celles-ci que l’on additionne, ou que l’on soustrait. Les facteurs premiers étant toujours les mêmes, seuls leurs puissances augmentent quand la factorielle croît. Sauf lorsque la factorielle recherchée est elle-même un nombre premier, le facteur s’ajoute alors à la liste des multiples, à la puissance 1.

De même { N } signifie, en fait, les facteurs premiers composant N.

 

Trois cas de figure se distinguent :

   

N est pair

 

N = 2n * x        , où x est un nombre impair quelconque.

La formule, par déduction, est :

=>        { N } ! = { N – 1 } ! + 2n + { x }                       { x } = { x } ! – { x – 1 } !

 

La procédure par       N / 2 = 2n – 1 * x

a/        Trouver dans la table la composition en facteurs premiers de { N / 2 } !

            ou trouver les facteurs premiers de { N / 2 }

b/        Chercher ses facteurs sur sa factorielle       N / 2 = { N / 2 } ! – [ { ( N / 2 ) – 1 } ! ]

            (cette étape n’est pas nécessaire si les facteurs de N / 2 sont mémorisés.)

c/         Trouver dans la table la composition en facteurs premiers de { N – 1  } !

d/        Additionner :   N = { N – 1 } ! + { N / 2 } + 21

 

N est premier

 

N / 2 = décimal entier                       conserver  E ( N / 2 )

 

a/        Trouver { E ( N / 2 ) } !

b/        Trouver { N – 1 } !

c/         Soustraire       { N – 1 } ! – { E ( N / 2 ) } ! = { E ( N / 2 ) }

d/        Additionner     { N – 1 } ! + { E ( N / 2 ) }

e/        Si         { N – 1 } ! – { E ( N / 2 ) } ! + { E ( N / 2 ) } = { N – 1 } !                     alors    N est premier

f/         En ce cas ajouter { N } à { N – 1 } !                N ! = { N – 1 } ! + { N }

 

N est impair

 

Il n’existe pas pour N impair de solution simple par l’addition.

Il faut utiliser le programme de décomposition précédemment étudié. A cela près, qu’il n’est pas nécessaire de calculer ( N / 2 ) !, puisqu’on le connait déjà. Il suffit d’utiliser la formule A du programme et augmenter ou réduire la factorielle. Soit [ ( N / 2 ) – x ] ! ou [ ( N / 2 ) + x ] !

Puis de diviser par N jusqu’au dernier entier avant les décimaux.

 

Appelons ce dernier entier  avant les décimaux, ni

N = ni1 * ni2                 ne pas oublier            ni1 = a *  p = pa           ou        ap

Chercher ni1 dans la table factorielle.          a peut être égal à 1, ni1 est alors premier lui-même.

Relancer le programme sur ni2

Relancer le programme jusqu’à extraction de toutes les racines. 

 

 

 

Conclusion

 

1°/       Ce programme mécanique sur la recherche factorielle énonce donc tous les facteurs premiers de tous les nombres, et trouve facilement quand un nombre est premier.

 

2°/       De façon pratique, il faut éditer cependant des tables mémorielles, tables électroniques type « multiplieurs », de la factorielle, qui elle ne se recherche alors qu’une seule fois.

En prenant soin dans le tableau de mémoriser 4 éléments

- le nombre N pour N !

- les facteurs premiers de N

- les facteurs premiers de N !

- le résultat entier de N !

 

3°/       La gestion des très grands nombres sera alors possible.

Pour être informé des derniers articles, inscrivez vous :

Commenter cet article

clovis simard 24/10/2013 21:29


LE PLUS GRAND NOMBRE PREMIER.fermaton.over-blog.com

Archives

Nous sommes sociaux !

Articles récents