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: EASY
Tags: Fundamentals

Data structures
Skill types: Data structures

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 deck_size <= 2:
		return 1
	k = 1
	while 2 ** k % (deck_size - 1) != 1:
		k += 1
	return k