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 - 26-12-2017 10:53:43

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3437

Cbe et diviseurs

Bonjour @ tous.

Une recherche de fin d'année pas trop méchante :

Trouver un nombre tel que son cube possède 2017 fois plus de diviseurs que lui.

Trouver un nombre tel que son cube possède 2018 fois plus de diviseurs que lui.

Dans le décompte des diviseurs, 1 et le nombre lui même sont pris en compte.

Wolfram peut sans doute vous aider, mais c'est mieux à la main....

Pour les plus inspirés d'entre vous :

Pour un coefficient multiplicateur donné entre le nombre de diviseurs de n et celui de n^3, existe t'il toujours une solution pour n ?



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 26-12-2017 18:19:28

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 691

Cube et divseurs

Sauf erreur de calcul, [latex]2^{1197}.3^{897}.5^{672}.7^{399}.11^{133}.13^{22}.17^{15}[/latex] convient pour 2017, et [latex]2^{336}.3^{112}.5^{75}.7^{25}.11^{4}.13^{3}.17.19[/latex] convient pour 2018.

 #3 - 26-12-2017 19:31:25

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3437

cube rt diviseurs

Une coquille pour 2017, un 25 au lieu d'un 26 il me semble.

Pour 2018, je crois que c'est bon, j'ai cependant un plus court. En fait tu as dû faire la même chose que ce que j'ai trouvé en première version, j'ai un 133 rayé qui a été remplacé par une valeur moindre.

Sinon, c'est OK bravo !


Je vais poser une question subsidiaire, je la mets ici et la recopie dans l'énoncé :
Peut on toujours trouver une solution pour un coefficient multiplicatif donné entre le nombre de diviseurs de n et le nombre de diviseurs de n^3 ?
Aide: ça ne marche jamais si le coefficient est un multiple de 3.

 #4 - 26-12-2017 19:37:27

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 691

Cube t diviseurs

Tu es sûr de la coquille ? 25 concerne 2018 pourtant ?

 #5 - 27-12-2017 07:59:25

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3437

Cube et diiviseurs

Euh, oui c'est bien 25 pour 2018, la coquille vient de ma propre recopie...

En revanche, je confirme le raccourci mais pour 2017, mais bon, je ne demandais pas spécialement le plus petit nombre.

 #6 - 27-12-2017 12:26:03

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 691

CCube et diviseurs

OK. Je regarderai pour l'optimisation mais ce n'est pas une grosse affaire. Je suis plus intéressé par la question subsidiaire, pour l'instant j'ai bien une idée mais il me reste un cas qui pose problème. Je continue à réfléchir.

 #7 - 28-12-2017 15:47:42

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 691

Cube et diviseus

Ça y est, j'ai trouvé une méthode qui fonctionne pour la question subsidiaire. Je la posterai bientôt, quand je serai dans de meilleures conditions pour rédiger.

Quand tu dis que tu as trouvé une solution plus courte pour 2017, est-ce une solution qui nécessite moins de facteurs premiers, ou une valeur de n plus petite (ou les deux) ?

 #8 - 28-12-2017 16:08:54

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2863
Lieu: Luxembourg

cube et diviseues

Soit N ce nombre.
Son écriture primaire est: N=Produit(pi^ni), et celle de son cube: N³=Produit(pi^3ni)
Le nombre de diviseurs de N est: Produit(ni+1), et celui de son cube: Produit(3ni+1)
On doit donc avoir: Produit(3ni+1) = 2017.Produit(ni+1)
Là je sèche un peu, mais je reviendrai: affaire à suivre.

 #9 - 28-12-2017 18:33:10

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3437

Cube et diviseus

@ Ebichu: oui, les deux, ça se trouve à la gestion post-399. Mais bon, c'est du détail.

@ Francky: tel est le problème qui est posé. Je donne du temps supplémentaire.

 #10 - 28-12-2017 21:08:58

ahbouk
Visiteur

Cube et divisers

Je Sais pas comment commencer.

 #11 - 29-12-2017 10:56:48

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 691

Cube et idviseurs

J'ai mieux à proposer pour 2017 : [latex]2^{897}.3^{748}.5^{672}.7^{499}.11^{33}.13^{28}.17^{19}[/latex], ou bien [latex]2^{897}.3^{748}.5^{672}.7^{499}.11^{3}.13^{3}.17.19[/latex].

J'ai amélioré la fin, comme tu le suggérais, mais aussi le début.

Maintenant je vais essayer de rédiger la question subsidiaire, ça risque d'être long hmm

 #12 - 29-12-2017 11:58:12

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 691

Cubee et diviseurs

Si [latex]n=\Pi p_i^{a_i}[/latex], alors le nombre de diviseurs de n est [latex]\Pi(a_i+1)[/latex], et celui de n³ est [latex]\Pi(3a_i+1)[/latex]. On recherche donc des entiers [latex]a_i[/latex] tels que le coefficient multiplicateur CM soit égal à [latex]\Pi \frac{3a_i+1}{a_i+1}[/latex].

Si CM est multiple de 3, ce n'est pas possible car aucun des [latex](3a_i+1)[/latex] n'est multiple de 3. Réciproquement, on va montrer que c'est possible si CM n'est pas multiple de 3, par récurrence sur CM : l'idée est que si on part par exemple de 2017, on trouve un certain nombre de [latex]a_i[/latex] qui permettent de se ramener à un CM strictement plus petit (et qui ne soit pas multiple de 3). Par exemple, en prenant [latex]a_1=672[/latex], on se ramène à CM=673 car 673*(3*672+1)/(672+1)=2017. En général, il sera parfois nécessaire de prendre plusieurs [latex]a_i[/latex] d'un coup pour se ramener au CM suivant.

Deux cas sont faciles : si CM=1 mod 9 ou si CM=4 mod 9, on prend [latex]a_i=\frac{CM-1}{3}[/latex]. Par exemple, si CM=31, on prend [latex]a_i=10[/latex], et on se ramène à CM=11.

Ensuite, on va régler le cas où CM=2 ou 5 ou 8 mod 9. On écrit alors [latex]CM+1=3^{k-1}.m[/latex] où 3 ne divise par m, donc m=3j+1 ou 3j+2, et il vient [latex]CM=3^{k}.j+(3^{k-1}-1)[/latex] ou [latex]CM=3^{k}.j+(2.3^{k-1}-1)[/latex] avec k>1 et j>=0.

Dans le premier cas, on prend [latex]a_i=5^i.3^{k-i}.j+(5^i.3^{k-1-i}-2)[/latex] pour i entre 1 et k-2, puis [latex]a_{k-1}=2.5^{k-2}.3.j+(2.5^{k-2}-1)[/latex]. Dans le deuxième cas, c'est pareil en rajoutant un facteur 2 devant le premier terme de la parenthèse. Je passe les calculs car c'est assez horrible, mais cela permet de se ramener à CM=3j+1 dans le premier cas, et CM=3j+2 dans le deuxième.

Par exemple, si CM=215, on a [latex]CM=3^4.2+(2.3^3-1)[/latex], donc on est dans le deuxième cas avec k=4, j=2. Les formules donnent [latex]a_1=358[/latex], [latex]a_2=598[/latex] et [latex]a_3=399[/latex] ce qui permet de se ramener à CM=8.

Il ne reste plus que le cas où CM=7 mod 9. On commence par prendre [latex]a_1=\frac{4CM-1}{3}[/latex], alors [latex]\frac{3a_i+1}{a_i+1}=\frac{2.CM}{(2CM+1)/3}[/latex]. Ce n'est pas suffisant car le facteur 2 au numérateur est en trop.

On écrit alors CM=9j+7 : si j=0 ou 1 mod 3, on prend [latex]a_2=\frac{a_1}{3}[/latex] et on se ramène à CM=j+1. Par exemple, si CM=61, on a 61=9.6+7, donc j=6, on a [latex]a_1=81[/latex], [latex]a_2=27[/latex], et on se ramène à CM=7.

Si j=2 mod 3, cette méthode ne marche pas car alors [latex]a_2+1[/latex] est multiple de 3. On remarque alors que [latex]\frac{2CM+1}{3}=6j+5[/latex] est de la forme 18m-1, donc on reprend la méthode compliquée ci-dessus : on écrit [latex]18m=3^{k-1}.(3j+(1\text{ ou }2))[/latex] et comme 18m est pair, le facteur 3j+(1 ou 2) est pair. La méthode compliquée permet ainsi de se ramener à un CM pair, dont le facteur 2 se simplifiera avec celui qui était de trop.

Par exemple, si CM=79, on obtient d'abord [latex]a_1=105[/latex] ce qui donne [latex]\frac{3a_1+1}{a_1+1}=\frac{2.79}{53}[/latex]. Puis on applique la méthode compliquée avec 53, ce qui donne [latex]a_2=88[/latex], [latex]a_3=148[/latex], [latex]a_4=99[/latex] et alors on retombe sur CM=1.

 #13 - 29-12-2017 17:28:43

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3437

cube et divoseurs

Je crois que tu as compris Ebichu. J'ai un chouïa plus synthétique en ramenant toujours les cas à des entiers impairs. Je rédigerai ma propre solution, tu pourras comparer.

 #14 - 01-01-2018 18:03:19

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3437

Cube et diviseur

Bon, peu de réponses sur ce sujet. Peut être un peu trop académique ?

On peut lire la solution d'Ebichu qui donne plusieurs solutions possibles parmi les plus petites.

Pour la généralité, Ebichu a donné aussi une réponse, j'ajoute la mienne un peu plus synthétique, pas forcément plus abordable.

Bonne année 2018 @ tous !

--------------------------------------------------------------------------------------------

Le nombre de diviseurs d(n) de n est le produit des ( pi+1 ), i de 1 à k, si p1, p2.....pk sont les puissances des nombres premiers de 1 à k qui composent n.
Le nombre de diviseurs d(n^3) de n ^ 3  est le produit des (3pi+1).

Dans quel cas peut on avoir d ( n^3 ) = C d(n) ?

Si d(n) est un multiple de 3, d(n^3) ne peut pas l'être puisque il est +1 modulo 3. C ne doit pas être muliple de 3

Si C est une puissance de 2, alors il suffit que p1 = p2 = ...pk = 1 car dans ce cas, d(n) = 2^k et d (n ^3 ) = 4 ^ k = (2 ^k) * d(n).
Comme toutes les parités de C peuvent être assurées, on ne s'intéresse qu'à C impair.

On peut toujours trouver C dans les autres cas par l'algorithme suivant.

On dit que C = C0 et on le remplacera par C1, puis C2, puis C3.... en opérant ainsi :

1) On cherche le plus petit multiple aC0 ( a = 1, 2, 4 ou 8 ) tel que aC0-1 est divisible par 3 et (aC0-1) / 3 + 1 n'est pas divisible par 3.

2) On recommence l'opération 1) à partir de C1 =( aC0-1) / 3 + 1, ou plus exactement C1 auquel on a ôté ses parités.   

Il faut démontrer que Cx est plus petit que C0 au bout de x itérations, ce qui permettrait à terme d' aboutir à Cx = 1

Cas 1 : C0 = 2 * 3 ^ j * k + 3 ^ j - 2  avec k différent de 1 [3]
C0 non utilisable tel que car (C0-1) / 3 + 1 divisible par 3. Il faut 4*C0.
-Dans d(n^3) : 3 * ( 2^3 * 3^(j-1) k + 2² * 3^(j-1) - 3 ) + 1
-Dans d(n) C1 = 2^3 * 3^(j-1) k + 2² * 3^(j-1) - 2
De la même forme que C0 avec les puissances de 2 incrémentées de 2 points et les puissances de 3 diminuées de 1 point.

On réitère alors l'opération ci dessus jusqu'à la dernière puissance de 3 :
C(j-1) = 2^(2j-1) * 3 k + 2^(2j-2) * 3 - 2. Utilisable directement. 
-Dans d(n^3) : 3 ( 2^(2j-1) * k + 2^(2j-2) -1 ) + 1
-Dans d(n) : C(j) = 2^(2j-1) * k + 2^(2j-2) ---------> 2 k + 1.   
C(j) < C0 et les facteurs pairs utilisés dans les d(n^3) successifs compensés par le dernier d(n).

 
Cas 2 : C0 = 2 * 3^j * k - 1, avec k premier avec 3.
2*C0 amènerait un C1 divisible par 3. On doit donc prendre 8*C0.
8*C0 :
- dans d(n^3) : 3 ( 2^4 * 3 ^ ( j - 1 ) * k  - 3 ) + 1
- dans d(n) C1 = 2^4 * 3 ^ ( j - 1 ) * k - 2--------> 2^3 * 3 ^ ( j - 1 ) * k - 1   
C1 est de la même forme que C0, sauf que la puissance de 2 a été incrémentée de 2 unités, et la puissance de 3 diminuée d'une unité.

L'opération ci-dessus est réitérée jusqu'a épuisement des puissances de 3.
C(j-1) = 2^(2j+1) * 3 k - 1
On utilise alors 2*C(j-1) :
-dans d(n^3) : 3 ( 2^(2j+2) * k - 1 ) + 1
-dans d( n) : C(j) = 2^(2j+2) * k -----> k après suppression des parités.
C(j) < C0 et les facteurs pairs utilisés dans les d(n^3) successifs compensés par le dernier d(n).

 #15 - 02-01-2018 17:59:03

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 691

Cube et diviserus

OK, j'ai relu : ta preuve est nettement plus rapide que la mienne tout de même, il y a beaucoup moins de cas à étudier. C'est bien plus élégant.

Juste un détail, mais qui ne remet pas en cause la validité de ta démonstration :

Si C est une puissance de 2, alors il faut et il suffit que p1 = p2 = ...pk = 1 car dans ce cas, d(n) = 2^k et d (n ^3 ) = 4 ^ k = (2 ^k) * d(n).

"Il suffit", oui, "il faut", non : par exemple, avec p1=21 et p2=7, on a (64/22)*(22/8)=8.

 #16 - 02-01-2018 19:34:16

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3437

Cue et diviseurs

Tu as raison, le " il faut " a été ajouté après une courte hésitation en cours de rédaction, sans vraiment de vérification, alors qu'il est inutile.
Je corrige.

 #17 - 02-01-2018 19:38:42

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 691

cube et fiviseurs

À part ça j'ai l'impression que tu as oublié gwen27 et moi-même sur le thread avec des "1" smile

 

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 31ème, en quelle position êtes-vous ?

Sujets similaires

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