You have a deck of 52 cards - for convenience, number them 1 through 52. You cut the cards into two equal halves and shuffle them perfectly. That is, the cards were in the order
1,2,3,...,52
and now they are
1,27,2,28,...,26,52. Let's call this a perfect in-shuffle.

If you repeat this in-shuffling process, how many in-shuffles will it take for the deck to return to its initial ordering (taking for granted that the cards will eventually do so)?
________________________

How does the solution change if you have a deck of 64 cards, or 10, or in general, n cards? For odd integer values of n, in-shuffling will take 1,2,3,...,n to 1,(n+3)/2,2,(n+5)/2,...,n,(n+1)/2. For example, when n=5, the first in-shuffle yields 1,4,2,5,3.

(In reply to re(3): Making a sequence (spoilers on the numbers) by Richard)

Apparently (based on my understanding of what I read), for odd numbers of cards, the number of shuffles equals the "multiplicative order" of 2 (mod n) where n is the number of cards. For even numbers, use n = one less than the number of cards.

The "multiplicative order" is like a modular logarithm of 1: it is the power to which, in this case, 2 is to be raised, mod n, in order to get 1.  The following program evaluates this:

DEFINT A-Z
CLS
FOR size = 3 TO 641 STEP 2
  lg = 1: pw = 2
  DO
   lg = lg + 1: pw = (pw * 2) MOD size
  LOOP UNTIL pw MOD size = 1
  shCt = lg
  n = (size - 3) / 2
  col = n \ 40
  row = n MOD 40 + 1
  LOCATE row, 10 * col + 1
  PRINT USING "### ### |"; size; shCt;
NEXT

and it indeed goes faster than actually shuffling the array of "cards".  As only odd sizes are calculated (since the same answer serves for the even size one higher), the list of answers goes twice as high.  The numbers agree with the previous results:

 3   2 |  83  82 | 163 162 | 243 162 | 323  72 | 403  60 | 483  66 | 563 562
 5   4 |  85   8 | 165  20 | 245  84 | 325  60 | 405 108 | 485  48 | 565  28
 7   3 |  87  28 | 167  83 | 247  36 | 327  36 | 407 180 | 487 243 | 567  54
 9   6 |  89  11 | 169 156 | 249  82 | 329  69 | 409 204 | 489 162 | 569 284
11  10 |  91  12 | 171  18 | 251  50 | 331  30 | 411  68 | 491 490 | 571 114
13  12 |  93  10 | 173 172 | 253 110 | 333  36 | 413 174 | 493  56 | 573 190
15   4 |  95  36 | 175  60 | 255   8 | 335 132 | 415 164 | 495  60 | 575 220
17   8 |  97  48 | 177  58 | 257  16 | 337  21 | 417 138 | 497 105 | 577 144
19  18 |  99  30 | 179 178 | 259  36 | 339  28 | 419 418 | 499 166 | 579  96
21   6 | 101 100 | 181 180 | 261  84 | 341  10 | 421 420 | 501 166 | 581 246
23  11 | 103  51 | 183  60 | 263 131 | 343 147 | 423 138 | 503 251 | 583 260
25  20 | 105  12 | 185  36 | 265  52 | 345  44 | 425  40 | 505 100 | 585  12
27  18 | 107 106 | 187  40 | 267  22 | 347 346 | 427  60 | 507 156 | 587 586
29  28 | 109  36 | 189  18 | 269 268 | 349 348 | 429  60 | 509 508 | 589  90
31   5 | 111  36 | 191  95 | 271 135 | 351  36 | 431  43 | 511   9 | 591 196
33  10 | 113  28 | 193  96 | 273  12 | 353  88 | 433  72 | 513  18 | 593 148
35  12 | 115  44 | 195  12 | 275  20 | 355 140 | 435  28 | 515 204 | 595  24
37  36 | 117  12 | 197 196 | 277  92 | 357  24 | 437 198 | 517 230 | 597 198
39  12 | 119  24 | 199  99 | 279  30 | 359 179 | 439  73 | 519 172 | 599 299
41  20 | 121 110 | 201  66 | 281  70 | 361 342 | 441  42 | 521 260 | 601  25
43  14 | 123  20 | 203  84 | 283  94 | 363 110 | 443 442 | 523 522 | 603  66
45  12 | 125 100 | 205  20 | 285  36 | 365  36 | 445  44 | 525  60 | 605 220
47  23 | 127   7 | 207  66 | 287  60 | 367 183 | 447 148 | 527  40 | 607 303
49  21 | 129  14 | 209  90 | 289 136 | 369  60 | 449 224 | 529 253 | 609  84
51   8 | 131 130 | 211 210 | 291  48 | 371 156 | 451  20 | 531 174 | 611 276
53  52 | 133  18 | 213  70 | 293 292 | 373 372 | 453  30 | 533  60 | 613 612
55  20 | 135  36 | 215  28 | 295 116 | 375 100 | 455  12 | 535 212 | 615  20
57  18 | 137  68 | 217  15 | 297  90 | 377  84 | 457  76 | 537 178 | 617 154
59  58 | 139 138 | 219  18 | 299 132 | 379 378 | 459  72 | 539 210 | 619 618
61  60 | 141  46 | 221  24 | 301  42 | 381  14 | 461 460 | 541 540 | 621 198
63   6 | 143  60 | 223  37 | 303 100 | 383 191 | 463 231 | 543 180 | 623  33
65  12 | 145  28 | 225  60 | 305  60 | 385  60 | 465  20 | 545  36 | 625 500
67  66 | 147  42 | 227 226 | 307 102 | 387  42 | 467 466 | 547 546 | 627  90
69  22 | 149 148 | 229  76 | 309 102 | 389 388 | 469  66 | 549  60 | 629  72
71  35 | 151  15 | 231  30 | 311 155 | 391  88 | 471  52 | 551 252 | 631  45
73   9 | 153  24 | 233  29 | 313 156 | 393 130 | 473  70 | 553  39 | 633 210
75  20 | 155  20 | 235  92 | 315  12 | 395 156 | 475 180 | 555  36 | 635  28
77  30 | 157  52 | 237  78 | 317 316 | 397  44 | 477 156 | 557 556 | 637  84
79  39 | 159  52 | 239 119 | 319 140 | 399  18 | 479 239 | 559  84 | 639 210
81  54 | 161  33 | 241  24 | 321 106 | 401 200 | 481  36 | 561  40 | 641  64

Posted by Charlie on 2004-05-20 09:03:20