![](/img/vague-bas-gauche.png) |
#1 - 29-01-2012 18:39:21
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Exponentiiation sommatoire
Bonsoir à tous, Derrière ce titre barbare se cache un problème très simple: il s'agit d'aboutir à un nombre donné en utilisant uniquement la somme et en partant de 1, les autres nombres créés au fur et à mesure de l'avancée sont bien sûr utilisables.
Exemple avec 13 1+1=2 (j'ai créé le 2 je peux m'en servir pour la ligne suivante) 1+2=3 3+3=6 6+6=12 12+1=13 Il a fallu 5 additions pour arriver à 13.
Pour les nombres suivants, choisis totalement au hasard, trouver la configuration qui vous donnera le moins d'additions possibles. 3289, 1999, 16509.
Bon amusement
#2 - 29-01-2012 19:07:03
- ksavier
- Professionnel de Prise2Tete
- Enigmes résolues : 49
- Messages : 166
Exponentiiation sommatoire
Salut,
Naïvement, je pense que qu'en 11 étapes on construit les nombres 8,16,64,128,1024,2048. En 5 étapes de plus, on construit 3289.
Bref, j'ai le nombre 3289 en 16 étapes.
#3 - 29-01-2012 19:30:48
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,937E+3
Exponenntiation sommatoire
1+1 = 2 2+2=4 4+4=8 8+8=16 16+16=32 32+32=64 64+64=128 256 512 1024 2048 et on conclut en base 2 , en additionnant les termes 2 à 2
2048+ 1024= 3072 3072+ 128= 3200 3200+64 = 3264 3264+16 = 3280 3280+8=3288 3288+1=3289
Donc : 2048+1024+128+64+16+8+1=3289
1024+128= 1152 64+16=80 8+1=9
2048+1152=3200 80+9=89
3200+89=3289 17 coups.
#4 - 29-01-2012 21:40:51
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
exponebtiation sommatoire
On écrit le nombre en binaire, puis on compte le nombre de chiffres et le nombre de 1 dans cette écriture. Le nombre minimum d'additions est alors égal à : nombre de chiffres + nombre de chiffres "1" - 2
Par exemple pour 13, qui s'écrit 1101 en binaire, il y a 4 chiffres dont 3 chiffres "1", donc cela fait 4+3-2=5 additions au minimum.
L'écriture binaire nous donne également la marche à suivre : 13=8+4+1. Le 8 s'obtient en doublant le 1 trois fois de suite (1+1=2, 2+2=4, 4+4=8) puis on ajoute le 4 (8+4=12) et enfin le 1 (12+1=13).
NB : ton titre m'a fait penser à l'exponentiation rapide et m'a donné la clé.
#5 - 30-01-2012 07:15:07
- algao
- Amateur de Prise2Tete
- Enigmes résolues : 48
- Messages : 7
- Lieu: Port-aux-Prunes
exponentiarion sommatoire
Bonjour, Le plus efficace me semble être d'arriver à chaque ligne au nombre le plus élevé possible inférieur ou égal au nombre cible. Cela implique d'utiliser uniquement les puissances de 2. Donc pour 3289 : 1+1=2 2+2=4 4+4=8 8+8=16 16+16=32 32+32=64 64+64=128 128+128=256 256+256=512 512+512=1024 1024+1024=2048 2048+1024=3072 3072+128=3200 3200+64=3264 3264+16=3280 3280+8=3288 3288+1=3289
Et idem pour les autres, mais j'ai la flemme de le faire ![cool](img/smilies/cool.png)
#6 - 30-01-2012 09:33:59
- masab
- Expert de Prise2Tete
- Enigmes résolues : 44
- Messages : 971
exponentiatiob sommatoire
Pour 3289 il suffit de faire 17 additions 1+1=2 2+2=4 4+4=8 8+8=16 16+16=32 32+32=64 64+64=128 128+128=256 256+256=512 512+512=1024 1024+1024=2048 2048+1024=3072 3072+128=3200 3200+64=3264 3264+16=3280 3280+8=3288 3288+1=3289
On peut obtenir le nombre minimal d'additions comme suit. On écrit n=3289 en base 2 n = 3289 = [1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1] On notre r le nombre de chiffres dans l'écriture binaire de n . On note k le nombre de 1 dans l'écriture binaire de n . Alors le nombre minimal d'additions pour obtenir n est donné par m=(r-1)+(k-1)=r+k-2
Pour n=3289, on a r=12, k=7 d'où m=r+k-2=17 .
n=1999=[1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1] r=11, k=9, d'où m=r+k-2=18
n=16509=[1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1] r=15, k=7, d'où m=r+k-2=20
Voilà !
#7 - 30-01-2012 11:20:46
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
Exponeentiation sommatoire
Ah ben non, c'est pas ça, je m'a trompé ! ![lol](img/smilies/lol.png)
Par exemple 15 = 1111 peut s'obtenir en 5 additions. 1+1=2, 2+1=3, 3+3=6, 6+6=12, 12+3=15. En binaire : 1+1=10, 10+1=11, 11+11=110, 110+110=1100, 1100+11=1111
On voit la récursivité du truc, pour le nombre de 1 qu'on obtient dans une somme, c'est au maximum, la somme des nombres de 1 des 2 nombres qu'on ajoute.
Bon alors je dirais un truc du genre (toujours avec l'écriture binaire) :
Si f(n) donne le nombre d'additions minimum pour atteindre n alors, dans les cas favorables, on aurait :
f(n) = nombre de chiffres de n' + f(nombre de chiffres "1" de n') - 1
où n' est n écrit en binaire. (évidemment nombre de chiffres de n' = E(log2(n)) +1)
Mais, bon, j'ai dit cas favorables, ça c'est quand les motifs de 1 se répètent comme dans 15=1111 ou 27=11011 ou 63=111111 (3 motifs de 2 ou 2 motifs de 3 peu importe), mais le problème avec des nombres du genre 29=11101 où les motifs de 1 ne se répètent pas , c'est qu'on va devoir aller chercher un motif de 3 puis un motif de 1 ce qui donne 7 additions et non 6 comme pour 27.
Je réfléchis quand j'ai le temps...
#8 - 30-01-2012 11:24:45
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1958
exponzntiation sommatoire
Ca me rappelle ce petit problème de l'an passé ![smile](img/smilies/smile.png) http://www.prise2tete.fr/forum/viewtopic.php?id=9139
Bon, comme c'est NP complet et que j'ai pas beaucoup de temps CPU dispo avec tout ce qui tourne en ce moment, on va dire que j'y répondrai une autre fois :p
#9 - 30-01-2012 18:27:54
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Exopnentiation sommatoire
Bon, pour l'instant j'ai eu les réponses classiques, et tout le monde à peu près s'est jeté sur l'évidence de la solution qui consiste à ajouter des puissances de 2. C'est bien, mais ...on peut faire mieux ! Pour 3289, je le fais en 15 additions seulement, et je ne pense pas qu'on puisse faire mieux. Vous allez vous rendre compte que pour 1999, l'écart entre la solution classique et une solution plus recherchée est conséquent. Titoufred est en cours de réflexion, il s'est bien aperçu qu'il y avait quelque chose à creuser....
Allez, courage, ce n'est pas fini, mais vous avez déja fait du chemin.
Pour Scarta: oui, c'est le même problème, et en plus j'y avais mis ma patte, j'avais oublié. Mais chut! que ça reste entre nous.
#10 - 31-01-2012 00:26:29
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
Exponentiaton sommatoire
1999 en 14 additions : 00000000001 (0) 00000000010 (1) = (0)*2 00000000011 (2) = (1)+(0) 00000001100 (4) = (2)*2^2 00000001111 (5) = (4)+(2) 00000011110 (6) = (5)*2 00000011111 (7) = (6)+(0) 11111000000 (13) = (7)*2^6 11111001111 (14) = (13)+(7)
3289 en 15 additions: 000000000001 (0) 000000000010 (1) = (0)*2 000000000011 (2) = (1)+(0) 000000011000 (5) = (2)*2^3 000011000000 (8) = (5)*2^3 110000000000 (12) = (8)*2^4 110011011001 (15) = (12)+(8)+(5)+(0)
16509 en 19 additions: 000000000000001 (0) 000000000000010 (1) = (0)*2 000000000000011 (2) = (1)+(0) 000000000001100 (4) = (2)*2^2 000000000110000 (6) = (4)*2^2 000000000111111 (8) = (6)+(4)+(2) 000000001111110 (9) = (8)*2 000000001111111 (10) = (9)+(0) 000000011111101 (11) = (9)+(10) 011111110000000 (18) = (10)*2^7 100000001111101 (19) = (18)+(11)
Sur les 2 premiers, ça se goupille bien, on arrive bien à faire le minimum (?), c'est-à-dire avec f(n) = #chiff(n') + f(#"1"(n')) - 1. Sur le dernier, f(16509)=18, mais ça se goupille mal, en tout cas, je n'ai pas trouvé mieux que 19 additions.
Je ne sais pas sur quels nombres on peut faire le minimum (?), par exemple qu'est-ce qui distingue 23 = 10111 qui nécessite 6 additions, de 29 = 11101 qui en nécessite 7.
#11 - 31-01-2012 01:15:18
- L00ping007
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 2010
- Lieu: Paris
Exponentiatino sommatoire
1+1=2 2+1=3 3+3=6 6+6=12 12+12=24 24+24=48 48+3=51 51+51=102 102+102=204 204+204=408 408+3=411 411+411=822 822+822=1644 1644+1644=3288 3288+1=3289 15 sommes ![smile](img/smilies/smile.png)
L'idée est de partir par la fin, et de faire l'opération suivante tant jusqu'à ce qu'on arrive à 1 : - on soustrait au nombre le reste de sa division eucludienne par 4. - on divise par 2, puis par 2 Évidemment il faut à un moment passer par 3 au début.
Avant d'appliquer cet algo aux autres nombres, je vais réfléchir si c'est améliorable avec 7 au lieu de 3 (voire 15, 31...)
#12 - 31-01-2012 02:12:26
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
Exponentiation smmatoire
16509 en 18 additions : 000000000000001 (0) 000000000000010 (1) = (0)*2 000000000000011 (2) = (1)+(0) 000000000000101 (3) = (2)+(1) 000000000001000 (4) = (3)+(2) 000001000000000 (10) = (4)*2^6 000001000000011 (11) = (10)+(2) 000100000001100 (13) = (11)*2^2 000100000001111 (14) = (13)+(2) 100000001111000 (17) = (10)*2^3 100000001111101 (18) = (17)+(3)
Je ne vois toujours pas de méthode générale.
#13 - 31-01-2012 09:20:51
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Exponentiation sommattoire
Salut, Moi je suis auditeur libre (je connaissais déjà), je vois que tu as écris:
...et je ne pense pas qu'on puisse faire mieux...
Donc soit c'est une formule de style dans la modestie, soit tu n'as pas la "solution", donc un petit lien fiable qui peut te les générer (juste avant "Conjectures") pour des nombres < 2^27 et te donner d'autres information sur le sujet:
http://wwwhomes.uni-bielefeld.de/achim/ … chain.html
#14 - 31-01-2012 10:17:13
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,937E+3
Exponentiation smmatoire
J'arrive effectivement à 3289 en 15 coups et à 1999 en 14
2 2 3 4 5 8 10 16 15 24 30 48 31 96 62 192 124 384 248 768 496 1536 992 3072 1984 3264 1999 3288 3289
#15 - 31-01-2012 10:17:42
- godisdead
- Expert de Prise2Tete
- Enigmes résolues : 22
- Messages : 747
Exponentiatiion sommatoire
1+1 = 2 2+1 = 3 6 12 24 48 96 192 386 768 1536 192 + 24 = 216 216 + 1 = 217 1536 + 217 = 1753 1753 + 1536 = 3289
Pour 1999, je n'arrive pas à mieux que 15 coups :
1 1 2 2 1 3 3 3 6 6 1 7 7 7 14 14 14 28 28 28 56 56 6 62 62 62 124 124 124 248 248 248 496 496 496 992 992 992 1984 1984 14 1998 1998 1 1999
#16 - 31-01-2012 16:12:58
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1958
exponentiation sommatoiee
15 sommes
14 sommes
18 sommes
#17 - 31-01-2012 17:30:39
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
exponentiation solmatoire
Titoufred a trouvé la meilleure solution pour les 3 nombres, je tiens à souligner la subtilité de sa solution pour le 16509.
Scarta et Gwen OK pour les 2 premiers nombres.
Godisdead est à (+1) de l'optimum pour le 2.
Clydevil fournit un site où ce problème est abordé, perso je ne connaissais pas.
#18 - 31-01-2012 20:24:33
- L00ping007
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 2010
- Lieu: Paris
Exponentiation ssommatoire
J'ai 15 sommes pour 1999, est-ce le minimum ?
Et 19 sommes pour 16509
#19 - 01-02-2012 12:11:05
- masab
- Expert de Prise2Tete
- Enigmes résolues : 44
- Messages : 971
exponentiation sommztoire
Voici de meilleures solutions... En binaire 3289 = [1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1] 3289 = 1 + 3*2^3 + 3*2^6 + 3*2^10
Le nombre 3289 s'obtient en 15 additions 1 : 1+1=2 2 : 2+1=3 3 : 3+3=6 4 : 6+6=12 5 : 12+12=24 6 : 24+24=48 7 : 48+48=96 8 : 96+96=192 9 : 192+192=384 10 : 384+384=768 11 : 768+768=1536 12 : 1536+1536=3072 13 : 3072+24=3096 14 : 3096+192=3288 15 : 3288+1=3289
En binaire 1999 = [1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1] 1999 = 15 + 31*2^6
Le nombre 1999 s'obtient en 14 additions 1 : 1+1=2 2 : 2+1=3 3 : 3+3=6 4 : 6+6=12 5 : 12+3 = 15 6 : 15+15 =30 7 : 30+1=31 8 : 31+31=62 9 : 62+62=124 10 : 124+124=248 11 : 248+248=496 12 : 496+496=992 13 : 992+992=1984 14 : 1984+15=1999
En binaire 16509 = [1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1] 16509=2^14+125=2^14+25+25*2^2
Le nombre 16509 s'obtient en 18 additions 1 : 1+1=2 2 : 2+1=3 3 : 3+3=6 4 : 6+6=12 5 : 12+12=24 6 : 24+1=25 7 : 25+25=50 8 : 50+50=100 9 : 100+25=125 10 : 125+3=128 11 : 128+128=256 12 : 256+256=512 13 : 512+512=1024 14 : 1024+1024=2048 15 : 2048+2048=4096 16 : 4096+4096=8192 17 : 8192+8192=16384 18 : 16384+125=16509
#20 - 01-02-2012 14:21:48
- Franky1103
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 3218
- Lieu: Luxembourg
Expponentiation sommatoire
Bonjour nodgim, Faut-il le moins d'additions possibles pour chacun des trois nombres ou pour l'ensemble de l'énigme ? Bonne journée.
#21 - 01-02-2012 17:31:12
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Exponentiation ssommatoire
Réponse à Francky: Pour l'ensemble de l'enigme, ça suppose de trouver une solution générale. Pour l'instant, j'ai pas... A Looping: tu es à +1 du min !
#22 - 01-02-2012 23:32:31
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
expinentiation sommatoire
@tout le monde: le problème général "shortest addition chain" n'est pas résolu à l'heure actuelle. Pour des nombres en particulier voir mon lien précédent ou évidemment googleliser "shortest addition chain"
#23 - 02-02-2012 08:42:36
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1958
Exponentiation somatoire
nodgim a écrit:Scarta et Gwen OK pour les 2 premiers nombres.
Je veux pas chipoter mais perso je ne vois pas de solution en moins de 18 coups pour 16509
#24 - 02-02-2012 19:05:02
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Exponentiatin sommatoire
Je me roule dans la poussière et implore Scarta de bien vouloir me pardonner de l'avoir omis parmi les personnes citées qui ont tout réussi.
Pour ceux qui n'ont pas encore forcément tout compris dans la méthode, lorsque le nombre est écrit en binaire, le but est bien de remplacer les 0 par des 1 avec le minimum d'opérations. Il y a 2 opérations élémentaires: le doublement du nombre, qui fait décaler le nombre écrit vers la gauche d'un rang, et l'addition de 2 nombres déja créés. Au vu des résultats, ceux qui sont intéressés peuvent maintenant se frotter à d'autres nombres.
Cette exponentiation de somme est utilisée lorsqu'on veut calculer des puissances élevées: pour calculer 2^1 000 000 000, on ne va pas faire 1 000 000 000 opérations, on va utiliser ce raccourci. Plus précisément, lorsqu'on veut savoir si un nombre p est probablement premier, on calcule 2^p modulo p, le théorème de Fermat dit que .... Les nombres probablement premiers de 200 chiffres dont on se sert pour le code RSA sont trouvés par cette méthode (allez donc en découvrir une autre...)
Merci aux participants.
#25 - 02-02-2012 20:53:21
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
exponentiation somlatoire
Merci à toi. C'était vraiment très intéressant.
Mots clés des moteurs de recherche
|
![](/img/vague-haut-droite.png) |