Enigme Trouver n^3 = 123456789 mod (10^9) @ Prise2Tete

falcon · #1

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.

cogito · #2

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]
Indice n°2:Spoiler : [Afficher le message]

Indice n°3:Spoiler : [Afficher le message]

Indice n°4 : Spoiler : [Afficher le message]

Indice n°5 : Spoiler : [Afficher le message]

Indice n°6 :Spoiler : [Afficher le message].

Indice n°7 : Spoiler : [Afficher le message]

indice n°8:Spoiler : [Afficher le message]
Et Pour vérifier les résultats :
Spoiler : [Afficher le message]

EfCeBa · #3

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.

FRiZMOUT · #4

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

MthS-MlndN · #5

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

falcon · #6

Beaucoup de bonne réponse. Bravo !

Frizmout, combien de temps ton algorithme a t'il pris pour le calcul ?

FRiZMOUT · #7

Je dirais dans les 10 minutes (en Python) (bon OK c'est très lent, mais ça marche très bien quand même !)

dhrm77 · #8

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...

EfCeBa · #9

Allez pour rigoler, en php :

Code:

<?php
function test($fin,$ok,$etape){
 for ($i = 0; $i < 10; $i++) {
     if (bcmod(bcpow($i.$ok,3), bcpow(10,$etape)) == substr($fin,-$etape)) return $i.$ok;
 }
}

$heure_debut = microtime(true);
$fin = '123456789';
$debut = '';
for ($i = 1; $i <= strlen($fin); $i++) {
    $debut = test($fin,$debut,$i);
}
echo 'Résultat : '.$debut.' - temps de calcul :'.(microtime(true)-$heure_debut).'s';

Résultat : 464658829 - temps de calcul :0.00080585479736328s

dhrm77 · #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

falcon · #11

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.

MthS-MlndN · #12

Merdre, ça me rappelle les débuts de Vasimolo, ce genre de phrases

PapyJohn · #13

Je ne suis pas sur d'avoir compris

tu cherche la racine cubique?
Papy

PapyJohn · #14

Et cela c'est pas joli?

987654321 * 9 = 8888888889

Papy

dhrm77 · #15

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.

PapyJohn · #16

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

MthS-MlndN · #17

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...

kosmogol · #18

MthS-MlndN a écrit:
Merdre, ça me rappelle les débuts de Vasimolo, ce genre de phrases

Vasimolo · #19

Mathias et Kosmo , vous pouvez approcher un peu

Encore un peu ...

Spoiler : [Afficher le message]

Voilà , c'est bon , vous pouvez retourner à vos occupations

Vasimolo

kosmogol · #20

ah non pas ça, pitié

TiLapiot · #21

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

nodgim · #22

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..

MthS-MlndN · #23

Idée développée dans mon post (#5).

nodgim · #24

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.

MthS-MlndN · #25

Exact, ça marche pas mal, et encore plus "a la main" ^^

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#1 - 11-06-2010 20:56:02

Trouver n^3 = 123546789 mod (10^9)

#0 Pub

#2 - 12-06-2010 00:03:35

Trouve n^3 = 123456789 mod (10^9)

#3 - 12-06-2010 00:06:21

Trouver n^3 = 123456789 mdo (10^9)

#4 - 12-06-2010 01:36:24

Trouver n^3 = 1123456789 mod (10^9)

#5 - 12-06-2010 12:05:09

Trouvre n^3 = 123456789 mod (10^9)

#6 - 12-06-2010 15:47:07

rTouver n^3 = 123456789 mod (10^9)

#7 - 12-06-2010 18:04:22

Trouvver n^3 = 123456789 mod (10^9)

#8 - 12-06-2010 19:00:01

troucer n^3 = 123456789 mod (10^9)

#9 - 12-06-2010 19:35:26

Trouver n^3 = 12345789 mod (10^9)

Code:

#10 - 12-06-2010 19:54:14

Trouver n^ = 123456789 mod (10^9)

#11 - 13-06-2010 11:09:04

Trouver n^ = 123456789 mod (10^9)

#12 - 13-06-2010 13:08:32

trouver n^3 = 123456789 mid (10^9)

#13 - 13-06-2010 20:50:45

Trouver n^33 = 123456789 mod (10^9)

#14 - 16-06-2010 08:11:44

Trouver n^3 = 123456789 mo d(10^9)

#15 - 16-06-2010 13:03:25

Trouver n^3 = 123456789 mod (1^9)

PapyJohn a écrit:

#16 - 16-06-2010 19:40:45

Trouver n^3 = 123456789 mo (10^9)

#17 - 16-06-2010 19:42:24

Trouver n^3 = 123456789 mod 10^9)

#18 - 16-06-2010 19:50:25

Trrouver n^3 = 123456789 mod (10^9)

MthS-MlndN a écrit:

#19 - 16-06-2010 22:40:47

Trouver n^3 = 12356789 mod (10^9)

#20 - 16-06-2010 23:18:47

Trouver n^33 = 123456789 mod (10^9)

#21 - 13-09-2011 23:44:17

Trouver n^3 = 123456789 mod (10^9

#22 - 14-09-2011 18:39:52

Trouver n^3 = 12345678 mod (10^9)

#23 - 14-09-2011 18:56:32

trouver b^3 = 123456789 mod (10^9)

#24 - 14-09-2011 21:40:25

Trouver n^3 = 123456789 mod (10^^9)

#25 - 15-09-2011 08:50:56

Trouver n^3 = 123456879 mod (10^9)

Réponse rapide

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums