In chaos theory, the horseshoe map is an example of how chaos arises in a simple process of folding and squashing. It goes like this: take an imaginary piece of dough, fold it, and finally squash it to its original size. Chaos arises in the pattern of how the pieces of dough end up in the final arrangement after n iterations.
In our case, we'll take a look at how a simple binary pattern behaves when we fold and squash it. Here are the steps with an 8-bit example (the binary representation of 201 or
Cut the bits in two pieces of equal length (add a '0' at the beginning if there is an odd number of bits).
1100 | 1001
Fold the first half over the second half. Note that the order of the first half is reversed, as we rotate it while folding.
Squash to its original shape. While squashing, the upper bits are shifted left to the bits under their original position.
If we repeat this for this example, we can see that after 4 iterations, we are back to the original bitstring:
Start bits: 11001001 Iteration 1: 01001011 Iteration 2: 01001101 Iteration 3: 01011001 Iteration 4: 11001001
So, for the decimal value of 201, the number of cycles is 4.
- Write a full program that takes a decimal number as input and outputs the number of cycles it takes to repeat in the above described binary squash-and-fold process.
- The (decimal) input must be taken from stdin (range: from 1 up to Googol or 10^100).
- The (decimal) output must be written to stdout.
- Your score is the number of bytes of your code.
- Your answer must begin with [Programming language] - [Score in bytes]
- Standard loopholes are not allowed.
7 --> 3 43 --> 5 178 --> 4 255 --> 1 65534 --> 1 65537 --> 12 1915195950546866338219593388801304344938837974777392666909760090332935537657862595345445466245217915 --> 329
What's interesting is that the number of cycles is related to the length of the binary representation, except for a few exceptions where the number of cycles is shorter because of the pattern in the bitstring (for example
111110 cycles after 1 iteration). This creates an interesting opportunity to optimize code length using the underlying pattern instead of calculating the number of cycles.