Enigme Exponentiation sommatoire @ Prise2Tete

nodgim · #1

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

ksavier · #2

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.

gwen27 · #3

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.

titoufred · #4

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

algao · #5

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

masab · #6

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à !

titoufred · #7

Ah ben non, c'est pas ça, je m'a trompé !

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

scarta · #8

Ca me rappelle ce petit problème de l'an passé
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

nodgim · #9

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.

titoufred · #10

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.

L00ping007 · #11

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

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

titoufred · #12

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.

Clydevil · #13

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

gwen27 · #14

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

godisdead · #15

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

scarta · #16

Code:

1+1        2
2+1        3
3+3        6
6+6        12
12+12        24
24+1        25
25+25        50
50+1        51
51+51        102
102+102        204
204+204        408
408+408        816
816+816        1632
1632+1632    3264
3264+25        3289

15 sommes

Code:

1+1        2
2+1        3
3+3        6
6+6        12
12+3        15
15+15        30
30+1        31
31+31        62
62+62        124
124+124        248
248+248        496
496+496        992
992+992        1984
1984+15        1999

14 sommes

Code:

1+1        2
2+1        3
3+3        6
6+6        12
12+12        24
24+1        25
25+25        50
50+50        100
100+25        125
125+3        128
128+128        256
256+256        512
512+512        1024
1024+1024    2048
2048+2048    4096
4096+4096    8192
8196+8192    16384
16384+125    16509

18 sommes

nodgim · #17

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.

L00ping007 · #18

J'ai 15 sommes pour 1999, est-ce le minimum ?

Et 19 sommes pour 16509

masab · #19

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

Franky1103 · #20

Bonjour nodgim,
Faut-il le moins d'additions possibles pour chacun des trois nombres ou pour l'ensemble de l'énigme ?
Bonne journée.

nodgim · #21

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 !

Clydevil · #22

@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"

scarta · #23

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

nodgim · #24

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.

titoufred · #25

Merci à toi. C'était vraiment très intéressant.

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 - 29-01-2012 18:39:21

Exponentiation smomatoire

#0 Pub

#2 - 29-01-2012 19:07:03

Exponentiattion sommatoire

#3 - 29-01-2012 19:30:48

exponentiation sommatiire

#4 - 29-01-2012 21:40:51

Exopnentiation sommatoire

#5 - 30-01-2012 07:15:07

Exponetiation sommatoire

#6 - 30-01-2012 09:33:59

exponentiatuon sommatoire

#7 - 30-01-2012 11:20:46

exponentiatoon sommatoire

#8 - 30-01-2012 11:24:45

Exponentiation sommatiore

#9 - 30-01-2012 18:27:54

Exponentiation soommatoire

#10 - 31-01-2012 00:26:29

Exponentition sommatoire

#11 - 31-01-2012 01:15:18

exponentuation sommatoire

#12 - 31-01-2012 02:12:26

Exponentiation sommatoie

#13 - 31-01-2012 09:20:51

Exponentiatino sommatoire

#14 - 31-01-2012 10:17:13

Exponentiation sommatire

#15 - 31-01-2012 10:17:42

Exponentiation sommatooire

#16 - 31-01-2012 16:12:58

Exponentation sommatoire

Code:

Code:

Code:

#17 - 31-01-2012 17:30:39

Exponentiation smmatoire

#18 - 31-01-2012 20:24:33

Exponentiation sommmatoire

#19 - 01-02-2012 12:11:05

Exponentiation somatoire

#20 - 01-02-2012 14:21:48

Exponentiation sommatoirre

#21 - 01-02-2012 17:31:12

exponentiation dommatoire

#22 - 01-02-2012 23:32:31

exponentiation sommatoore

#23 - 02-02-2012 08:42:36

exponentiation sommztoire

nodgim a écrit:

#24 - 02-02-2012 19:05:02

exponebtiation sommatoire

#25 - 02-02-2012 20:53:21

exponentiatoon sommatoire

Réponse rapide

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums