Enigme A vous de payer

dhrm77 · #1

Comme cette énigme est apparement trop simple pour certains, je vous propose une petite complication:

2 mathematiciens (A et B) jouent au probleme suivant:
A choisit mentalement un nombre X dans l'ensembre {1,....,10000000000000000}.
B qui cherche à découvrir X, peut choisir un sous-ensemble E de {1,....,10000000000000000} et demander si X appartient à E ou non.
- Si la réponse de A est Oui, B doit payer 7 euros.
- Si la réponse de A est Non, B doit payer 3 euros.

Quel est la somme minimale nécessaire que B doit posséder au départ pour être assuré de trouver X ?
Et bien sur, quelles sont donc les étapes?

Edit:
Pour ceux qui n'ont pas les moyens d'aller jusqu'a 10^16, donnez la solution pour un ensemble de depart de 2277444446 nombres.

Pour les étapes, il suffit d'expliquer un peu et de donner quelques nombres clef, pour que je vois si vous avez la bonne réponse.

Franky1103 · #2

Bonjour,
Même si la proportion des coûts des Oui/Non est différente, on reste sur le principe d'une suite de Fibonacci. Son n-ième terme est donné par:
Fn = (phi^n - phi^(-n)) / V5 avec phi = (1+V5) / 2 = nombre d'or
J'inverse cette formule pour calculer n en fonction de Fn: je trouve:
n = ln [(V5 Fn + V(5Fn²+4)) / 2) / ln (phi)
Si Fn est "grand", alors 4 est "peanut" et n = ln (V5 Fn) / ln (phi)
Soit notre ensemble {1,...,10^m}; on aura :
n = ent [ln (V5) / ln (phi) + m ln (10) / ln (phi)]
ou encore n = ent (1,672 + 4,785 m)
Dans ton énigme, m = 16 et donc n = 78.
B devra donc avoir un budget de 7 x 78 / 2 + 3 = 276 €
Bonne soirée.
Frank

dhrm77 · #3

Franky, c'est pas loin, mais c'est pas ca...

Bamby2 · #4

j'avais directement codé un algorithme pour calculer pas a pas.
ca marchait bien pour le 1er, mais pour ce probleme la, ca passait plus.

puis j'ai remarqué un truc dans les chiffres que j'obtenais !

et j'ai réfléchis dessus.

a chaque étape, j'ai deux tas, l'un correspond a ce que je peux avoir avec n-7 pièce, et l'autre avec n-3 pièces.
et je demande a vérifier celui de S(n-7) éléments.
si j'ai bon, je me fait prélever 7 pièces, et je peux les traiter, car me reste n-7 pièce, parfait pour gérer S(n-7).
et réciproquement si je perds avec n-3.

Ma suite je l'ai écrite, de manière analogue: en notant le moment ou il fallait payer un de plus, par conséquent ma formule est un chouilla plus compliqué : Sn s’écrit S(n-3) + S(n-7) - 1
mais elle est strictement équivalente a celle que je décrit au début

en partant de la j'arrive a définir les 150 premiers termes, mais a un moment la suite coince
par exemple j'obtient qu'il faut 150 pièces pour 1965908963 : S(150) = 1965908963
(et donc 149 suffisent pour 1965908962)

par contre le chiffre si énorme(10^16), j'arrive rien a en faire, désolé

bon j'ai pas finalisté, mais il se fait tard déjà et je n'ai plus toute ma tête... bonne nuit !

EDIT : j'ai modifier un peu car je n’étais pas clair sur les 2 suites (celle que j'explique, et celle que j'avais calculer a la base. la 1ere étant plus simple, mais ne correspondant pas a celle que j'avais calculé initialement)

Nicouj · #5

Python me répond instantanément 254 :

Code:

def find_u_aux(n, size, u6, u5, u4, u3, u2, u1, u0):
    if u6 >= size:
        return n
    else:
        return find_u_aux(n+1, size, u4+u0, u6, u5, u4, u3, u2, u1)

def find_u(size):
    return find_u_aux(6, size, 1, 1, 1, 1, 1, 1, 1)

>>> find_u(10 ** 16)
254

Nicouj · #6

Dès fois qu'il y aurait une suite j'ai préparé une fonction générique ^^ :

Code:

def find_u(size, yes, no):
    u = [1] * max(yes, no)
    n = max(yes, no) -1
    while (u[n] < size):
        n = n + 1
        u.append(u[n - yes] + u[n - no])
    return (n, u)

scarta · #7

Pour 2277444446, c'est 168 (bruteforcé en une poignée de minutes)

Edit: et mal bruteforcé, en plus. Je trouve 151 maintenant...

dhrm77 · #8

Au départ je voulais faire 10^17, mais comme je m'étonnais que personne ne sois pres de la solution, je me suis apercu que j'avais mal compté mes chiffres...

Donc, bonne réponse (longue) de Nicouj pour l'instant.
Du coup, Franky est plus loin que je ne pensais...
Scarta, réponse (courte) presque juste...

scarta · #9

J'ai modifié mon algo pour optimiser, c'est quasi instantané
pour 2277444447: 150
pour 10^17: 270
pour 10^18: 286

Plus précisément:
A partir de 2: 7
A partir de 3: 10
A partir de 4: 13
A partir de 5: 14
A partir de 6: 16
A partir de 7: 17
A partir de 9: 19
A partir de 10: 20
A partir de 13: 21
A partir de 14: 22
A partir de 15: 23
A partir de 19: 24
A partir de 22: 25
A partir de 23: 26
A partir de 28: 27
A partir de 34: 28
A partir de 36: 29
A partir de 42: 30
A partir de 52: 31
A partir de 57: 32
A partir de 64: 33
A partir de 79: 34
A partir de 90: 35
A partir de 99: 36
A partir de 120: 37
A partir de 141: 38
A partir de 155: 39
A partir de 183: 40
A partir de 219: 41
A partir de 244: 42
A partir de 281: 43
A partir de 338: 44
A partir de 384: 45
A partir de 435: 46
A partir de 520: 47
A partir de 602: 48
A partir de 678: 49
A partir de 800: 50
A partir de 939: 51
A partir de 1061: 52
A partir de 1234: 53
A partir de 1458: 54
A partir de 1662: 55
A partir de 1911: 56
A partir de 2257: 57
A partir de 2600: 58
A partir de 2971: 59
A partir de 3490: 60
A partir de 4057: 61
A partir de 4632: 62
A partir de 5400: 63
A partir de 6313: 64
A partir de 7231: 65
A partir de 8370: 66
A partir de 9802: 67
A partir de 11287: 68
A partir de 13001: 69
A partir de 15201: 70
A partir de 17599: 71
A partir de 20231: 72
A partir de 23570: 73
A partir de 27400: 74
A partir de 31517: 75
A partir de 36570: 76
A partir de 42600: 77
A partir de 49115: 78
A partir de 56800: 79
A partir de 66169: 80
A partir de 76514: 81
A partir de 88316: 82
A partir de 102738: 83
A partir de 119113: 84
A partir de 137430: 85
A partir de 159537: 86
A partir de 185281: 87
A partir de 213943: 88
A partir de 247852: 89
A partir de 288018: 90
A partir de 333055: 91
A partir de 385281: 92
A partir de 447554: 93
A partir de 518335: 94
A partir de 599223: 95
A partir de 695405: 96
A partir de 806352: 97
A partir de 932277: 98
A partir de 1080685: 99
A partir de 1253905: 100
A partir de 1450611: 101
A partir de 1679907: 102
A partir de 1949309: 103
A partir de 2256962: 104
A partir de 2612183: 105
A partir de 3029993: 106
A partir de 3510866: 107
A partir de 4062793: 108
A partir de 4709899: 109
A partir de 5460174: 110
A partir de 6319754: 111
A partir de 7322081: 112
A partir de 8490166: 113
A partir de 9830619: 114
A partir de 11384873: 115
A partir de 13200064: 116
A partir de 15290792: 117
A partir de 17704626: 118
A partir de 20522144: 119
A partir de 23780957: 120
A partir de 27535244: 121
A partir de 31907016: 122
A partir de 36981020: 123
A partir de 42826035: 124
A partir de 49611641: 125
A partir de 57503163: 126
A partir de 66606991: 127
A partir de 77146884: 128
A partir de 89410178: 129
A partir de 103588010: 130
A partir de 119972918: 131
A partir de 139021818: 132
A partir de 161091172: 133
A partir de 186579908: 134
A partir de 216168701: 135
A partir de 250501349: 136
A partir de 290167917: 137
A partir de 336141618: 138
A partir de 389523166: 139
A partir de 451259088: 140
A partir de 522721525: 141
A partir de 605691866: 142
A partir de 701760436: 143
A partir de 812889441: 144
A partir de 941833483: 145
A partir de 1091283601: 146
A partir de 1264148528: 147
A partir de 1464555007: 148
A partir de 1696975466: 149
A partir de 1965908963: 150
A partir de 2277444447: 151
A partir de 2638808948: 152
A partir de 3057192563: 153
A partir de 3541592974: 154
A partir de 4103363954: 155
A partir de 4754168028: 156
A partir de 5507501936: 157
A partir de 6380808400: 158
A partir de 7392976975: 159
A partir de 8564694498: 160
A partir de 9922401373: 161
A partir de 11496340928: 162
A partir de 13318862525: 163
A partir de 15429903308: 164
A partir de 17877149327: 165
A partir de 20711839499: 166
A partir de 23994597805: 167
A partir de 27799550699: 168
A partir de 32208180426: 169
A partir de 37313460329: 170
A partir de 43229454006: 171
A partir de 50085329752: 172
A partir de 58025299827: 173
A partir de 67224051810: 174
A partir de 77884880450: 175
A partir de 90233480252: 176
A partir de 104537512138: 177
A partir de 121114334455: 178
A partir de 140318810003: 179
A partir de 162562811964: 180
A partir de 188338386264: 181
A partir de 218203690452: 182
A partir de 252796292215: 183
A partir de 292875898401: 184
A partir de 339318024906: 185
A partir de 393115102217: 186
A partir de 455438710364: 187
A partir de 527656411169: 188
A partir de 611318792668: 189
A partir de 708235002578: 190
A partir de 820532309569: 191
A partir de 950636817573: 192
A partir de 1101350104794: 193
A partir de 1275971019932: 194
A partir de 1478293228741: 195
A partir de 1712668897461: 196
A partir de 1984206022509: 197
A partir de 2298825538309: 198
A partir de 2663305715033: 199
A partir de 3085556127302: 200
A partir de 3574796558240: 201
A partir de 4141598943773: 202
A partir de 4798225024762: 203
A partir de 5559002580748: 204
A partir de 6440424482081: 205
A partir de 7461530739794: 206
A partir de 8644558708049: 207
A partir de 10015221040320: 208
A partir de 11603129683566: 209
A partir de 13442783732810: 210
A partir de 15574223621067: 211
A partir de 18043554165646: 212
A partir de 20904314472603: 213
A partir de 24218782329115: 214
A partir de 28058775205965: 215
A partir de 32507444156168: 216
A partir de 37661566061924: 217
A partir de 43632998827031: 218
A partir de 50550998321813: 219
A partir de 58565880534526: 220
A partir de 67851781156145: 221
A partir de 78609773527777: 222
A partir de 91073324690693: 223
A partir de 105513347218068: 224
A partir de 122242772354807: 225
A partir de 141624323012505: 226
A partir de 164079227752593: 227
A partir de 190094553510951: 228
A partir de 220234096540281: 229
A partir de 255152552443285: 230
A partir de 295607900729018: 231
A partir de 342476868895087: 232
A partir de 396776875455789: 233
A partir de 459687128481610: 234
A partir de 532571422406037: 235
A partir de 617010971996069: 236
A partir de 714839680924894: 237
A partir de 828179323135054: 238
A partir de 959487840891155: 239
A partir de 1111616556380682: 240
A partir de 1287866451616663: 241
A partir de 1492059263297191: 242
A partir de 1728627528376750: 243
A partir de 2002706132541556: 244
A partir de 2320238586432244: 245
A partir de 2688115369267904: 246
A partir de 3114322688922237: 247
A partir de 3608105038048906: 248
A partir de 4180174632565094: 249
A partir de 4842950217298986: 250
A partir de 5610811170590461: 251
A partir de 6500413218997337: 252
A partir de 7531065586566889: 253
A partir de 8725133859512697: 254
A partir de 10108518257046242: 255
A partir de 11711240219131982: 256
A partir de 13568084076811682: 257
A partir de 15719329427636702: 258
A partir de 18211653438129318: 259
A partir de 21099149663378570: 260
A partir de 24444463287149398: 261
A partir de 28320171695175559: 262
A partir de 32810389882510551: 263
A partir de 38012547363961079: 264
A partir de 44039501122812260: 265
A partir de 51022043320639868: 266
A partir de 59111697027339648: 267
A partir de 68483964409961657: 268
A partir de 79342215015815426: 269
A partir de 91922086909850198: 270
A partir de 106496511773922735: 271
A partir de 123381716138627685: 272
A partir de 142944130230490065: 273
A partir de 165608208801262382: 274
A partir de 191865680548589341: 275
A partir de 222286345246305490: 276
A partir de 257530295711112579: 277
A partir de 298362192322512075: 278
A partir de 345668061384933174: 279
A partir de 400474425941602643: 280
A partir de 463970401123774456: 281
A partir de 537533741933522514: 282
A partir de 622760771187908132: 283
A partir de 721500696834887034: 284
A partir de 835895934256034588: 285
A partir de 968428832572841305: 286

scarta · #10

Voici, non pas le programme lui-même, mais les détails de l'algorithme utilisé.

Pour réaliser un programme qui va trouver les solutions, l'idée est simple:
- on construit une fonction F:N->N qui à un entier N représentant le cardinal d'un ensemble fait correspondre une valeur M qui est la somme minimale nécéssaire pour trouver un nombre dans cet ensemble
- cette fonction est construite valeur par valeur. La première valeur est bien entendu F(1) = 0; car pour un nombre unique, il ne faut poser aucune question pour le trouver
- pour un nombre N quelconque, et en supposant que toutes les valeurs de F inférieures à N ont déjà été calculées, on calcule le F(N) comme étant le minimum de l'expression MAX(F(A)+7, F(N-A)+3); A étant un entier compris entre 1 et N-1

Cependant, deux problèmes se posent: la gestion de la mémoire et le temps de calcul.

Gestion de la mémoire
Pour représenter cette fonction F, la manière la plus naturelle serait d'utiliser un tableau, noté valeurs[]. on aurait alors valeurs[N] = F(N+1) (les indices d'unt tableau de taille T sont compris entre 0 et T-1)
Le problème, c'est que 10^16 c'est beaucoup. Un tableau d'entiers (32 bits) à 10^16 entrées ferait une taille d'environ 37252903 Go (ça fait beaucoup de RAM)
On peut cependant contourner ce problème facilement: en effet, on remarque que les valeurs changent assez peu souvent.
Du coup, on utilise 2 tableaux notés clefs[] et valeurs[]. i étant un entier, on note Clefs(i) le plus petit entier pour lequel il faudrait au minimum Valeurs(i) euros.
Autrement dit, F(Clefs(i)) = Valeurs(i).
Avec cette implémentation, on peut calculer F(N) de la manière suivante:

fonction F(entier N) renvoyant un entier:
boucle pour i allant du dernier indice de Clefs jusqu'à 0 en décroissant
si Clefs(i) <= N; renvoyer Valeurs(i)
fin de la boucle
renvoyer 0 (au cas où)
fin de fonction

Explications: Tous les nombres compris entre Clefs(i) (inclu) et Clefs[i+1] (exclu) ont pour image par F Valeurs(i); on par donc de la dernière clef et on remonte jusqu'à la première clef inférieure à N (la clef suivante est donc nécessairement supérieure à N); et on renvoie la valeur associée.

Gestion du temps de calcul
Pour calculer F de cette manière, supposons qu'un millionième de seconde suffise pour trouver une valeur de N, il nous faudrait l'équivalent de 317 années de calcul.
De plus, plus N est grand, plus le minimum est à calculer sur un nombre important de valeurs (et donc plus le temps nécessaire pour trouver F(N) est grand aussi).
Voyons quelles optimisations on peut apporter au système.
On remarque tout d'abord que F est croissante (résultat trivial étant donné que s'il faut X euros pour un ensemble de cardinal N, il faut aussi au moins X euros pour un ensemble de cardinal plus grand que N).

Optimisation n°1
Lorsqu'on calcule le minimum; on calcule en général toutes les valeurs une par une et on stocke la plus petite qu'on ait vu.
Dans notre cas, si une de ces valeurs vaut F(N-1) alors inutile d'aller plus loin. En effet, on ne peut pas trouver moins car F est croissante.

Optimisation n°2
Au lieu de faire croître A entre 1 et N-1 on va le faire décroître de N. Ca ne change pas grand chose en théorie...
Sauf que pour plusieurs (beaucoup) valeurs consécutives de A, on a un F(A) constant (cf. la gestion de mémoire)
Du coup, si j'ai déjà calculé la valeur MAX(F(A+1)+3, F(N-A-1)+7) et que F(A) = F(A+1) il est inutile de calculer MAX(F(A)+3, F(N-A)+7)
En effet, F est croissante donc F(N-A-1) <= F(N-A); du coup le MAX calculé en A sera soit égal, soit supérieur à celui calculé en A+1. Comme on cherche le plus petit des maximums, inutile de calculer ceux dont on sait à l'avance qu'ils seront plus grands. Comme on stocke dans Clefs[] les valeurs de N où F(N) change, il suffit de prendre les valeurs Clefs(i)-1, qui est la plus grande valeur telle à image par F constante.
Autrement dit, on ne va pas calculer notre minimum sur toutes les valeurs de A, uniquement sur celles telles que F(A) < F(A+1), c'est à dire les plus grandes valeurs pour une même image.

Seulement voilà, ces deux optimisations sont bien jolies mais elles ne font qu'accélerer le calcul de F(N): on est toujours obligé de faire le calcul 10^16 fois pour l'instant.
Il faudrait donner un coup de boost au calcul, et déterminer que F(N+1) = F(N) en avance de phase quand c'est possible.
Pour celà, on va s'inspirer de l'optimisation 2

Optimisation n°3
Quand j'ai fini de calculer F(N), j'ai trouvé un A tel que:
- MAX(F(A)+3;F(N-A)+7) est minimal
- F(A) < F(A+1), cf. l'optimisation n°2
Pour N+1, on est en droit de se demander si la même valeur de A donnerait directement le même résultat. Et la réponse est: pas toujours ^^
Ceci dit, si jamais F(N+1-A) = F(N-A), alors la réponse est oui. En effet, on a alors MAX(F(A)+3; F(N-A)+7) = MAX(F(A)+3; F(N+1-A)+7). Comme le premier est minimal dans le cas N; le second aussi dans le cas N+1 (F est croissante, on ne pourra pas trouver moins).
Du coup, une fois que j'ai calculé F(N) pour un minimum obtenu avec une valeur A, je peux passer toutes les valeurs de N jusqu'à N' tel que f(N'-A) > f(N-A).
On va donc chercher la première clef K supérieure à N-A et reprendre à N=K+A. On saute ainsi de nombreuses valeurs de N pour lesquelles F(N) est constante.
Attention, ça ne signifie pas que la valeur calculée suivante sera différente, elle pourra être identique pour une autre valeur de A. Quoi qu'il en soit, même après avoir calculé cette nouvelle image de F on réappliquera cette optimisation.

Avec ces trois modifications, le programme calcule toutes les valeurs où l'image par F change, sur tous les entiers de 64 bits (inférieurs à 2^64 = 1,8E19) en moins d'une seconde.

dhrm77 · #11

Scarta, cette fois-ci c'est bon.

nicolas647 · #12

Appelons de nouveau f la fonction qui associe le nombre d'éléments de l'ensemble à la somme minimale nécessaire. Par itérations successives, on obtient :
f(1)=0
f(2)=7
f(3)=10
f(4)=13
f(5)=14
f(6)=16
f(7)=17
f(8)=17
f(9)=19
f(10)=20
f(11)=20
f(12)=20
f(13)=21
f(14)=22
f(15)=23
f(16)=23
f(17)=23
f(18)=23
f(19)=24
f(20)=24
f(21)=24
f(22)=25
f(23)=26

De la même manière que pour les énigmes précédentes, si on appelle a(n) la fonction réciproque de f qui prend toujours le plus grand antécédent, on sait que a(n)=a(n-7)+a(n-3), à condition bien sûr que les valeurs soient définies.

On n'a plus qu'à générer cette suite en prenant :
a(19)=9
a(20)=12
a(21)=13
a(22)=14
a(23)=18
a(24)=21
a(25)=22

On obtient :
a(253)=8,72513E+15
a(254)=1,01085E+16

La réponse est donc 254

dhrm77 · #13

Bonne réponse de Nicolas

dhrm77 · #14

Comme dit plus haut, bravo a ceux qui ont trouvé les solutions:
Voici les couts et maximum N pour chaque nombre de la serie.
0: 0 1
1: 0 1
2: 0 1
3: 0 1
4: 0 1
5: 0 1
6: 0 1
7: 7 2
8: 7 2
9: 7 2
10: 10 3
11: 10 3
12: 10 3
13: 13 4
14: 14 5
15: 14 5
16: 16 6
17: 17 8
18: 17 8
19: 19 9
20: 20 12
21: 21 13
22: 22 14
23: 23 18
24: 24 21
25: 25 22
26: 26 27
27: 27 33
28: 28 35
29: 29 41
30: 30 51
31: 31 56
32: 32 63
33: 33 78
34: 34 89
35: 35 98
36: 36 119
37: 37 140
38: 38 154
39: 39 182
40: 40 218
41: 41 243
42: 42 280
43: 43 337
44: 44 383
45: 45 434
46: 46 519
47: 47 601
48: 48 677
49: 49 799
50: 50 938
51: 51 1060
52: 52 1233
53: 53 1457
54: 54 1661
55: 55 1910
56: 56 2256
57: 57 2599
58: 58 2970
59: 59 3489
60: 60 4056
61: 61 4631
62: 62 5399
63: 63 6312
64: 64 7230
65: 65 8369
66: 66 9801
67: 67 11286
68: 68 13000
69: 69 15200
70: 70 17598
71: 71 20230
72: 72 23569
73: 73 27399
74: 74 31516
75: 75 36569
76: 76 42599
77: 77 49114
78: 78 56799
79: 79 66168
80: 80 76513
81: 81 88315
82: 82 102737
83: 83 119112
84: 84 137429
85: 85 159536
86: 86 185280
87: 87 213942
88: 88 247851
89: 89 288017
90: 90 333054
91: 91 385280
92: 92 447553
93: 93 518334
94: 94 599222
95: 95 695404
96: 96 806351
97: 97 932276
98: 98 1080684
99: 99 1253904
100: 100 1450610
101: 101 1679906
102: 102 1949308
103: 103 2256961
104: 104 2612182
105: 105 3029992
106: 106 3510865
107: 107 4062792
108: 108 4709898
109: 109 5460173
110: 110 6319753
111: 111 7322080
112: 112 8490165
113: 113 9830618
114: 114 11384872
115: 115 13200063
116: 116 15290791
117: 117 17704625
118: 118 20522143
119: 119 23780956
120: 120 27535243
121: 121 31907015
122: 122 36981019
123: 123 42826034
124: 124 49611640
125: 125 57503162
126: 126 66606990
127: 127 77146883
128: 128 89410177
129: 129 103588009
130: 130 119972917
131: 131 139021817
132: 132 161091171
133: 133 186579907
134: 134 216168700
135: 135 250501348
136: 136 290167916
137: 137 336141617
138: 138 389523165
139: 139 451259087
140: 140 522721524
141: 141 605691865
142: 142 701760435
143: 143 812889440
144: 144 941833482
145: 145 1091283600
146: 146 1264148527
147: 147 1464555006
148: 148 1696975465
149: 149 1965908962
150: 150 2277444446
151: 151 2638808947
152: 152 3057192562
153: 153 3541592973
154: 154 4103363953
155: 155 4754168027
156: 156 5507501935
157: 157 6380808399
158: 158 7392976974
159: 159 8564694497
160: 160 9922401372
161: 161 11496340927
162: 162 13318862524
163: 163 15429903307
164: 164 17877149326
165: 165 20711839498
166: 166 23994597804
167: 167 27799550698
168: 168 32208180425
169: 169 37313460328
170: 170 43229454005
171: 171 50085329751
172: 172 58025299826
173: 173 67224051809
174: 174 77884880449
175: 175 90233480251
176: 176 104537512137
177: 177 121114334454
178: 178 140318810002
179: 179 162562811963
180: 180 188338386263
181: 181 218203690451
182: 182 252796292214
183: 183 292875898400
184: 184 339318024905
185: 185 393115102216
186: 186 455438710363
187: 187 527656411168
188: 188 611318792667
189: 189 708235002577
190: 190 820532309568
191: 191 950636817572
192: 192 1101350104793
193: 193 1275971019931
194: 194 1478293228740
195: 195 1712668897460
196: 196 1984206022508
197: 197 2298825538308
198: 198 2663305715032
199: 199 3085556127301
200: 200 3574796558239
201: 201 4141598943772
202: 202 4798225024761
203: 203 5559002580747
204: 204 6440424482080
205: 205 7461530739793
206: 206 8644558708048
207: 207 10015221040319
208: 208 11603129683565
209: 209 13442783732809
210: 210 15574223621066
211: 211 18043554165645
212: 212 20904314472602
213: 213 24218782329114
214: 214 28058775205964
215: 215 32507444156167
216: 216 37661566061923
217: 217 43632998827030
218: 218 50550998321812
219: 219 58565880534525
220: 220 67851781156144
221: 221 78609773527776
222: 222 91073324690692
223: 223 105513347218067
224: 224 122242772354806
225: 225 141624323012504
226: 226 164079227752592
227: 227 190094553510950
228: 228 220234096540280
229: 229 255152552443284
230: 230 295607900729017
231: 231 342476868895086
232: 232 396776875455788
233: 233 459687128481609
234: 234 532571422406036
235: 235 617010971996068
236: 236 714839680924893
237: 237 828179323135053
238: 238 959487840891154
239: 239 1111616556380681
240: 240 1287866451616662
241: 241 1492059263297190
242: 242 1728627528376749
243: 243 2002706132541555
244: 244 2320238586432243
245: 245 2688115369267903
246: 246 3114322688922236
247: 247 3608105038048905
248: 248 4180174632565093
249: 249 4842950217298985
250: 250 5610811170590460
251: 251 6500413218997336
252: 252 7531065586566888
253: 253 8725133859512696
254: 254 10108518257046241
255: 255 11711240219131981
256: 256 13568084076811681
257: 257 15719329427636701
258: 258 18211653438129317
259: 259 21099149663378569
260: 260 24444463287149397
261: 261 28320171695175558
262: 262 32810389882510550
263: 263 38012547363961078
264: 264 44039501122812259
265: 265 51022043320639867
266: 266 59111697027339647
267: 267 68483964409961656
268: 268 79342215015815425
269: 269 91922086909850197
270: 270 106496511773922734
271: 271 123381716138627684
272: 272 142944130230490064
273: 273 165608208801262381
274: 274 191865680548589340
275: 275 222286345246305489
276: 276 257530295711112578
277: 277 298362192322512074
278: 278 345668061384933173
279: 279 400474425941602642
280: 280 463970401123774455
281: 281 537533741933522513
282: 282 622760771187908131
283: 283 721500696834887033
284: 284 835895934256034587
285: 285 968428832572841304
286: 286 1121975122776489675
287: 287 1299866335379809042
288: 288 1505962574506363817
289: 289 1744735893964397806
290: 290 2021367032214696075
291: 291 2341858508762398404
292: 292 2713164726537239110
293: 293 3143342154991185750
294: 294 3641724844142207446
295: 295 4219127301043602927
296: 296 4888078048955583556
297: 297 5663091876356903521
298: 298 6560985809806001331
299: 299 7601242775492822666

Ainsi j'ai marqué en gras les cas mentionnés plus haut.

Chaque nombre de la serie s'obtient simplement en faisant pour tout x>7 N(x) = N(X-7)+N(x-3), et pour tout x<=7 N(x)=1.

scarta · #15

Ah ben oui, vu comme ça, c'est encore plus rapide

Franky1103 · #16

Bonjour,
Mon raisonnement à partir de la suite de Fibonacci est complètement faux et il n'est donc pas étonnant que mon résultat soit faux aussi
Bravo à tous ceux qui ont trouvé et bonne journée.
Frank

Bamby2 · #17

arf j'avais bon, mais comme j'ai codé ca vite fait sans trop refléchir en c, je me suis heurté a la taille des int

bref, j'aurai du passé sur Excel.... je viens de le faire et ca m'a pris 10sec, et ca marche bien mieux

merci pour l'enigme

dhrm77 · #18

Je l'ai fait sur Linux (ubuntu) avec le compilateur C qui vient avec, et j'utilise des long long. (64 bits).
Ceci dit, il ne s'agit que de faire des additions, si on veut vraiment, et elles sont faisable assez facilement autrement, comme en BCD sur des arrays of characters ou simplement en ASCII sur des chaines de caracteres,..

En fait, c'est une variation de la serie de Fibonacci, comme le dit franky plus haut,
au lieu de faire N(x) = N(x-2)+N(x-1) pour fibonacci
on fait: N(x) = N(x-7)+N(x-3)

Bamby2 · #19

a ben, chez moi, que ce soit en int, long ou long long, a l'affichage, ca plante apres le calcul 150:

148 1464555007
149 1696975466
150 1965908963
151 -2017522849
152 -1656158348

étrange d’ailleurs que ca plante pareil quelque soit le typage .... j'y réfléchirai après une nuit de sommeil

dhrm77 · #20

Es-tu sur d'utiliser le bon type dans la chaine du printf ?
signed int : %i
unsigned int: %u
signed long : %li
unsigned long: %lu
signed long long : %lli
unsigned long long: %llu

Cependant si ton compilateur ne supporte pas "long long" il va simplement ignorer le 2eme "long". comme si tu mettais : signed signed int (un 2eme 'signed" ne rend pas la variable plus signée)

verifie avec ce simple petit programme:

long long a;
void main(){ printf("%u\n", sizeof(a)); }
si il supporte long long en tant que 64 bit, tu devrais voir '8' s'afficher.

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 - 02-11-2011 18:08:38

a cous de payer - suite (3/7)

#0 Pub

#2 - 02-11-2011 21:15:17

A vous d payer - suite (3/7)

#3 - 02-11-2011 22:20:45

A vous de payer - suite (3/7))

#4 - 03-11-2011 00:14:31

a vous dz payer - suite (3/7)

#5 - 03-11-2011 09:14:03

A ovus de payer - suite (3/7)

Code:

#6 - 03-11-2011 09:46:59

A vous de payer - suite (33/7)

Code:

#7 - 03-11-2011 14:25:02

a vous de payer - suitr (3/7)

#8 - 04-11-2011 01:13:27

a vpus de payer - suite (3/7)

#9 - 04-11-2011 09:08:20

A vvous de payer - suite (3/7)

#10 - 04-11-2011 11:05:10

A vous de payer - suuite (3/7)

#11 - 04-11-2011 11:06:01

A vous de payer - suite (3/7

#12 - 04-11-2011 15:09:23

a voud de payer - suite (3/7)

#13 - 05-11-2011 00:59:20

a vous de payer - suute (3/7)

#14 - 07-11-2011 03:39:43

A vous de payer - suite ((3/7)

#15 - 07-11-2011 08:46:16

A voous de payer - suite (3/7)

#16 - 07-11-2011 14:45:31

a vous de pauer - suite (3/7)

#17 - 08-11-2011 00:20:26

A vous de payer - suite (3/)

#18 - 08-11-2011 02:04:13

a vous de pauer - suite (3/7)

#19 - 09-11-2011 23:37:04

a vous de payer - suiye (3/7)

#20 - 10-11-2011 03:33:19

A vous de payer - suite ((3/7)

Réponse rapide

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums