A faro shuffle of a deck of playing cards is a shuffle in which the deck is split exactly in half and then the cards in the two halves are perfectly interwoven, such that the original bottom card is still on the bottom and the original top card is still on top.

For example, faro shuffling the list
```python
['ace', 'two', 'three', 'four', 'five', 'six']
```
gives
```python
['ace', 'four', 'two', 'five', 'three', 'six' ]
```

If 8 perfect faro shuffles are performed on a deck of 52 playing cards, the deck is restored to its original order.

Write a function that inputs an integer n and returns an integer representing the number of faro shuffles it takes to restore a deck of n cards to its original order.

Assume n is an even number between 2 and 2000.

Difficulty: introductory

Starter code:

def faro_cycles(deck_size):
	

Solutions:
def faro_cycles(n):
    x, cnt = 2, 1
    while x != 1 and n > 3:
        cnt += 1
        x = x*2 % (n-1)
    return cnt

def faro_cycles(deck_size):
    arr, count = list(range(deck_size)), 0
    original_arr = arr
    while True:
        arr = arr[0:deck_size:2] + arr[1:deck_size:2]
        count += 1
        if original_arr == arr:
            break
    return count

def faro_cycles(size):
    deck = list(range(size))
    cur, count = deck[::2] + deck[1::2], 1
    while cur != deck:
        cur, count = cur[::2] + cur[1::2], count + 1
    return count


def faro_cycles(n):
  original = list(range(1,n+1))
  duplicate, c = original.copy(), 0
  while 1:
      first, bottom = duplicate[0], duplicate[-1]
      first_half = duplicate[1:n//2]
      second_half = duplicate[n//2:-1]
      duplicate = []
      for i,j in zip(first_half,second_half) : duplicate.extend([j,i])
      duplicate = [first]+duplicate+[bottom]
      c+=1
      if original==duplicate:return c

def faro_cycles(deck_size):
    if deck_size == 2: return 1
    pos, output = 2, 1
    while pos != 1:
        pos = pos * 2 % (deck_size - 1)
        output += 1
    return output

def faro_cycles(deck_size):
    pos=1
    for i in range(deck_size):
        pos = pos*2-(0 if pos<deck_size/2 else deck_size-1)
        if pos==1:
            return i+1

def faro(xs):
    m = len(xs) // 2
    return [x for xs in zip(xs[:m], xs[m:]) for x in xs]

def faro_cycles(deck_size):
    xs = original = list(range(deck_size))
    n = 0
    while True:
        n += 1
        xs = faro(xs)
        if xs == original:
            return n

def interv(list1, list2):
    out_list = []
    for el1, el2 in zip(list1, list2):
        out_list.append(el1)
        out_list.append(el2)
    return out_list    
    
def faro_cycles(deck_size):
    original = [x for x in range(deck_size)]
    new = interv(original[:deck_size//2], original[deck_size//2:])
    n = 1
    while original!=new:
        new = interv(new[:deck_size//2], new[deck_size//2:])
        n += 1

    return n

def faro_cycles(deck_size):
    return [None, 1, 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 28, 5, 10, 12, 36, 12, 20, 14, 12, 23, 21, 8, 52, 20, 18, 58, 60, 6, 12, 66, 22, 35, 9, 20, 30, 39, 54, 82, 8, 28, 11, 12, 10, 36, 48, 30, 100, 51, 12, 106, 36, 36, 28, 44, 12, 24, 110, 20, 100, 7, 14, 130, 18, 36, 68, 138, 46, 60, 28, 42, 148, 15, 24, 20, 52, 52, 33, 162, 20, 83, 156, 18, 172, 60, 58, 178, 180, 60, 36, 40, 18, 95, 96, 12, 196, 99, 66, 84, 20, 66, 90, 210, 70, 28, 15, 18, 24, 37, 60, 226, 76, 30, 29, 92, 78, 119, 24, 162, 84, 36, 82, 50, 110, 8, 16, 36, 84, 131, 52, 22, 268, 135, 12, 20, 92, 30, 70, 94, 36, 60, 136, 48, 292, 116, 90, 132, 42, 100, 60, 102, 102, 155, 156, 12, 316, 140, 106, 72, 60, 36, 69, 30, 36, 132, 21, 28, 10, 147, 44, 346, 348, 36, 88, 140, 24, 179, 342, 110, 36, 183, 60, 156, 372, 100, 84, 378, 14, 191, 60, 42, 388, 88, 130, 156, 44, 18, 200, 60, 108, 180, 204, 68, 174, 164, 138, 418, 420, 138, 40, 60, 60, 43, 72, 28, 198, 73, 42, 442, 44, 148, 224, 20, 30, 12, 76, 72, 460, 231, 20, 466, 66, 52, 70, 180, 156, 239, 36, 66, 48, 243, 162, 490, 56, 60, 105, 166, 166, 251, 100, 156, 508, 9, 18, 204, 230, 172, 260, 522, 60, 40, 253, 174, 60, 212, 178, 210, 540, 180, 36, 546, 60, 252, 39, 36, 556, 84, 40, 562, 28, 54, 284, 114, 190, 220, 144, 96, 246, 260, 12, 586, 90, 196, 148, 24, 198, 299, 25, 66, 220, 303, 84, 276, 612, 20, 154, 618, 198, 33, 500, 90, 72, 45, 210, 28, 84, 210, 64, 214, 28, 323, 290, 30, 652, 260, 18, 658, 660, 24, 36, 308, 74, 60, 48, 180, 676, 48, 226, 22, 68, 76, 156, 230, 30, 276, 40, 58, 700, 36, 92, 300, 708, 78, 55, 60, 238, 359, 51, 24, 140, 121, 486, 56, 244, 84, 330, 246, 36, 371, 148, 246, 318, 375, 50, 60, 756, 110, 380, 36, 24, 348, 384, 16, 772, 20, 36, 180, 70, 252, 52, 786, 262, 84, 60, 52, 796, 184, 66, 90, 132, 268, 404, 270, 270, 324, 126, 12, 820, 411, 20, 826, 828, 92, 168, 332, 90, 419, 812, 70, 156, 330, 94, 396, 852, 36, 428, 858, 60, 431, 172, 136, 390, 132, 48, 300, 876, 292, 55, 882, 116, 443, 21, 270, 414, 356, 132, 140, 104, 42, 180, 906, 300, 91, 410, 60, 390, 153, 102, 420, 180, 102, 464, 126, 310, 40, 117, 156, 940, 220, 36, 946, 36, 316, 68, 380, 140, 204, 155, 318, 96, 483, 72, 194, 138, 60, 488, 110, 36, 491, 196, 138, 154, 495, 30, 396, 332, 36, 60, 232, 132, 468, 504, 42, 92, 84, 84, 1018, 340, 10, 20, 156, 294, 515, 258, 132, 120, 519, 346, 444, 180, 348, 262, 350, 108, 420, 15, 88, 1060, 531, 140, 240, 356, 24, 252, 140, 358, 492, 253, 342, 60, 543, 330, 1090, 364, 36, 274, 156, 366, 29, 24, 180, 1108, 100, 156, 148, 1116, 372, 522, 1122, 300, 231, 564, 84, 510, 452, 378, 264, 162, 42, 76, 180, 382, 575, 288, 60, 132, 180, 126, 166, 116, 388, 249, 1170, 88, 460, 530, 390, 236, 156, 156, 1186, 140, 44, 298, 476, 18, 180, 300, 200, 24, 280, 60, 516, 1212, 324, 152, 572, 180, 611, 420, 204, 1228, 615, 204, 36, 1236, 174, 72, 140, 164, 28, 156, 138, 534, 100, 418, 1258, 48, 420, 220, 180, 414, 20, 198, 40, 1276, 639, 60, 1282, 16, 60, 161, 1290, 86, 36, 648, 72, 1300, 651, 84, 1306, 120, 198, 300, 524, 146, 659, 60, 126, 260, 221, 442, 1210, 70, 44, 285, 204, 444, 312, 268, 224, 630, 96, 20, 540, 638, 30, 680, 644, 12, 683, 1332, 76, 1372, 100, 216, 588, 1380, 460, 92, 18, 462, 636, 99, 60, 70, 233, 466, 660, 140, 66, 704, 328, 156, 188, 36, 70, 84, 237, 180, 1426, 84, 468, 179, 60, 478, 719, 130, 36, 136, 723, 66, 1450, 1452, 48, 115, 486, 486, 90, 292, 162, 84, 245, 490, 580, 210, 56, 370, 1482, 180, 743, 744, 210, 1492, 132, 166, 1498, 234, 498, 84, 340, 502, 755, 88, 100, 180, 105, 156, 1522, 60, 508, 690, 1530, 18, 204, 364, 54, 66, 771, 204, 24, 1548, 230, 194, 620, 516, 779, 111, 260, 156, 783, 522, 1570, 660, 60, 738, 526, 40, 791, 316, 506, 678, 252, 522, 140, 532, 60, 400, 228, 212, 803, 201, 534, 52, 72, 210, 1618, 1620, 540, 300, 542, 180, 87, 385, 36, 1636, 740, 546, 260, 276, 180, 48, 84, 252, 60, 92, 78, 30, 831, 36, 1666, 1668, 556, 357, 660, 84, 99, 820, 120, 84, 24, 562, 198, 1692, 28, 848, 566, 162, 780, 20, 284, 244, 812, 114, 588, 200, 570, 215, 574, 220, 260, 36, 144, 1732, 692, 96, 828, 1740, 246, 348, 1746, 260, 408, 146, 36, 150, 879, 586, 140, 88, 90, 420, 330, 588, 140, 74, 148, 204, 891, 24, 1786, 596, 198, 810, 716, 598, 48, 25, 50, 684, 276, 198, 362, 252, 220, 429, 424, 606, 911, 180, 84, 290, 305, 276, 732, 830, 612, 393, 144, 60, 923, 602, 154, 72, 156, 618, 780, 1860, 594, 372, 1866, 66, 935, 936, 500, 1876, 939, 90, 804, 84, 72, 472, 60, 90, 756, 135, 210, 1900, 860, 28, 1906, 902, 84, 239, 764, 630, 900, 56, 64, 60, 460, 214, 1930, 644, 84, 444, 276, 646, 924, 388, 290, 1948, 975, 30, 88, 306, 652, 468, 60, 260, 210, 890, 18, 1972, 780, 658, 1978, 282, 660, 44, 1986, 24, 180, 996, 36, 1996, 333][deck_size >> 1]

def faro_cycles(deck_size):
    """
        If the deck size is 2*n, then it'll take at least
        k shuffles to get back to the starting order, where k 
        is the smallest integer such that 2**k = 1 (mod 2*n - 1)
    """
    
    if deck_size <= 2: return 1
    
    k = 1
    while ((2**k % (deck_size - 1)) != 1): k += 1
    return k