 |
#1 - 26-12-2017 10:53:43
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3828
cybe 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 ?
#2 - 26-12-2017 18:19:28
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
Cube e diviseurs
Sauf erreur de calcul, 21197.3897.5672.7399.11133.1322.1715 convient pour 2017, et 2336.3112.575.725.114.133.17.19 convient pour 2018.
#3 - 26-12-2017 19:31:25
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3828
ube et 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 : 888
Cube et diviiseurs
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 : 3828
Cube et idviseurs
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 : 888
cube et divisrurs
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 : 888
cube er diviseurs
Ç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 : 3234
- Lieu: Luxembourg
cube et doviseurs
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 : 3828
Cube et diivseurs
@ 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
cube er diviseurs
Je Sais pas comment commencer.
#11 - 29-12-2017 10:56:48
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
Cube et diviseusr
J'ai mieux à proposer pour 2017 : 2897.3748.5672.7499.1133.1328.1719, ou bien 2897.3748.5672.7499.113.133.17.19.
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 
#12 - 29-12-2017 11:58:12
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
cube et diviseurq
Si n=Πpaii, alors le nombre de diviseurs de n est Π(ai+1), et celui de n³ est Π(3ai+1). On recherche donc des entiers ai tels que le coefficient multiplicateur CM soit égal à Π3ai+1ai+1.
Si CM est multiple de 3, ce n'est pas possible car aucun des (3ai+1) 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 ai qui permettent de se ramener à un CM strictement plus petit (et qui ne soit pas multiple de 3). Par exemple, en prenant a1=672, 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 ai 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 ai=CM−13. Par exemple, si CM=31, on prend ai=10, 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 CM+1=3k−1.m où 3 ne divise par m, donc m=3j+1 ou 3j+2, et il vient CM=3k.j+(3k−1−1) ou CM=3k.j+(2.3k−1−1) avec k>1 et j>=0.
Dans le premier cas, on prend ai=5i.3k−i.j+(5i.3k−1−i−2) pour i entre 1 et k-2, puis ak−1=2.5k−2.3.j+(2.5k−2−1). 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 CM=34.2+(2.33−1), donc on est dans le deuxième cas avec k=4, j=2. Les formules donnent a1=358, a2=598 et a3=399 ce qui permet de se ramener à CM=8.
Il ne reste plus que le cas où CM=7 mod 9. On commence par prendre a1=4CM−13, alors 3ai+1ai+1=2.CM(2CM+1)/3. 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 a2=a13 et on se ramène à CM=j+1. Par exemple, si CM=61, on a 61=9.6+7, donc j=6, on a a1=81, a2=27, et on se ramène à CM=7.
Si j=2 mod 3, cette méthode ne marche pas car alors a2+1 est multiple de 3. On remarque alors que 2CM+13=6j+5 est de la forme 18m-1, donc on reprend la méthode compliquée ci-dessus : on écrit 18m=3k−1.(3j+(1 ou 2)) 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 a1=105 ce qui donne 3a1+1a1+1=2.7953. Puis on applique la méthode compliquée avec 53, ce qui donne a2=88, a3=148, a4=99 et alors on retombe sur CM=1.
#13 - 29-12-2017 17:28:43
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3828
Cube et iviseurs
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 : 3828
cube et diviseues
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 : 888
Cube et divseurs
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 : 3828
cube et diviszurs
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 : 888
uCbe et diviseurs
À part ça j'ai l'impression que tu as oublié gwen27 et moi-même sur le thread avec des "1" 
|
 |