Enigme Calculons peu, calculons bien @ Prise2Tete

scarta · #1

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

fabb54 · #2

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

Clydevil · #3

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

scarta · #4

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

rivas · #5

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

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

Clydevil · #6

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

gwen27 · #7

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

Nicouj · #8

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

scarta · #9

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

gwen27 · #10

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

Clydevil · #11

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

Nicouj · #12

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

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

L00ping007 · #13

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
J'ai soit mal compris l'énoncé, soit je me suis plantouillé dans mes multiplications !

scarta · #14

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)

MthS-MlndN · #15

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

gwen27 · #16

19 35 67 ?

scarta · #17

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

gwen27 · #18

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

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

rivas · #19

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:

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

Clydevil · #20

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

L00ping007 · #21

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 )

nodgim · #22

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.

scarta · #23

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

scarta · #24

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

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

calculons peu, calculons bieb

#0 Pub

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

Calculons peu, calclons bien

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

Calculons peu, clculons bien

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

calculons peu, calculpns bien

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

Calculoons peu, calculons bien

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

Calculons peu, calculons bein

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

cakculons peu, calculons bien

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

Calculons peu ,calculons bien

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

calcilons peu, calculons bien

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

calculons peu, calcukons bien

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

calculons peu, calculons bieb

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

Calculons peu, calculons bie

Code:

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

Calculons peu, calcuolns bien

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

calculons peu, calvulons bien

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

Calcuolns peu, calculons bien

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

Clculons peu, calculons bien

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

Calculons peu, caculons bien

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

Caculons peu, calculons bien

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

calculons peu, calculons bieb

Code:

Code:

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

Caculons peu, calculons bien

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

Calculons peu, calculnos bien

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

Calcullons peu, calculons bien

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

Calculons peu, ccalculons bien

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

Calculons peu, ccalculons bien

Réponse rapide

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums