Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 14-01-2016 15:32:41

portugal
Professionnel de Prise2Tete
Enigmes résolues : 22
Messages : 374

une quesyion technique

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 ?



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 14-01-2016 17:12:17

w9Lyl6n
Professionnel de Prise2Tete
Enigmes résolues : 26
Messages : 220

Une queston 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 : 374

une question techniqye

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 : 2991
Lieu: Fanning Island-?-Lac Tele,Mali

Une qusetion technique

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 : 374

une question tzchnique

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 : 2991
Lieu: Fanning Island-?-Lac Tele,Mali

ne question technique

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 : 374

Une question techniqu

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 : 301
Lieu: Montargis

Une quuestion 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 : 2991
Lieu: Fanning Island-?-Lac Tele,Mali

une question trchnique

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 : 2955

Une question techique

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 : 374

Une questio ntechnique

@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 qiestion technique

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

 #13 - 15-01-2016 13:16:31

portugal
Professionnel de Prise2Tete
Enigmes résolues : 22
Messages : 374

une question trchnique

@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 : 4734

Une question technqiue

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

Vasimolo

 #15 - 15-01-2016 23:12:15

kossi_tg
Professionnel de Prise2Tete
Enigmes résolues : 18
Messages : 301
Lieu: Montargis

Une question tcehnique

http://www.prise2tete.fr/upload/nobodydy-N40-p29.jpghttp://www.prise2tete.fr/upload/nobodydy-N40-p66.jpghttp://www.prise2tete.fr/upload/nobodydy-N40-p49.jpg
Pour mon modèle numérique, j'ai trouvé la condition pour avoir P(n)=P(n-1). En effet s'il existe A et B premiers entre eux tel que n=A*B alors P(n)=P(n-1).

Pour les valeurs de X(n), plus besoin de calculer P(n), ce qui m'a permis d'aller jusqu'à [latex]n=10^8[/latex].

 #16 - 16-01-2016 01:08:42

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 2991
Lieu: Fanning Island-?-Lac Tele,Mali

Une question tecnique

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 : 374

Une uqestion technique

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 : 2955

une question techbique

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 : 374

Une question tehcnique

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 : 2955

Une questoin 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 : 374

Unee question technique

C'est  clairement mon intuition également...hmmtongue

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 : 2991
Lieu: Fanning Island-?-Lac Tele,Mali

Une uestion technique

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 : 2955

une question rechnique

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 techinque

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

 #25 - 18-01-2016 12:08:19

portugal
Professionnel de Prise2Tete
Enigmes résolues : 22
Messages : 374

Une uestion technique

J'avais compris et même pas corrigé cetaut clair...

Des que je peux j'envoie ma solution...au plus tard mercredi...

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Dans une course, vous doublez le 19ème, en quelle position êtes-vous ?

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete