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 - 20-06-2011 10:41:47

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1934

Calculons peu, alculons bien

Armé d'un papier et d'un crayon, je ne calcule pas 5^16 avec 15 multiplications, puisque 4 suffisent.
Preuve par l'exemple
5 * 5 = 25
25 * 25 = 625 = 5^4
625 * 625 = 390625 = 5^8
390625 * 390625 = 152587890625 = 5^16

Quelle est la plus petite puissance 5^a de 5 que je ne puisse calculer en 5 multiplications ? Et en 6 multiplications pour 5^b ? Enfin en 7 pour 5^c?
La case réponse valide les trois nombres a,b,c écrits dans ce format


 
Réponse :
  • |
  • Répondre

#0 Pub

 #2 - 20-06-2011 13:51:18

fabb54
Habitué de Prise2Tete
Enigmes résolues : 20
Messages : 37

calculons peu, calculins bien

J'ai trouvé pour 5, 6 et 7 multiplications les puissances  19, 23 et 43.

 #3 - 20-06-2011 14:30:54

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 914
Lieu: Seahaven island

calculond peu, calculons bien

Salut,
Je ne comprend pas trop ou je me suis fourvoyé, je trouve 15,23,31

 #4 - 20-06-2011 14:37:52

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1934

camculons peu, calculons bien

@fabb54: le 1er est ok.
@Clydevil: aucun n'est bon

 #5 - 20-06-2011 15:02:05

rivas
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1106
Lieu: Jacou

Calculons peuu, calculons bien

Je trouve 19,29 et 47...
Je détaillerai un peu plus tard. smile

A NOTER:
Si on ne peut multiplier que par des puissances de 5 supérieures ou égales à 5, alors la plus petite qu'on ne puisse pas obtenir dans les 3 cas est la même: 5 (ou même 1).

 #6 - 20-06-2011 15:15:13

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 914
Lieu: Seahaven island

Calculons peu, calculons bienn

Ha l'exponentiation rapide n'est pas le plus rapide...  Damned, première nouvelle!!
Merci pour cette énigme qui corrige une lacune. smile

 #7 - 20-06-2011 16:02:59

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,896E+3

calcylons peu, calculons bien

11 , un arbre des possiblités le montre assez facilement.

 #8 - 20-06-2011 16:37:22

Nicouj
Professionnel de Prise2Tete
Enigmes résolues : 27
Messages : 330

Calculons peu, calculons bin

5^(2n) = 5^n * 5^n
5^(2n+1) = 5^n * 5^n * 5

En appliquant cette méthode, si j'écris n en binaire et que j'oublie le bit de poids fort, chaque 1 apporte 2 multiplications et chaque 0 en apporte 1.

Le plus petit n tel que 5^n nécessite au moins 6 multiplications est donc au moins 15.  (1111)
Le plus petit n tel que 5^n nécessite au moins 7 multiplications est donc au moins 23.  (10111)
Le plus petit n tel que 5^n nécessite au moins 8 multiplications est donc au moins 31.  (11111)

Pour 5^15 je trouve en 5 :
5^2 = 5*5
5^3= 5^2*5
5^5= 5^3*5^2
5^15= 5^5*5^5*5^5
J'essaie avec le suivant 5^19 (10011) je trouve rien en mieux que 6 multiplications

Pour 23 j'arrive 6 multiplications en faisant
5^2 = 5*5,
5^7 = 5^2*5^2*5^2*5
5^23 = 5^7*5^7*5^2
J'essaie avec le suivant 5^27 (11011), je trouve en 6
J'essaie avec le suivant 5^29 (11101), je ne trouve rien en 6

Pour 5^31 je trouve en 7 :
5^15 = 5^15*5^15*5
J'essaie avec le suivant 5^39 (100111) je trouve en 7 (1, 2, 4, 6, 12, 13, 26, 39)
J'essaie avec le suivant 5^43 (101011) je trouve en 7 (1, 2, 3, 5, 10, 20, 40, 43)
J'essaie avec le suivant 5^45 (101101) je trouve en 7 (1, 2, 3, 5, 10, 15, 30, 45)
J'essaie avec le suivant 5^46 (101110) je trouve en 7 (1, 2, 3, 5, 10, 20, 23, 46)
J'essaie avec le suivant 5^51 (110011) je ne trouve rien pour l'instant

Pour l'instant je trouve au moins 5^19, 5^29, 5^51

 #9 - 20-06-2011 16:53:46

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1934

Calculons peu, calculnos bien

@gwen: il y a 3 questions... (ceci dit, ta réponse n'est pas correcte tongue )
@Nicouj: 2 sur 3. J'ai eu du mal à comprendre comment tu sautes des cas, fait bien attention

 #10 - 20-06-2011 17:09:24

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,896E+3

xalculons peu, calculons bien

Oui, j'étais resté sur 4 lol Je m'y colle ce soir, un arbre marche très bien quand même.

 #11 - 20-06-2011 17:28:45

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 914
Lieu: Seahaven island

Calcullons peu, calculons bien

he be.
19,29,47!
On peut minorer déjà avec l'exponentiation rapide.
par exemple pour ^23 qui en binaire donne 10111
on sait qu'il faut 1+2+2+2 = 6  (on lit les digits de gauche a droite sans le premier 0 compte 1 et 1 compte 2)
Donc l'exponentiation rapide ne suffit pas à faire ^23 en moins de 6 multiplications (et c'est le premier de ce genre car sans compter le premier il faut 4 digits dont 3 digit à 1)
Il suffit donc de traiter le cas à la main et de passer au suivant que l'exponentiation rapide ne sait pas traiter optimalement à savoir:
11011  (27) on y arrive donc suivant
puis
11101  (29)
pfiou!

"@Nicouj: 2 sur 3. J'ai eu du mal à comprendre comment tu sautes des cas, fait bien attention"
Par contre je ne vois pas pourquoi ca t'étonne qu'il saute des cas, je ne vois pas de manière générique de traitement.

Et ca semble être un probleme non résolu dans le cas général justement.
http://oeis.org/search?q=1%2C2%2C3%2C5% … ;go=Search
et/ou
http://en.wikipedia.org/wiki/Addition_chain

 #12 - 20-06-2011 17:36:49

Nicouj
Professionnel de Prise2Tete
Enigmes résolues : 27
Messages : 330

CCalculons peu, calculons bien

Je compte le nombre de multiplications que va donner la méthode dichotomique.

5^(2n) = 5^n * 5^n   
5^(2n+1) = 5^n * 5^n * 5

Je regarde les bits en base 2.
Donc mis à part le 1 de tête, les '0' signifient 1 multiplication et les '1' deux multiplications en utilisant la méthode dichotomique.
Je peux donc déjà éliminer tous les cas ou j'ai moins de multiplication en comptant comme ça.

En revanche j'ai éliminé tous ceux dont la somme était différente au lieu de strictement inférieure ><

Donc apres 46 (101110), j'ai oublié 47 (101111) qui nécessite au moins 8 multiplications big_smile


J'ai écrit un petit algo et les réponses suivantes sont 71, 127, 191

En python :

Code:

def min_mult(nb_mult):
    if nb_mult % 2 == 1:
        n = (1 << (2 + nb_mult // 2)) -1
    else: 
        n = (1 << (1 + nb_mult // 2)) + (1 << (nb_mult // 2)) -1 
    while min_mult_aux(n, [1], nb_mult):
        n = n+1
    return n

def min_mult_aux(n, l, nb_mult):
    if n in l: 
        return True
    elif nb_mult <= 0:
        return False
    else:
        max = l[0]
        for x in l:
            l.insert(0, x+ max)
            if min_mult_aux(n, l, nb_mult-1):
                return True
            else:
                l.pop(0)
        return False

 #13 - 20-06-2011 17:58:25

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2010
Lieu: Paris

Calculons peu, callculons bien

5 : 0 multiplication
5^2 : 1 multiplication
5^3 : 2
5^4 : 2 => 5^2 * 5^2
5^5 : 3 => 5^2 * 5*2 * 5
5^6 : 3 => 5*5*5, puis ^2
5^7 : 4 => 5*(5*5*5)^2
5^8 : 3 => ((5*5)^2)^2
5^9 : 4 => 5*5^8
5^10 : 4 => (5*((5*5)^2))^2
5^11 : 5 => 5*5^10
5^12 : 4 => ((5*5*5)^2))^2
5^13 : 5 => 5*5^12
5^14 : 5 => (5^7)^2
5^15 : 5 => (5^5)*(5^5)*(5^5)
5^16 : 4 => exemple
5^17 : 5 => 5*5^16
5^18 : 5 => ((5*5*5)^2)^3
5^19 : 6 => 5*5^18 : c'est le premier qui nécessite au moins 6 multiplications
5^20 : 5 => (5^5)^4
5^21 : 6 => (5^7)^3
5^22 : 6 => (5^11)^2
5^23 : 7 => 5*5^22 : c'est le premier qui nécessite au moins 7 multiplications
5^24 : 5 => (5^8)^3
5^25 : 6 => 5*5^24
5^26 : 6 => (5^13)^2
5^27 : 6 => (5^9)^3
5^28 : 6 => (5^14)^2
5^29 : 7 => 5*5^28
5^30 : 6 => (5^15)^2
5^31 : 7 => 5*5^30
5^32 : 5 => (5^16)^2
5^33 : 6 => 5*5^32
5^34 : 6 => (5^17)^2
5^35 : 7 => 5*5^34
5^36 : 6 => (5^9)^4
5^37 : 7 => 5*5^36
5^38 : 7 => (5^19)^2
5^39 : 7 => (5^13)^3
5^40 : 6 => (5^20)^2
5^41 : 7 => 5*5^40
5^42 : 7 => (5^21)^2
5^43 : 8 => 5*5^42 : c'est le premier qui nécessite au moins 8 multiplications

La case réponse devrait donc valider :
5^19,5^23,5^43
Mais ce n'est pas le cas hmm
J'ai soit mal compris l'énoncé, soit je me suis plantouillé dans mes multiplications !

 #14 - 20-06-2011 18:11:20

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1934

Calculons peu ,calculons bien

Bonnes réponses de Clydevil et de Nicouj
@L00ping : je n'ai jamais dit que chaque calcul devait tenir sur une ligne, ton erreur vient de là (enfin, tu as toujours 33% de correct)

 #15 - 20-06-2011 18:36:42

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

Calculoons peu, calculons bien

Bon, je vais réessayer :

5^3 --> 2 opérations
5^4 --> 2 opérations
5^5 --> 3 opérations
5^6 --> 3 opérations
5^7 --> 4 opérations
5^8 --> 3 opérations
5^9 --> 4 opérations
5^10 --> 4 opérations
5^11 --> 5 opérations
5^12 --> 4 opérations
5^13 --> 5 opérations
5^14 --> 5 opérations
5^15 --> 5 opérations
5^16 --> 4 opérations
5^17 --> 5 opérations
5^18 --> 5 opérations
5^19 --> 6 opérations
5^20 --> 5 opérations
5^21 --> 6 opérations
5^22 --> 6 opérations
5^23 --> 6 opérations
5^24 --> 5 opérations
5^25 --> 6 opérations
5^26 --> 6 opérations
5^27 --> 6 opérations
5^28 --> 6 opérations
5^29 --> 7 opérations
5^30 --> 6 opérations
5^31 --> 7 opérations
5^32 --> 5 opérations
5^33 --> 6 opérations
5^34 --> 6 opérations
5^35 --> 7 opérations
5^36 --> 6 opérations
5^37 --> 7 opérations
5^38 --> 7 opérations
5^39 --> 7 opérations
5^40 --> 6 opérations
5^41 --> 7 opérations
5^42 --> 7 opérations
5^43 --> 7 opérations
5^44 --> 7 opérations
5^45 --> 7 opérations
5^46 --> 7 opérations
5^47 --> 8 opérations

Je tente donc 19,29,47, et ça marche, après plusieurs tentatives, plusieurs révisions, et plusieurs "ah oui, je suis con, j'ai qu'à créer le 2^k au début et je m'en ressers à la fin", avec k valant 3 une fois, 5 la fois suivante...


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #16 - 20-06-2011 18:38:09

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,896E+3

Calculons pe, calculons bien

19 35 67 ?

 #17 - 20-06-2011 18:54:42

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1934

Calculons peu, calculons bienn

Bravo à  Mathias
@gwen: 1 de bon, mais je te conseille de revoir ta méthode

 #18 - 20-06-2011 22:25:35

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,896E+3

Calculns peu, calculons bien

Après MP , merci (35 n'est pas le pus petit....)  : 19,31...????

Oups, zappé 29, il faut que je vérifie.

 #19 - 20-06-2011 22:51:12

rivas
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1106
Lieu: Jacou

Calculons peu ,calculons bien

J'ai procédé en construisant les solutions.
Il y a sans doute plus élégant dans l'abstraction.

Je regarde les exposants des puissances de 5 uniquement.
Pour le premier nombre on utilise 5 donc l'exposant 1.
Après la première multiplication, on a donc à notre disposition les exposants 1 et 2.
Après la troisième multiplication on a à notre disposition les exposants 1 et 2 et les combinaisons de ceux-ci: 3 et 4.
Ensuite il faut faire un arbre pour ne pas utiliser des exposants qu'on n'a pas obtenu lors de notre série d'opération.
Par exemple si on a fait 5*5=25 et 25*25=625, les exposants que nous avons sont 1, 2, 4 mais pas 3 qui est dans la branche 1, 2, 3.
L'arbre ressemble donc à ceci:

Code:

   1
   2
3    4

On construit chaque niveau de l'arbre à partir d'une des feuilles actuelles en lui adjoingnant comme feuilles filles toutes les combinaisons obtenus par addition de 2 exposants figurant dans ses antécédents.
Le niveau suivant ressemble donc à

Code:

     1
     2
 3      4
456    568

(Ne pas oublier 2 fois lui-même à chaque niveau).
En construisant ainsi 5 niveaux, on s'aperçoit que le plus petit nombre que l'on n'obtient pas est 19.

En continuant 2 niveaux de plus on trouve 29 et 47. (Un peu fastidieux pour le niveau 7, j'ai fait un petit programme).

 #20 - 21-06-2011 09:08:47

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 914
Lieu: Seahaven island

Calculons peeu, calculons bien

(Suite)
Peut toujours être utile, un lien vers les solutions les plus courtes pour les entiers jusqu'à 1024:
http://wwwold.iit.cnr.it/staff/giovanni.resta/ac/

 #21 - 21-06-2011 16:13:34

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2010
Lieu: Paris

Calcuulons peu, calculons bien

J'avais 19,23,43, mais effectivement 23 et 43 peuvent s'obtenir avec une multiplication de moins que ce que j'avais trouvé en premier lieu :

5^23=(5^3)*(5^3*5^2)^4
1 multiplication pour obtenir 5^2, 1 pour obtenir 5^3, 1 pour avoir 5^5, 2 pour obtenir 5^20, et 1 entre 5^20 et 5^3 déjà calculé, ce qui fait bien 6.

Du coup le premier à nécessiter 7 multiplications est 5^29.

5^43=(5^3)*(5^3*5^2)^8
qui de la même manière fait 7 multiplications.

5^44 : (5^4)*(5*5^4)^8 => 7
5^45 : (5^9)*(5*5^8)^4 => 7
5^46 : (5^23)^2 => 7
5^47 : au moins 8 nécessaires

Et la case réponse valide bien 19,29,47
(et non pas les nombres astronomiques que j'ai essayé de valider big_smile)

 #22 - 21-06-2011 18:40:26

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

cakculons peu, calculons bien

Je ne sais pas s'il y a mieux mais je dirais que le nombre de multiplications nécesssaires pour une puissance n est:
Si n est  écrit en binaire:
m(n)= (nb de chiffres) + (nb de 1)-1.
Exemple: 23=10111 a 5 chiffres et 4 as donc 5+4-1=8 multiplications.

 #23 - 22-06-2011 00:23:23

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1934

Calculons peu, calculons iben

Nodgim : remplace nécessaire par suffisant et je suis d'accord smile

 #24 - 23-06-2011 10:50:24

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1934

aClculons peu, calculons bien

Les bonnes réponses étaient donc 19, 29 et 47. Bravo à tous
La question est de savoir, partant de 1, combien d'additions sont nécessaires pour obtenir N en utilisant tous les résultats intermédiaires autant que souhaité.
Il s'agit d'un problème non résolu à ce jour dans le cas général, et pour lequel on n'a pas encore trouvé d'algorithme efficace.

On apprend ici tout de même que l'exponentiation rapide n'est pas la plus rapide possible smile
Comme certains l'ont fait remarqué, le nombre de multiplications nécessaires pour obtenir N via l'exponentiation rapide est égal au nombre de chiffres en binaire de N + son nombre de 1, moins 1.
Partant de là, il faut 6 opération pour calculer une puissance 15ème, alors que 5 suffisent : 1+1+1 = 3; 3+3=6; 6+6 = 12; 12+3 = 15
De même, il faudrait 7 opérations pour calculer une puissance 23ème alors que 6 suffisent: 1+1=2; 1+2=3; 3+2=5; 5+5=10; 10+10=20; 20+3=23
etc...

Clydevil a eu la gentillesse de nous faire partager un peu de documentation sur le sujet, je vous laisse regarder ça en détail.

 

Réponse rapide

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

Répondez à la devinette suivante : 

Le père de toto a trois fils : Riri, Fifi et ?

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