Discussion :

[sandaff]

Bonsoir tout le monde;

Je ne sais pas si cette question à une bonne réponse ou pas.

Je voudrais savoir s'il y a une méthode permettant de trouver le rang d'un nombre composés impairs donné.

Par exemple de 1 à 100, il y a un total de 25 nombres composés impairs : 9, 15, 21, 25, 27, 33, 35, 39, 45, 49, 51, 55, 57, 63, 65, 69, 75, 77, 81, 85, 87, 91, 93, 95 et 99.

9 occupe le rang 1 et 15 le rang 2

comment savoir que 99 occupe le rang 25?

Merci pour votre aide.

[tbc92]

Il n'y a pas de formule précise toute faite. Evidemment.
Il y a des formules d'estimations assez classiques, valables pour les très grands nombres.
Généralement, on cherche la quantité de nombres premiers inférieur à un entier n. Il y a différentes formules plus ou moins précises pour obtenir une estimation de cette quantité. La plus simple de ces formules est n/ln(n)
Ensuite, par une soustraction, on obtient une estimation du nombre que tu recherches.

[sandaff]

Il n'y a pas de formule précise toute faite. Evidemment.
Il y a des formules d'estimations assez classiques, valables pour les très grands nombres.

bonsoir;
à partir de quel nombre?

[Guesset]

Bonjour,

Ce n'est pas possible actuellement car c'est lié directement aux nombres premiers. S'il est possible d'avoir une densité de nombres premiers, il n'existe pas de formule directe (le comptage incrémental est loin d'être direct) qui donne son rang.

Or le négatif des nombres composés impairs est les premiers (impairs pour rester dans le même type). S'il était possible de savoir directement le rang r d'un nombre composé impair n, il serait facile de trouver directement le rang du premier immédiatement supérieur. Et réciproquement. Simplement parce que le nombre i d'impairs <= n (nombre impair) est (n-1)/2 en excluant 1.

En outre, si une telle formule existait, elle devrait retourner une valeur particulière quand elle ne trouve pas de rang, c'est-à-dire si le nombre n'est pas impair ou si c'est un premier. Nous aurions là un super test de primalité.

Salutations

[Flodelarab]

Bonjour

Utilise l'OEIS (clic ici) ou l'OEIS (clic aussi ici).

[sandaff]

Merci pour votre aide;

(n-1)/2 - n/ln(n)

Ce n'est pas facile mais j'ai réussit à réduire l’incrémentation;
Seulement je dois passer maintenant au code avec le C++ car mon code java est inaccessible, le disque est gâté donc j'ai peur de m'affronter encore avec le type bigInteger très difficile à manipuler;
mais mon souci reste le test à savoir si un nombre est décimal ou pas;

comme en java on a:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
int i;
double d = 16.7;
i = (int)d;
if (i == d)
// entier
else
// décimal

mais en C++ j'ai la difficulté

en plus ça reste deux autre soucis:
-je voudrais savoir si c'est le type double qui gère les nombres RSA?
-et comment calculer la racine d'un type double en C++?

Je dois lever toutes ces question pour commencer le code, donc merci d'avance.

[Guesset]

Bonjour,

C'est toujours dangereux de faire correspondre a priori une opération informatique avec une opération mathématique sur des réels. Si c'était possible la cardinalité de la puissance du continu serait un problème réglé. Mais en informatique, toutes les grandeurs sont discrètes, y compris les flottants.

Prenons l'exemple des doubles, ils sont stockés sur 64 bits. Le maximum de valeurs différentes qu'on pourrait espérer (mais c'est inférieur) serait 2^64. Il y a donc des trous, des valeurs entières n'existent pas comme double, comme 2^60 - 1.0 par manque de précision (la mantisse a moins de 60 bits). On imagine bien que cela aura des effets aussi sur les comparaisons. Et même si le résultat est bon 99 fois sur 100, celui erroné ne se distinguera pas des autres.

Augmenter la précision des flottants améliore la situation sans faire disparaître le problème. Un simple rationnel comme 1/3 demanderait une infinité de chiffres.

Salutations

[sandaff]

Prenons l'exemple des doubles, ils sont stockés sur 64 bits.
ce qui veux dire que le type double ne gère pas les nombre RSA vue le cas de 2048 bits.

quel est le type qui le gère maintenant?

[wiwaxia]

Bonjour,

... Je voudrais savoir s'il y a une méthode permettant de trouver le rang d'un nombre composés impairs donné.

Par exemple de 1 à 100, il y a un total de 25 nombres composés impairs : 9, 15, 21, 25, 27, 33, 35, 39, 45, 49, 51, 55, 57, 63, 65, 69, 75, 77, 81, 85, 87, 91, 93, 95 et 99.

9 occupe le rang 1 et 15 le rang 2

comment savoir que 99 occupe le rang 25 ? ...

Considérons l'ensemble des entiers naturels impairs premiers ou composés; en raison de l'exclusion du (1) qui ne lui appartient pas, la liste ordonnée selon l'ordre croissant commence avec (3), et tous les nombres envisagés admettent pour expression générale en fonction de leur rang (k):

I = 2*k + 1 .

Soit maintenant P(n) le plus grand nombre premier inférieur à l'entier envisagé, et de rang (n); la liste contient (n - 1) entiers premiers (du fait de l'absence du 2 , le seul nombre premier pair), et le nombre (r) d'entiers impairs composés admet pour expression:

r = k - (n - 1) = k + 1 - n .

Dans le cas où I = 99 , on a k = (I - 1)/2 = 98/2 = 49 , P(n) = 97 et n = 25 ,
de sorte que l'on obtient: r = 49 + 1 - 25 = 25
conformément à la question posée.

Le calcul implique la connaissance de la suite P(n) des nombres premiers, comme Guesset l'a signalé dès le début de cette discussion.

[wiwaxia]

L'algorithme déterminant le rang d'un entier composé impair s'apparente à celui donnant la liste des nombres premiers successifs; il comporte un test de primalité quelque peu allégé, la restriction aux nombres impairs dispensant du test de parité.

Il est possible de vérifier les résultats pour des entiers raisonnablement peu élevés par la consultation d'une liste en ligne des nombres premiers, par exemple celle à laquelle donne accès le lien suivant:

http://compoasso.free.fr/primelistwe...ste_online.php

sachant que sur le site indiqué chaque page contient (20*10 - 1) = 199 termes;
on trouve ainsi dans les deux cas suivants:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
a) I =  9999    k = 9998/2 = 4999
P(n) =  9973    (page 7)     n =  6*199 + 35 = 1229    r =  5000 - 1229 =  3771
 
b) I = 99999    k = 99998/2 = 49999
P(n) = 99991    (page 49)    n = 48*199 + 40 = 9592    r = 50000 - 9592 = 40408

Le temps de calcul s'accroît considérablement lorsque le nombre testé (Nic) atteint et dépasse plusieurs centaines de millions, valeur très inférieure à la limite imposée par le Pascal (2³¹ - 1 = 2 147 483 647 pour les variables de type LongInt).
Une limitation semblable m'est apparue lors de la comparaison de deux programmes, l'un écrit en Virtual Pascal et l'autre en Python (par quelqu'un d'autre ); il s'agissait de trouver le dix-millionième nombre premier.
Par conséquent la possibilité de gérer les grands nombres débouche sur l'obligation d'accélérer les calculs.

Voici un programme simple permettant d'aborder le problème; il contient quelques procédures de confort rassemblées dans l'unité E_Texte: A_ (pose/arrêt), E(...) (couleurs/effacement), Wt(...), We(...) (affichage d'un texte ou d'un entier).

Code Pascal :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
 PROGRAM Liste_Nombres_Impairs_Composes;
 
 USES Crt, E_Texte;
 
 CONST Nmax = 50000000;
 
 TYPE Tab_E = ARRAY[1..Nmax] OF LongInt;
 
 VAR Nic: LongInt; Liste: Tab_E;
 
 FUNCTION Test_Prim(n: LongInt): Bool;
   VAR Lim: LongInt; Test, Test3: Bool;
       Delta, q, r: LongInt;
   BEGIN
     Lim:= Trunc(Sqrt(n)); Test3:= ((n MOD 3)>0);
     q:= 1; Delta:= 4;
     REPEAT
       Inc(q, Delta); Delta:= 6 - Delta; r:= n MOD q;
     UNTIL ((r=0) OR (q>Lim));
     IF (Test3 AND (r>0)) THEN Test:= True ELSE Test:= False;
     Result:= Test
   END;
 
 PROCEDURE Enumeration(N_: LongInt; VAR L_: Tab_E);
   CONST C1 = 5; L1 = 3; L2 = L1 + 2;
         T = 'Rang du nombre impair compos‚: r = ';
   VAR p, r: LongInt;
   BEGIN
     p:= 7; r:= 0;
     IF Test_Prim(N_) THEN BEGIN
                             E(0010); Wt(50, L1, 'Nombre premier')
                           END
                      ELSE BEGIN
                             REPEAT
                               Inc(p, 2);
                               IF (NOT Test_Prim(p)) THEN BEGIN
                                                            Inc(r);
                                                            L_[r]:= p
                                                          END
                             UNTIL (p=N_);
                             E(0015); Wt(C1, L2, T);
                             E(0010); Write(r:9)
                           END;
   END;
 
 PROCEDURE Saisie(VAR N_: LongInt);
   CONST C1 = 5; C2 = C1 + 35; L1 = 3;
   VAR n: LongInt;
   BEGIN
     E(1015); Wt(C1, L1, 'Entier impair envisag‚:      Nic = ');
     REPEAT
       GotoXY(C2, L1); ClrEol; Read(n)
     UNTIL (Odd(n) AND (n>7));
     N_:= n; E(0012); We(C2, L1, Nic, 9)
   END;
 
 PROCEDURE Init_L(VAR L_: Tab_E);
   VAR j: LongInt;
   BEGIN
     FOR j:= 1 TO Nmax DO L_[j]:= 0
   END;
 
 BEGIN
   REPEAT
     Init_L(Liste);           // Mise … z‚ro de tous les termes de la liste
     Saisie(Nic);             // Saisie de l'entier impair
     Enumeration(Nic, Liste); // Affichage du r‚sultat
     A_
   UNTIL (Nic<10);
   A_
 END.

Les limites numériques des variables n'ont pas été testées. Il faudrait aussi envisager une programmation dynamique, par recours aux pointeurs.

[sandaff]

Considérons l'ensemble des entiers naturels impairs premiers ou composés; en raison de l'exclusion du (1) qui ne lui appartient pas, la liste ordonnée selon l'ordre croissant commence avec (3), et tous les nombres envisagés admettent pour expression générale en fonction de leur rang (k):

I = 2*k + 1 .

Soit maintenant P(n) le plus grand nombre premier inférieur à l'entier envisagé, et de rang (n); la liste contient (n - 1) entiers premiers (du fait de l'absence du 2 , le seul nombre premier pair), et le nombre (r) d'entiers impairs composés admet pour expression:

r = k - (n - 1) = k + 1 - n .

Dans le cas où I = 99 , on a k = (I - 1)/2 = 98/2 = 49 , P(n) = 97 et n = 25 ,
de sorte que l'on obtient: r = 49 + 1 - 25 = 25
conformément à la question posée.

Le calcul implique la connaissance de la suite P(n) des nombres premiers, comme Guesset l'a signalé dès le début de cette discussion.

Bonjour Monsieur wiwaxia

Vous avez une très bonne intervention même je suis un peu détourner vers python mais aussi un peu soufrant (mon cote gauche me fait mal, surtout mon avant bras, donc je n'arrive pas à bien travailler)

Je voudrais savoir comment vous trouvez n=25
si p(n)=97; on a p(25)=97 et par quelle expression que n=25;

j'ai cru que c’était une supposition mais votre deuxième intervention fait apparaître des calcules qui me fait comprendre que ce n'est pas un hasard.

[wiwaxia]

Bonjour,

... Je voudrais savoir comment vous trouvez n=25
si p(n)=97; on a p(25)=97 et par quelle expression que n=25;

j'ai cru que c’était une supposition mais votre deuxième intervention fait apparaître des calcules qui me fait comprendre que ce n'est pas un hasard.

C'est tout simplement le 25^me terme de la liste des nombres premiers:

Le repérage du rang devient de plus en plus difficile pour des nombres plus élevés, parce qu'il faut compter les pages précédant celle qui contient l'entier recherché. Le procédé trouve rapidement sa limite, et il faudrait trouver un site permettant une exploration plus efficace de la liste des nombres premiers.

L'établissement de cette liste est exclusivement algorithmique, il n'existe pas de fonction explicite p = F(n) ou n = G(p) - pour la raison qui a déjà été clairement exposée (#3)