The magician's shuffle

Problem

At the town theater, Aurelio the magician always shuffles the same way, and he swears that if he repeats it just enough times the deck puts itself back in order. Nobody believes him. You are going to count.

The deck holds the cards 1 to n, in order. One shuffle splits it into two equal halves, the first and the second, and builds a new deck by taking one card from each half in turns: the first card of the first half, the first of the second, the second of the first, and so on. Write a function that takes n (an even whole number, 2 or more) and returns, as a whole number, how many shuffles it takes for the deck to read 1 to n again. The first shuffle already counts, so you never return 0.

With 6: [1, 2, 3] and [4, 5, 6] give [1, 4, 2, 5, 3, 6], then [1, 5, 4, 3, 2, 6], [1, 3, 5, 2, 4, 6] and [1, 2, 3, 4, 5, 6]. You return 4.

Examples

• The example

  6 → 4

• Four cards

  4 → 2

• Eight cards

  8 → 3

• A full deck

  52 → 8

Besides these, the challenge has hidden tests that are revealed when you submit your solution.

You start with this

def shuffles(n):
    pass

function shuffles(n) {
}