si j'ai bien compris X(n) compte le nombre de nombres premiers jusqu'à n (puisqu'un nombre non premier aura ses facteurs présents dans 1...n)

Donc X(n)/n tend vers 0 à la vitesse de 1/ln(n)

Mathieu

P(n) n'est jamais inferieur a P(n-1), mais il peut etre égal pour tout nombre composé de nombre deja rencontrés auparavant.
dont on a:
P(1) =  1, X(1)=0
P(2) =  2, X(2)=0
P(3) =  6, X(3)=0
P(4) = 12, X(3)=0
P(5) = 60, X(5)=0
P(6) = 60, X(6)=1
...
P(10)=2520, X(10)=2, etc...

Les nombres qui ne font PAS monter le compteur sont les nombres premiers, et toutes leurs puissances....
C'est a dire: 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131, etc...
ainsi que:  4, 8, 9, 16, 25, 27, 32, 49, 64,81,121,125,128, etc...
Tout le reste fait monter le compteur.

Bon, c'est simple... si X(n) increment pour tout nombre qui ne sont ni une puissance ni premiers, X(n) tend donc vers l'infini, mais lentement....

Par définition [latex]\forall n\geq 2,  X(n)\leq (n-1)[/latex]


donc [latex]\forall n\geq 2,   \frac{X(n)}{n} \leq \frac{n-1}{n} [/latex].

Je n'ai pas la suite en démonstration analytique.

Par contre, d'après mon modèle numérique; [latex]X(n)/n[/latex] tend vers 1. Le calcul fait sur l'intervalle [latex][1 ; 10^8][/latex] donne une courbe à allure logarithmique avec asymptote la droite y=1.

Salut Portugal,
Pas trop dur celle ci, mais marrante.

Si p premier : P(p)=p*P(p-1) donc X(p)=X(p-1).

Si n composé et =/= 4 : P(n)=P(n-1) donc X(n)=X(n-1)+1.

Pour cette 2ème régle, il faut une petite explication. Si n=p1*p2*p3...produit de facteurs premiers, ces facteurs premiers existent déja dans les n-1 précédents nombres.
Si n=p² : il existe entre 1 et n-1, p-1 facteurs de p (p, 2p, 3p,..) donc forcément plus que 2 sauf si p=2. Donc P(p²)=P(p²-1)
Idem si n= p1^k * p2^j * p3^l * .....

Donc X(n)=n-p(n)-2 si p(n) est le nombre de nombres premiers entre 1 et n. 
X(n)/n=1- p(n)/n - 2/n qui tend vers 1 quand n tend vers l'infini.

Poson [latex]Y(n)=n-X(n)[/latex] (inversion de la condition)

En examinant plus attentivement, Y(n) compte aussi les puissances des nombres premiers.
En effets si n possède m facteurs premiers,
pour faire monter le compteur Y(n), il faut qu'en retirant un facteur premier quelconque de n on obtienne toujours le même nombre, sinon le ppcm de deux de ces nombre serait n. Dans ce cas les m facteurs premiers doivent être égaux.

Calculons maintenant Y(n)/n

Pour un nombre premier p, ses puissance font monter le compteur entre 1 et [latex]p^n[/latex] de n
Autrement dit de 1 à [latex]n = p^{\frac{ln(n)}{ln(p)}}[/latex] , les puissances de p font monter le compteur de [latex]\lfloor{\frac{ln(n)}{ln(p)}}\rfloor [/latex]

On peut alors poser une bonne majoration : [latex]Y(n) \le ln(n) \sum_{p \le n} \frac{1}{ln(p)}[/latex]

sachant que la densité des nombres premier est [latex]\frac{1}{ln(n)}[/latex], on peut approximer grossièrement la somme par :
[TeX]\sum_{i=2}^{n} \frac{1}{ln(i)^2}[/TeX]
A grand coup de wolphram alpha et de wikipedia : [latex]\int \frac{1}{ln(x)^2} = li(x) - \frac{ln(x)}{x} + Cst[/latex]

En développant [latex]li(x) = \frac{x}{ln(x)} + \frac{x}{ln(x)^2} + o(\frac{x}{ln(x)^2})[/latex]

Ce qui nous laisse [latex]\sum_{i=2}^{n} \frac{1}{ln(i)^2} \sim \frac{n}{ln(n)^2}[/latex]

Finalement [latex]Y(n) \sim \frac{n}{ln(n)}[/latex] comme le nombre de nombre premier inférieur à n, ce qui intuitivement est cohérent vu que les puissances des nombres premiers montent très vite.

Conclusion : Y(n)/n tend vers 0 et est équivalent à 1/ln(n)
X(n)/n tend vers 1

Un bon problème de math, merci

Bonjour

Les seuls nombres qui font avancer le compteur sont les puissances des nombres premiers . J'ai l'impression que ces puissances se raréfient sérieusement quand n grandit ce qui laisse penser que le rapport va tendre vers 0 . Il y a peut-être une inégalité astucieuse qui tue le problème mais je ne vois pas à priori

Vasimolo

Voila, apres avoir corrigé quelques petits problemes dans mon programme j'obtiens ca:

pour n=10:                   X(n)/n = 0.2000000000
pour n=100:                 X(n)/n = 0.6400000000
pour n=1000:               X(n)/n = 0.8060000000
pour n=10000:             X(n)/n = 0.8719000000
pour n=100000:           X(n)/n = 0.9029900000
pour n=1000000:         X(n)/n = 0.9212650000
pour n=10000000:       X(n)/n = 0.9334865000
pour n=100000000:     X(n)/n = 0.9423714000
pour n=1000000000:   X(n)/n = 0.9491487760
pour n=4211490532:   X(n)/n = 0.9526243703

On "voit" bien que ca tend vers 1....

Pour aller plus loin, on separe combien il y a de nombres premiers et combien de puissances de nombres premiers il y a à chaque étape. Pourquoi separer? Simplement parce que calculer tous les nombres premiers jusqu'a 10^19 prend trop de momoire et trop de temps, Mais cette information est accessible sur Internet. Par contre compter toutes les puissances de nombres premiers jusqu'a 10^19 c'est beaucoup plus rapide.

n             pi (premiers)                           pu  (puissances)                   X(n)/n=1-(pi+pu+1)/n
10^1      4                                                3                                                0.2
10^2      25                                              10                                             0.64
10^3      168                                            25                                             0.806
10^4      1229                                          51                                             0.8719
10^5      9592                                          108                                           0.90299
10^6      78498                                        236                                           0.921265
10^7      664579                                      555                                           0.9334865
10^8      5761455                                    1404                                         0.94237140
10^9      50847534                                  3689                                         0.949148776
10^10    455052511                               10084                                       0.9526243703
10^11    4118054813                             28156                                       0.95881917030
10^12    37607912018                           80070                                       0.962392007911
10^13    346065536839                        230567                                     0.9653934232593
10^14    3204941750802                      670124                                     0.96795057579073
10^15    29844570422669                    1962748                                  0.970155427614582
10^16    279238341033925                  5784522                                  0.9720761653181552
10^17    2623557157654233                17186755                               0.97376442825159011
10^18    24739954287740860              52837455                               0.975260045659421684
10^19    234057667276344607            222187533                            0.9765942332501467859
edit: pour les corrections voir plus bas.

Ici, on voit que la presence des puissances de nombres premiers devient de plus en plus negligeable par rapport au nombre de nombres premiers.

Alors, pourquoi fais-je ces calculs apres avoir dit que ca tend vers 1?
Parce que je n'en suis pas sur a 100%. L'infini est quand meme loin... est-ce que les puissances peuvent devenir dominante?
Si le taux de presence des puissances commencait a s'accroitre au meme se stabiliser, au lieu de diminuer, x(n)/n pourrais tendre vers un nombre autre que 1, peut-etre 0.9999998?

Pour continuer on peut extrapoler pour estimer la progression des puissances et des nombres premiers, parce que faire les calculs prend beaucoup de temps.

n             pi (premiers)                                    pu  (puissances)                   X(n)/n=1-(pi+pu+1)/n
10^20   2220819602560918840                688780000 ?                        0.977791803967503...
10^21   21127269486018731928              2204100000 ?                     0.9788727305117771...
10^22   201467286689315906290            7053100000 ?                     0.9798532713393153...
10^23   1925320391606803968923          22570000000 ?                   0.9807467960837062...
10^24   18435599767349200867866       ???                                          0.9815644002326...
10^25   176846309399143769411680     ???                                          0.98231536906007...

Je me suis planté en raisonnant à tort sur n!

En fait, P(n) augmente pour chaque nouveau nombre premier ou chaque élévation d'un nombre premier à une puissance supérieure.

X(n) vaut donc (n-1) auquel on retranche les nombres premiers compris entre 1 et n, chacun de ces nombres premiers étant affecté d'un coeff équivalent à la puissance de ce nombre premier immédiatement inférieur à n.

Par exemple, pour 100:
x(100)=100-1-(7+4+2+2+1+1+....)
7: vient de 2^7, plus grande puissance de 2 < 100
4: vient de 3^4, plus grande puissance de 3 < 100
2: vient de 5^2, plus grande puissance de 5 < 100
....

X(n)/n=1-1/n-(p1+p2+p3+..)/n où p1,p2,p3...représentent la puissance de chaque nombre premier entre 1 et n. 

La quantité de nombres premiers entre 1 et n est environ n/ln(n).
La quantité de nombres premiers entre 1 et Vn est environ Vn/ln(Vn) ou 2Vn/ln(n).
La quantité de nombres premiers entre 1 et (n)^(1/k) est environ k*n^(1/k)/ln(n).

X(n)/n vaut environ alors:
1- (1 + 2/Vn +...k/n^((k-1)/k))/ln(n).
L'expression négative -----> 0 si n----> oo
X(n)/n tend vers 1 quand n--->oo

Intuitivement c'est quand même assez évident. n et X(n) se décalent d'une unité quand on tombe sur un nombre premier ou une puissance de l'un d'eux. Les nombres premiers se raréfient, leurs puissances encore plus ! alors si le décalage grandit infiniment, il se fait très lentement.

Correction:

Apres avoir examiné la progression du nombre de puissances de nombres premiers, je me suis apercu que quelque choise n'allais pas. J'ai donc fait des corrections, et voici la série corrigée:
n         pi (premiers)                               pu  (puissances)      X(n)/n=1-(pi+pu+1)
10^1  4                                                    3                                 0.2
10^2  25                                                  10                               0.64
10^3  168                                                25                              0.806
10^4  1229                                              51                              0.8719
10^5  9592                                              108                            0.90299
10^6  78498                                            236                            0.921265
10^7  664579                                          555                            0.9334865
10^8  5761455                                        1404                         0.94237140
10^9  50847534                                      3689                         0.949148776
10^10  455052511                                  10084                       0.9544937404
10^11  4118054813                                28156                      0.95881917030
10^12  37607912018                              80070                      0.962392007911
10^13  346065536839                            230567                    0.9653934232593
10^14  3204941750802                          670121                    0.96795057579076
10^15  29844570422669                       1962689                  0.970155427614641
10^16  279238341033925                     5782467                  0.9720761653183607
10^17  2623557157654233                   17124205                0.97376442825221561
10^18  24739954287740860                 50930439                0.975260045661328700
10^19  234057667276344607               152043591              0.9765942332571611801

10^20  2220819602560918840             455462060              0.97779180396983619099
10^21  21127269486018731928           1368671978           0.978872730512612596093
10^22  201467286689315906290         4124576081           0.9798532713306559517628
10^23  1925320391606803968923       12461253414         0.98074679608380734777662
10^24  18435599767349200867866     37732562054         0.981564400232613066570079
10^25  176846309399143769411680   114475542913      0.9823153690600741755045406
Note: les comptes des puissances de nombres premiers pour les lignes 10^20 a 10^25 ne sont que des estimations.

Il est plus clair maintenant que les taux de progression du nombre de nombres premiers et de leur puissances se stabilisent, et par consequent X(n)/n tend bien vers 1.

J'avais inversé les conditions pour incrémenter le compteur. Du coup j'adapte ma démo avec une petite astuce Y(n) = n - X(n)