|
#1 - 11-06-2010 20:56:02
- falcon
- Professionnel de Prise2Tete
- Enigmes résolues : 26
- Messages : 106
Trouver ^n3 = 123456789 mod (10^9)
Un petit problème d'arithmétique
Montrez qu'il existe un entier naturel n donc l'écriture du cube en décimal se termine par 123456789.
Autrement dit n^3 = 123456789 (10^9)
Si quelqu'un trouve une façon efficace de trouver ce nombre via informatique cela m'intéresse. J'ai essayer sans succès avant de me pencher sur un véritable raisonnement.
Il vaut mieux pomper meme s'il ne se passe rien que risquer qu'il se passe quelque chose de pire en ne pompant pas
#2 - 12-06-2010 00:03:35
- cogito
- Expert de Prise2Tete
- Enigmes résolues : 48
- Messages : 593
Toruver n^3 = 123456789 mod (10^9)
Bonjour à tous, Normalement avec les indices 1 et 4 on a tous les éléments pour trouver la solution. Indice n°1 : Spoiler : [Afficher le message] il faut se préoccuper seulement du chiffre des unités. Indice n°2:Spoiler : [Afficher le message] La seul façon que le cube d'un nombre se termine par un 9 c'est que ce nombre lui même se termine par un 9.
Indice n°3:Spoiler : [Afficher le message] Donc ce nombre s'écrit [TeX]$$ m * 10 + 9$$[/latex]
Indice n°4 : Spoiler : [Afficher le message] [latex]$(a + b)^3 = a^3 + 3a^2b + 3ab^2 + b^3$[/latex]
Indice n°5 : Spoiler : [Afficher le message] Dans [latex]$(m * 10^k +\bar{a9})^3$[/latex] la seul parite qui nous intéresse est :
[latex]$3 * m * 10^k * \bar{a9}^2$[/TeX] où [latex]$\bar{a9}$ [/latex] est le nombre construit au fur et à mesure, car ce nombre ce termine par un 9 donc son carré se termine par un 1 et donc le triple se termine forcément par un 3 .
Indice n°6 :Spoiler : [Afficher le message] Et donc si le chiffre des unités à chercher est par exemple 7 alors le chiffre des unités de m sera forcément 9 et le nouveau nombre [TeX]$\bar{a9}$[/latex] devient [latex]$\bar{9a9}$[/latex] .
Indice n°7 : Spoiler : [Afficher le message] Si tout est bien fait à chaque étape quand on fait
[latex]$123456789 - \bar{a9}^3$[/TeX] on dois avoir un zero de plus à chaque fois et le premier chiffre non nul est ton nouveau chiffre unité que l'on dois trouver.
indice n°8:Spoiler : [Afficher le message] Attention si le nombre est négatif le chiffre à trouver est son complementaire (10 -le chiffre. par exemple si on a [TeX] $ 123456789 - \bar{a9}^3 = - 7454230000 $[/TeX] (exemple pris au hasard ) alors le chiffres des unités à trouver est 7= (10 -3) (et donc le chiffre à ajouter à notre nombre est 9 (indice 6). Et Pour vérifier les résultats : Spoiler : [Afficher le message] Les nombres entiers se terminant par 464658829 sont les nombres dont le cube se termine par 123456789.
Il y a sûrement plus simple.
#3 - 12-06-2010 00:06:21
- EfCeBa
- Administrateur
- Enigmes résolues : ∞+1
- Messages : 11×569
trouver n^3 = 123456789 mpd (10^9)
Le calcul doit se faire sans trop de difficulté informatiquement, notamment grâce à l'exponentiation modulaire (a^b mod n) http://fr.wikipedia.org/wiki/Exponentiation_modulaire
Sinon, à la main, je peux te dire que ce nombre fini par 9 (seul chiffre dont le cube fini par 9), voire par 29 (seul nombre dont le dernier chiffre est 9 et dont le cube fini par 89) etc.
J'ai écris un programme qui fait ces tests mais je suis limité par la capacité des entiers aux cinq derniers chiffres qui sont (normalement) 58829.
#4 - 12-06-2010 01:36:24
- FRiZMOUT
- Verbicruciste binairien
- Enigmes résolues : 49
- Messages : 2218
Trouve rn^3 = 123456789 mod (10^9)
464658829
Un algo naïf crétin marche très bien !
Un truc du genre :
nombre = 0 tant qu'on n'a pas trouvé le bon nombre : si nombre^3 modulo 10^9 = 123456789 : afficher le nombre (et quitter l'algo) sinon : incrémenter le nombre
#5 - 12-06-2010 12:05:09
- MthS-MlndN
- Hors d'u-Sage
- Enigmes résolues : 49
- Messages : 12,414E+3
- Lieu: Rouen
Troouver n^3 = 123456789 mod (10^9)
Je tenterais bien une remontée récursive. Je m'explique :
Si je veux que le cube d'un nombre finisse par 9, le nombre doit finir par 9 ([latex]9^3 = 729[/latex] alors que les autres cubes de nombres sous 10 finissent par d'autres chiffres).
Mon nombre est de la forme [latex](10 k_1 + 9)[/latex], et : [TeX](10 k_1 + 9)^3 = 1000 k_1^3 + 2700 k_1^2 + 2430 k_1 + 729[/TeX] Le chiffre des dizaines sera dicté par les deux derniers termes de ce développement : [latex]2430 k_1 + 729[/latex]. Il sera même égal à [latex]3 k_1 + 2 [10][/latex]. On sait qu'il doit valoir 8, donc le chiffre des unités de [latex]k_1[/latex] est un 2. Le nombre n recherché se termine donc par 29 : [latex]n = 100 k_2 + 29[/latex]. On est reparti pour un tour ? [TeX](100 k_2 + 69)^3 = 1000000 k_2^3 + 870000 k_2^2 + 252300 k_2 + 24389[/TeX] Le chiffre des centaines sera [latex]3 k_2 +3 [10][/latex] et doit valoir 7, donc [latex]k_2[/latex] se termine par un 8 et [latex]n=1000k_3 + 829[/latex]. [TeX](1000k_3 + 829)^3 = 10^9 k_3^3 + 2487 \times 10^6 k_3^2 + 2061723 \times 10^3 k_3 + 569722789[/latex] donc [latex]3 k_3 + 2[/latex] se termine par un 6, donc [latex]k_3[/latex] se termine par un 8 : [latex]n=10000k_4 + 8829[/latex]. On peut continuer ainsi en remarquant qu'on écrit toujours le chiffre à rajouter de la même façon...
[latex]8829^3 = 688231506789[/latex] donc on ajoute le chiffre 5 à gauche, car [latex]3 \times 5 + 0 \equiv 5 [10][/latex].
[latex]58829^3 = 203598417656789[/latex] donc on rajoute un 6 à gauche car [latex]3 \times 6 + 6 \equiv 4 [10][/TeX] Quelques itérations plus tard : [latex]464658829^3=100323478236586978123456789[/latex]
Donc la réponse est 464 658 829.
La réponse ?! Allez, un petit complément quand même : ce nombre est le plus petit dont le cube se termine par 123456789 en décimal... Mais tous les nombres de la forme [latex]k \times 10^{9} + 464658829[/latex] avec k entier positif sont solution du problème
Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298
#6 - 12-06-2010 15:47:07
- falcon
- Professionnel de Prise2Tete
- Enigmes résolues : 26
- Messages : 106
Trouver n^3 = 123456789 mod 10^9)
Beaucoup de bonne réponse. Bravo !
Frizmout, combien de temps ton algorithme a t'il pris pour le calcul ?
Il vaut mieux pomper meme s'il ne se passe rien que risquer qu'il se passe quelque chose de pire en ne pompant pas
#7 - 12-06-2010 18:04:22
- FRiZMOUT
- Verbicruciste binairien
- Enigmes résolues : 49
- Messages : 2218
Trouvr n^3 = 123456789 mod (10^9)
Je dirais dans les 10 minutes (en Python) (bon OK c'est très lent, mais ça marche très bien quand même !)
#8 - 12-06-2010 19:00:01
- dhrm77
- L'exilé
- Enigmes résolues : 49
- Messages : 3004
- Lieu: Fanning Island-?-Lac Tele,Mali
Trouver n^3 = 123456789 mod (10^9
464658829^3 = 100323478236586978123456789 on peut dire mieux: 4464658829^3 = 88994841198648401870123456789
62570834584464658829^3 = 244971658930552267821098374702295578019609876543210123456789
64063457744464658829^3 = 262924542181502636163825384657189342939601234567890123456789
PS: le programme prend a peine une fraction de seconde sur un ordinateur normal. Je n'ai pas mesuré, mais c'est quasiment instantané, meme pour les cubes de 20 chiffres. PPS: J'ai d'autres programmes qui font des recherches de nombres a propriétés particulieres jusqu'a 2^65520 ( soit quelques 19724 chiffres ...), donc des nombres a 20 ou 60 chiffres, sont petits en comparaison...
Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt
#9 - 12-06-2010 19:35:26
- EfCeBa
- Administrateur
- Enigmes résolues : ∞+1
- Messages : 11×569
trouver n^3 = 123456789 lod (10^9)
Allez pour rigoler, en php :
Résultat : 464658829 - temps de calcul :0.00080585479736328s
#10 - 12-06-2010 19:54:14
- dhrm77
- L'exilé
- Enigmes résolues : 49
- Messages : 3004
- Lieu: Fanning Island-?-Lac Tele,Mali
Trouver n^3 = 123456789 mod (10^)
On peut aussi avoir: 79858716637368288471^3 = 509292147254569119612816584076634854512511111111111111111111 15015138644385446477^3 = 3385228901464551304619645329943776378133333333333333333333 59631497233899660753^3 = 212044563057497605947980729786976737753277777777777777777777 34717433274736576942^3 = 41844928338605982466290241935271559338588888888888888888888 84717433274736576942^3 = 608020703876998281643287214206394470043188888888888888888888 09717433274736576942^3 = 917602739803078176541755799710103986288888888888888888888 59717433274736576942^3 = 212962628717671050288538728070833014690888888888888888888888 99999999999999999999^3 = 999999999999999999970000000000000000000299999999999999999999
Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt
#11 - 13-06-2010 11:09:04
- falcon
- Professionnel de Prise2Tete
- Enigmes résolues : 26
- Messages : 106
Trouver n^3 = 132456789 mod (10^9)
99999999999999999999^3 = 999999999999999999970000000000000000000299999999999999999999
ça c'est joli !
Je ramènerais un problème plus difficile la prochaine fois, vous avez résolu trop facilement celui ci.
Il vaut mieux pomper meme s'il ne se passe rien que risquer qu'il se passe quelque chose de pire en ne pompant pas
#12 - 13-06-2010 13:08:32
- MthS-MlndN
- Hors d'u-Sage
- Enigmes résolues : 49
- Messages : 12,414E+3
- Lieu: Rouen
Trouver n^3 = 132456789 mod (10^9)
Merdre, ça me rappelle les débuts de Vasimolo, ce genre de phrases
Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298
#13 - 13-06-2010 20:50:45
- PapyJohn
- Habitué de Prise2Tete
- Enigmes résolues : 0
- Messages : 49
Trouver n^3 = 123456789 mod ((10^9)
Je ne suis pas sur d'avoir compris
tu cherche la racine cubique? Papy
#14 - 16-06-2010 08:11:44
- PapyJohn
- Habitué de Prise2Tete
- Enigmes résolues : 0
- Messages : 49
Trouver n^3 == 123456789 mod (10^9)
Et cela c'est pas joli?
987654321 * 9 = 8888888889
Papy
#15 - 16-06-2010 13:03:25
- dhrm77
- L'exilé
- Enigmes résolues : 49
- Messages : 3004
- Lieu: Fanning Island-?-Lac Tele,Mali
Trouver n^3 = 123456789 mod (110^9)
PapyJohn a écrit:Je ne suis pas sur d'avoir compris
tu cherche la racine cubique? Papy
En fait on cherchais la racine cubique d'un nombre qui se termine par 123456789, et dont la racine cubiques est un entier. Ce qui revient a dire que l'on cherche un entier dont le cube se termine par 123456789. J'ai étendu le probleme a la recherche d'un entier dont le cube se termine par n'importe quel serie de chiffres un peu particuliere.
Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt
#16 - 16-06-2010 19:40:45
- PapyJohn
- Habitué de Prise2Tete
- Enigmes résolues : 0
- Messages : 49
Trouvver n^3 = 123456789 mod (10^9)
Je vais peut être dire une bêtise mais tapez pas sur la tete:
Moi j'aurai explore la voie suivante
si mon cube doit de terminer par 12345679 il est donc obligatoire que la racine cubique termine mon nombre
donc tu prends une terminaison quelquonque et tous les nomnres de terminant par cette racine sont bons
Mais je n"ai pas essayé c'est peut etre complément faux c'est un peu le principe du 3 a la fin
Informatiquement cela va plus vite comment?
Papy
#17 - 16-06-2010 19:42:24
- MthS-MlndN
- Hors d'u-Sage
- Enigmes résolues : 49
- Messages : 12,414E+3
- Lieu: Rouen
Trouver n^3 = 1234566789 mod (10^9)
si mon cube doit de terminer par 12345679 il est donc obligatoire que la racine cubique termine mon nombre
Pas forcément... Ton entier N devrait alors se finir par 493,933859...
Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298
#18 - 16-06-2010 19:50:25
- kosmogol
- Banni
- Enigmes résolues : 49
- Messages : 11,928E+3
Trouver nn^3 = 123456789 mod (10^9)
http://enigmusique.blogspot.com/
#19 - 16-06-2010 22:40:47
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,397E+3
Trouvre n^3 = 123456789 mod (10^9)
#20 - 16-06-2010 23:18:47
- kosmogol
- Banni
- Enigmes résolues : 49
- Messages : 11,928E+3
Trouver n^3 123456789 mod (10^9)
ah non pas ça, pitié
http://enigmusique.blogspot.com/
#21 - 13-09-2011 23:44:17
- TiLapiot
- Expert de Prise2Tete
- Enigmes résolues : 16
- Messages : 852
- Lieu: au terrier ;^)
Troouver n^3 = 123456789 mod (10^9)
(Sans regarder vos précédents posts)
On remarque d'abord qu'il faut que N finisse par 9 pour que son cube N^3 finisse par 9.
Puis, avec Excel, en calculant 9^3, 19^3, 29^3, 39^3, etc... on remarque qu'il faut que N finisse par 29 pour que N^3 finisse par "89"
De même, en calculant 29^3, 129^3, 229^3, 329^3, etc... on remarque qu'il faut que N finisse par 829 pour que N^3 finisse par "789"
En calculant 829^3, 1829^3, 2829^3, 3829^3, etc... on remarque qu'il faut que N finisse par 8829 pour que N^3 finisse par "6789"
En calculant 8829^3, 18829^3, 28829^3, 38829^3, etc... on remarque qu'il faut que N finisse par 58829 pour que N^3 finisse par "56789"
Ensuite, mon Excel m'affiche systématiquement l'erreur #NOMBRE, car le cube est sûrement trop grand pour être affiché en entier :
Alors, on va pas abandonner en si bon chemin, et je demande à Wolfram qui ne tarde pas à trouver la réponse :
#22 - 14-09-2011 18:39:52
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Trouver n^3 = 123456789 mod 10^9)
Sans avoir trop réfléchi sur le sujet: on peut tout de même assez facilement trouver la terminaison d'un cube en cherchant la terminaison de la racine cubique: l'unité est 9, pas d'autre solution. Chercher la dizaine qui donnera 8, puis la centaine, etc..
#23 - 14-09-2011 18:56:32
- MthS-MlndN
- Hors d'u-Sage
- Enigmes résolues : 49
- Messages : 12,414E+3
- Lieu: Rouen
Trouver n^3 = 12456789 mod (10^9)
Idée développée dans mon post (#5).
Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298
#24 - 14-09-2011 21:40:25
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Trouver n^3 = 123456789 mod 10^9)
Oui d'accord MthS. J'ajouterai un petit complément: pour trouver le chiffre suivant, on part de (10a+b)^3=...+30ab²+b^3. On calcule le 30b² et on repère le rang du chiffre qui nous intéresse, on y ajoute le chiffre du b^3 correspondant et on trouve ainsi facilement le a.
#25 - 15-09-2011 08:50:56
- MthS-MlndN
- Hors d'u-Sage
- Enigmes résolues : 49
- Messages : 12,414E+3
- Lieu: Rouen
Trouver n^33 = 123456789 mod (10^9)
Exact, ça marche pas mal, et encore plus "a la main" ^^
Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298
Mots clés des moteurs de recherche
|
|