![](/img/vague-bas-gauche.png) |
#1 - 14-01-2016 15:32:41
- portugal
- Professionnel de Prise2Tete
- Enigmes résolues : 22
- Messages : 382
une question techbique
Suit à mes dernières énigmes plutôt conceptuelles, voici une question purement technique .
Soit P(n) le PPCM des n premiers nombres entiers naturels.
Soit la suite X(n) X(1)=0 X(n) = X(n-1) si P(n)>P(n-1) = X(n-1)+1 sinon
Quelle est la limite de X(n)/n pour n tends vers l'infini ?
#2 - 14-01-2016 17:12:17
- w9Lyl6n
- Professionnel de Prise2Tete
- Enigmes résolues : 26
- Messages : 220
Une questtion technique
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
#3 - 14-01-2016 18:41:40
- portugal
- Professionnel de Prise2Tete
- Enigmes résolues : 22
- Messages : 382
une question techniqie
Pas tout à fait... Il existe d'autres nombres qui font monter le compteur.
#4 - 14-01-2016 19:43:59
- dhrm77
- L'exilé
- Enigmes résolues : 49
- Messages : 3004
- Lieu: Fanning Island-?-Lac Tele,Mali
Une question tchnique
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.
Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt
#5 - 14-01-2016 20:04:20
- portugal
- Professionnel de Prise2Tete
- Enigmes résolues : 22
- Messages : 382
une suestion technique
Tout a fait d'accord avec cette première moitié de résolution dhrm
Et pour la suite ?
#6 - 14-01-2016 20:17:08
- dhrm77
- L'exilé
- Enigmes résolues : 49
- Messages : 3004
- Lieu: Fanning Island-?-Lac Tele,Mali
Une question tecchnique
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....
Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt
#7 - 14-01-2016 20:57:59
- portugal
- Professionnel de Prise2Tete
- Enigmes résolues : 22
- Messages : 382
une suestion technique
La question
Quelle est la limite de X(n)/n pour n tends vers l'infini ?
#8 - 14-01-2016 23:58:58
- kossi_tg
- Professionnel de Prise2Tete
- Enigmes résolues : 18
- Messages : 307
- Lieu: Montargis
ube question technique
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.
#9 - 15-01-2016 01:48:53
- dhrm77
- L'exilé
- Enigmes résolues : 49
- Messages : 3004
- Lieu: Fanning Island-?-Lac Tele,Mali
une question rechnique
ohhh.... j'avais pas vu le "/n"
Bon, c'est quand meme relativement simple. Comme les nombres premier se font de plus en plus rare en allant vers l'infini, et que les puissances de ces nombres sont encore plus rares, the ratio X(n)/n tend vers 1.
Voir mon message plus bas pour voir comment des puissances deviennent plus rares que les nombres premiers eux-meme.
Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt
#10 - 15-01-2016 09:15:54
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
une questoon technique
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.
#11 - 15-01-2016 09:53:17
- portugal
- Professionnel de Prise2Tete
- Enigmes résolues : 22
- Messages : 382
Uen question technique
@nodgim et @tous pas toujours facile de comprendre ce que vous voulez dire.
Merci de préciser en une phrase simple avant d'attaquer la suite du problème à quelle condition P(n)=P(n-1). Ca permettra d'être certain de partir sur une bonne base.
@dhrm tu es celui qui répond le plus proche de ce que je pense mais tu vas un peu vite pour moi quand tu dis "deviens de plus en plus rare" pour la deuxième catégorie car a un nombre premier on peut théoriquement associer un nombre infini de ta deuxième catégorie, non ? suis je clair ?
@kossi La majoration est bonne certes et même assez triviale... Comment as tu programmé ta deuxième partie. Ca fait de gros calculs non ?
@matthieu @tous Les nombres "singuliers" ne sont pas que les nombres premiers...
#12 - 15-01-2016 10:36:35
- w9Lyl6n
- Professionnel de Prise2Tete
- Enigmes résolues : 26
- Messages : 220
Une question techinque
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 ![smile](img/smilies/smile.png)
#13 - 15-01-2016 13:16:31
- portugal
- Professionnel de Prise2Tete
- Enigmes résolues : 22
- Messages : 382
Une question tehcnique
@Mathieu Merci. Tout cela me semble parfait. Je vais étudier ta démo dès que j'en aurais la possibilité
@tous origine du problème
Ce problème semble artificiel. Il part en fait d'un questionnement très pratique.
J'apprenais à mon fils (CM2) les fractions et la façon de les additionner. D’où le PPCM. En lui faisant additionner plus de 2 fractions, je me suis rendu compte du critère pour le changement du dénominateur pour une fraction supplémentaire, et j'ai "généralisé" avec la première partie du problème.
Naturellement, on se demande alors si le plus souvent, il faudra changer de dénominateur avec l'ajout d'une nouvelle fraction a additionner...d'ou la deuxième partie du problème et cette notion de densité ainsi modélisée.
Je me suis refusé à poser le problème en terme de densité car dans N ca ne veut rien dire vu que par exemple les nombres premiers sont en bijection avec tous les entiers naturels...Je suis preneur si le problème aurait pu être formulé plus élégamment
Absent pour quelques jours..je vous laisse conclure le sujet et reviendrait pour la conclusion la semaine prochaine...
#14 - 15-01-2016 16:25:05
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,418E+3
une question technisue
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 ![smile](img/smilies/smile.png)
Vasimolo
#15 - 15-01-2016 23:12:15
- kossi_tg
- Professionnel de Prise2Tete
- Enigmes résolues : 18
- Messages : 307
- Lieu: Montargis
#16 - 16-01-2016 01:08:42
- dhrm77
- L'exilé
- Enigmes résolues : 49
- Messages : 3004
- Lieu: Fanning Island-?-Lac Tele,Mali
Une queestion technique
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...
Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt
#17 - 16-01-2016 10:21:06
- portugal
- Professionnel de Prise2Tete
- Enigmes résolues : 22
- Messages : 382
une question techniquz
Ok dhrm
Toujours sympa de "checker" un résultat numérique...
Astucieux de récupérer les nombres premiers et construire les puissances. Je me demenendais comment tu faisais...
Observer l'évolution du ratio des 2 permettrait à mon goût plus de sûreté sr la conclusion (si le ratio baisse clairement le résultat final est d'autant plus clair )
#18 - 16-01-2016 12:11:36
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
une quedtion technique
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
#19 - 16-01-2016 17:46:22
- portugal
- Professionnel de Prise2Tete
- Enigmes résolues : 22
- Messages : 382
une question technisue
Ta méthode est celle a laquelle je pensais initialement mais j'avais du mal à conclure sur la dernière équation.
#20 - 16-01-2016 18:18:24
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Une qquestion technique
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.
#21 - 16-01-2016 21:50:40
- portugal
- Professionnel de Prise2Tete
- Enigmes résolues : 22
- Messages : 382
Une questiion technique
C'est clairement mon intuition également...![hmm](img/smilies/hmm.png) ![tongue](img/smilies/tongue.png)
J ai Une demo qui me semble simple et solide et je travaille sur une autre totalement diferente...
Je ne dis pas que la tienne ne l'est pas...faut que j'étudie plus pour avoir une idée nette...
#22 - 17-01-2016 02:31:31
- dhrm77
- L'exilé
- Enigmes résolues : 49
- Messages : 3004
- Lieu: Fanning Island-?-Lac Tele,Mali
Une question techniquue
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.
Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt
#23 - 17-01-2016 12:36:05
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
une qiestion technique
En fait, ma démo n'est pas finalisée. Il faudrait un majorant, mais je ne suis plus là-dessus pour l'instant....
#24 - 17-01-2016 16:34:25
- w9Lyl6n
- Professionnel de Prise2Tete
- Enigmes résolues : 26
- Messages : 220
Une question tehcnique
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) ![smile](img/smilies/smile.png)
#25 - 18-01-2016 12:08:19
- portugal
- Professionnel de Prise2Tete
- Enigmes résolues : 22
- Messages : 382
ube question technique
J'avais compris et même pas corrigé cetaut clair...
Des que je peux j'envoie ma solution...au plus tard mercredi...
|
![](/img/vague-haut-droite.png) |