Utilisateur:Stéphane Jaouen/Brouillon

La numération primorielle est une numération où un entier $n$ est écrit sous la forme :

$n=x\times p_{m}\sharp +....+f\times 2310+e\times 210+d\times 30+c\times 6+b\times 2+a\times 1$

où a, b, c,... sont des entiers que l'on soumet à des contraintes pour garantir l'unicité de l'écriture de n dans cette nouvelle numération :

class="table-rh" {{rh}} \| Base	19	17	13	11	7	5	3	2
class="table-rh" {{rh}} \| Valeur de position	(p ₇ = 17) #	(p ₆ = 13) #	(p ₅ = 11) #	(p ₄ = 7) #	(p ₃ = 5) #	(p ₂ = 3) #	(p ₁ = 2) #	(p ₀ = 1) #
class="table-rh" {{rh}} \| Écriture en base 10	510510	30030	2310	210	30	6	2	1
class="table-rh" {{rh}} \| Chiffre le plus élevé autorisé	I=18	G=16	C=12	A=10	6	4	2	1

On écrit alors n=(x...gfedcba). C'est par exemple la notation adoptée par Charles-Ange Laisant en 1888 dans son article sur la numération factorielle (wp), une numération similaire à la numération primorielle(Sur la numération factorielle, application aux permutations Bulletin de la S. M. F., tome 16 (1888), p. 176-183). On peut aussi écrire (g:f:e:d:c:b:a), notation adoptée dans un article ébauché dans une publication de l'OEIS également donné en références.

Par exemple, 2101=10x210+0x30+0x6+0x2+1x1=(A0001) en numération primorielle (ici, e=10=A, d=0, c=0, b=0 et a=1) ou (A:0:0:0:1).

On utilise classiquement les chiffres A=10, B=11, C=12, ... comme en base 12 par exemple pour présenter les résultats simplement.

Le système de numération primorielle est aussi appelé "primoradic" en anglais(voir le site de l'OEIS indiqué dans les références).

Exemples[modifier | modifier le wikicode]

Dans l'écriture n=30d+6c+2b+1a, a appartient à {0,1}, b à {0,1,2}, c à {0,1,2,3,4}. Ces restrictions permettent l'unicité de l'écriture de n en numération primorielle. Voici l'écriture des premiers entiers :

0=(0)

1=(1)

2=(10)

3=(11)

4=(20)

5=(21)

6=(100)

7=(101)

8=(110)

9=(111)

10=(120)

11=(121)

12=(200)

...

29=(421)

30=(1000)

31=(1001)

...

35=(1021)

....

209=(6421)

...

On peut obtenir l'écriture d'un entier sur un tableur par exemple. Proposons au hasard l'écriture de N=654.565.467=1x1+1x2+4x6+2x30+7x210+0x2310+3x30.030+9x510.510+21x9.699.690+2x223.092.870. On écrira plus volontiers N=2.(21)93.072.411 ou N=2.L93.072.411 avec L=21. On verra dans l'exemple n°4 ci-dessous que la terminaisons (11) indique immédiatement un multiple de 3, ce qu'on peut vérifier immédiatement avec le critère de divisibilité par 3 classique en numération décimale. Cette information serait immédiatement fournie par une interface de programmation (API), comme de nombreuses informations que l'API pourrait fournir et qu'on développera dans les exemples ci-dessous.
Considérons le 5ème nombre de Fermat $F_{5}=2^{32}+1=4.294.967.297=(J.5F1.721.221)$ avec J=19 et F=15. (voir l'exemple n°8 ci-dessous pour un petit développement)

Bref historique[modifier | modifier le wikicode]

La numération primorielle est une numération à base variable (wp). Tout comme le décompte des années, mois, jours, heures, minutes et secondes. Il y a une autre numération à base variable utile en mathématiques : la numération factorielle.

Opérations[modifier | modifier le wikicode]

On peut additionner, soustraire, multiplier et diviser en numération primorielle. On utilise la division euclidienne.

Une écriture élégante de problèmes d'arithmétique[modifier | modifier le wikicode]

La numération primorielle permet d'écrire élégamment quelques problèmes arithmétiques :

Le problème des nombres premiers jumeaux s'écrit : Existe-t-il une infinité de couples de nombres premiers du type (p,p+10) ?
Le problème des nombres premiers sexys s'écrit de même avec (p,p+100)
On peut écrire élégamment aussi le problème des constellations. Par exemple, la constellation (9.000.004.001,9.000.004.007,9.000.004.013,9.000.004.019) s'écrit (p,p+100, p+200,p+300) avec p=(4F3.490.3A1.121). On a utilisé les chiffres A=10, B=11, C=12, ... comme en base 12.
Le problème du changement de champions (d'abord les jumeaux, puis les sexys se révèlent très tôt plus nombreux, puis les couples de nombres premiers séparés de 30,de 210, de 2310... s'écrit avec (p,p+1000), (p,p+10.000), ...

Intérêts de la numération primorielle[modifier | modifier le wikicode]

Exemple n°1: application aux suites de Tao[modifier | modifier le wikicode]

Considérons une suite de Tao, (3361, 3571, 3781) suite de raison 210 et de longueur 3. Elle s'écrit en numération primorielle (150001,160001,170001). L'élégance de cette écriture n'est pas fortuite. La numération primorielle est liée aux groupes des unités des $Z/p_{n}\sharp Z$ , groupes utiles en arithmétique.

Exemple n°2 : application aux nombres de Sophie Germain[modifier | modifier le wikicode]

Un nombre premier sûr est un nombre premier de la forme 2p + 1, où p est lui-même un nombre premier (p est alors appelé un nombre premier de Sophie Germain).

Voici deux couples de nombres entiers :

(32.561;65123) et (62.591 ; 125.183).

En numération primorielle, ces deux couples s'écrivent :

(1.110.121 ; 2.220.321) et (2.110.121 ; 4.220.321).

Exemple n°3 : critères de divisibilité[modifier | modifier le wikicode]

Il existe des critères de divisibilité intéressants en numération primorielle.

En voici un exemple simple : les nombres divisibles par 3 sont les nombres qui se terminent par (00) ou (11).
En numération primorielle, les multiples de 7 qui ne sont pas des multiples de 2 ou de 3 ou de 5 se terminent par (0101), (1301), (2221), (3001), (3421), (4201), (5121) ou (6321). [critère de divisibilité par 7 en numération primorielle] Considérons un exemple historique, un nombre étudié par Blaise Pascal qui se proposa de montrer que ce nombre était divisible par 7 sans poser la division, en l'occurrence N=287.542.178. Commençons par le diviser par 2 : N1=N/2=143.771.089 En numération primorielle, N1=(EFA.761.301)=49 mod 210. Il aura suffi de regarder la terminaison (1.301) pour se convaincre que le nombre de Pascal est un multiple de 7.

Voici une utilisation plus technique :

Soit M₅₉, le 59è nombre de Mersenne

$M_{59}=2^{59}-1=[(44)2S.EPD.2C6.325.101]$

On peut utiliser une table de congruence des $p_{n}\sharp$ modulo $p_{m}$ pour prouver que $M_{59}$ n'est pas premier :

Modulo 179.951,

13#=30030

17#=150608

19#=162287

23#=133581

29#=94878

31#=62002

37#=134662

41#=122612

et 43#=53737

Donc M₅₉ est congru à 13676276=76x179951

Autrement dit, 179951 divise M₅₉, qui en particulier n'est donc pas premier.

Exemple n°4 : Nombres de Mersenne[modifier | modifier le wikicode]

Voici l'écriture des nombres de Mersenne en numération primorielle :

000000001

000000011-

000000101

000000211-

000001001

000002011-

000004101

000011211-

000023001

000046011-

000095101

000183211-

000360001

000710011-

001120101

002240211-

004481001

008952011-

0105A4101

020BA1211-

041A93001

083876011-

0G7445101

1DE893211-

38C480001

...

On a indiqué par un tiret les multiples de 3 (voir exemple n°4).

Exemple n°5 : factorielles[modifier | modifier le wikicode]

L'écriture des factorielles en numération primorielle est également très intéressante. Elle permet entre autres de faire le lien avec la numération factorielle et aussi permet d'illustrer le théorème de Wilson.

Exemple n°6 : puissances d'un entier[modifier | modifier le wikicode]

Il est aisé d'obtenir avec un tableur l'écriture en numération primorielle des puissances d'un nombre entier. Cette écriture montre les périodicités dans ces écritures liées au petit théorème de Fermat. En ce qui concerne les puissances de 10, cette écriture permet le passage d'une écriture en base 10 en numération primorielle. Tous les problèmes arithmétiques (par exemple les nombres RSA) peuvent être soumis aux techniques de la numération primorielle ou de la numération factorielle.

Exemple n°7 : Spirale d'Ulam[modifier | modifier le wikicode]

Illustration de la spirale d'Ulam centrée en 0.

Grâce aux critères de divisibilité en numération primorielle (voir exemple n°4), on peut revisiter la spirale d'Ulam en utilisant la numération primorielle. On attribue des couleurs dans l'illustration ci-dessous par exemple aux multiples de 3 qui ne sont pas des multiples de 2; une autre aux multiples de 5 qui ne sont ni multiples de 2 ni de 3, etc. Cela permet de mieux comprendre la fréquence des écarts égaux aux primorielles (30, 210, 2310, ...) qui apparaissent visuellement sur la spirale.

Exemple : Si on se limite à colorier les nombres qui sont multiples de 2, 3, 5, 7, 11, 13, 17, 19, les deux couples (829,1669) et (839,1679) apparaissent en blanc sur des lignes parallèles observées par Stanislaw Ulam : en numération primorielle, ces deux couples s'écrivent (36.301,76.301) et (36.421,76.421). Ils contiennent trois nombres premiers. Seul 1679=23x73. Et l'on a 76.301-36.301=40.000 (4x210 en numération décimale)

Exemple n°8 : Nombres de Fermat[modifier | modifier le wikicode]

Les nombres de Fermat sont définis par $F_{n}:=2^{2^{n}}+1$ .

$F0=3=(00000000011)$

$F_{1}=5=(00000000021);F_{2}=17=(0000000.221);F_{3}=257=(000011.221);F_{4}=65.537=(2.240.221);$

$F_{5}=2^{32}+1=4.294.967.297=(J.5F1.721.221)$

Si F_n - 1 est congru à 16 modulo 30 comme F₂, F₃ et F₄, alors 2^(2^(n+1))=(2^(2^n))^2=16²mod30=16mod 30 et F_n+1=17mod 30. Ainsi on a prouvé que pour tout n supérieur ou égal à 2, F_n=17mod30 d'où la terminaison (221)=17.

Ceci est le genre de résultat simple à démontrer que suggère une interface de programmation.

Exemple n°9 : Nombres premiers écrits en numération primorielle[modifier | modifier le wikicode]

(10) (11) (21) (101) (121) (201) (221) (301) (321) (421) _________________________ (1001) (1101) (1121) (1201) (1221) (1321) (1421) _______________________ (2001) (2101) (2121) (2201) (2321) (2421) _________________________ .... Les liens apparaissant dans cette liste sont liés aux groupes Z/pn#Z, ici Z/30Z (voir figure 1 du paragraphe 13 de l'article de cryptologie donné en références)

Références[modifier | modifier le wikicode]

Primorial numeral system sur l'Encyclopédie en ligne des suites de nombres entiers
Modern Cryptography : Current challenges and Solutions (chapitre II, paragraphe 14), publié par Menachem Domb, (https://books.google.fr/books?id=ipj8DwAAQBAJ&pg=PA29&lpg=PA29&dq=primoradic&source=bl&ots=syRBIpgRk7&sig=ACfU3U3a6_qXrnuMdiURSJkxI-u6C17Vkg&hl=fr&sa=X&ved=2ahUKEwiApouFxpLwAhUPmRQKHaOXDPUQ6AEwBnoECAkQAw#v=onepage&q=primoradic&f=false)
http://archive.numdam.org/article/BSMF_1888__16__176_0.pdf(notation de Charles-Ange Laisant pour la numération factorielle, numération à base variable comme la numération primorielle)
Representation of Integer Numbers in Computer Systems, http://lux.dmcs.pl/csI/integer_representation.pdf
Même article que plus haut mais un peu plus développé ici sur la numération primorielle : https://www.researchgate.net/publication/334056166_Survey_of_RSA_Vulnerabilities

Utilisateur:Stéphane Jaouen/Brouillon

Sommaire

Exemples[modifier | modifier le wikicode]

Bref historique[modifier | modifier le wikicode]

Opérations[modifier | modifier le wikicode]

Une écriture élégante de problèmes d'arithmétique[modifier | modifier le wikicode]

Intérêts de la numération primorielle[modifier | modifier le wikicode]

Exemple n°1: application aux suites de Tao[modifier | modifier le wikicode]

Exemple n°2 : application aux nombres de Sophie Germain[modifier | modifier le wikicode]

Exemple n°3 : critères de divisibilité[modifier | modifier le wikicode]

Exemple n°4 : Nombres de Mersenne[modifier | modifier le wikicode]

Exemple n°5 : factorielles[modifier | modifier le wikicode]

Exemple n°6 : puissances d'un entier[modifier | modifier le wikicode]

Exemple n°7 : Spirale d'Ulam[modifier | modifier le wikicode]

Exemple n°8 : Nombres de Fermat[modifier | modifier le wikicode]

Exemple n°9 : Nombres premiers écrits en numération primorielle[modifier | modifier le wikicode]

Références[modifier | modifier le wikicode]

Menu de navigation

Utilisateur:Stéphane Jaouen/Brouillon

Exemples[modifier | modifier le wikicode]

Bref historique[modifier | modifier le wikicode]

Opérations[modifier | modifier le wikicode]

Une écriture élégante de problèmes d'arithmétique[modifier | modifier le wikicode]

Intérêts de la numération primorielle[modifier | modifier le wikicode]

Exemple n°1: application aux suites de Tao[modifier | modifier le wikicode]

Exemple n°2 : application aux nombres de Sophie Germain[modifier | modifier le wikicode]

Exemple n°3 : critères de divisibilité[modifier | modifier le wikicode]

Exemple n°4 : Nombres de Mersenne[modifier | modifier le wikicode]

Exemple n°5 : factorielles[modifier | modifier le wikicode]

Exemple n°6 : puissances d'un entier[modifier | modifier le wikicode]

Exemple n°7 : Spirale d'Ulam[modifier | modifier le wikicode]

Exemple n°8 : Nombres de Fermat[modifier | modifier le wikicode]

Exemple n°9 : Nombres premiers écrits en numération primorielle[modifier | modifier le wikicode]

Références[modifier | modifier le wikicode]

Menu de navigation

Chercher