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.

Example of an invariant measure

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 11001001).

  1. 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

  2. Fold the first half over the second half. Note that the order of the first half is reversed, as we rotate it while folding.


  3. 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.

The challenge

  • 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

Final note

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.

  • \$\begingroup\$ If the bit length of the number shortens during iteration, do we cut and fold using the original bit length, or the current one? \$\endgroup\$
    – xnor
    Commented Oct 13, 2015 at 20:53
  • 2
    \$\begingroup\$ @xnor I would assume the original one, otherwise you would never complete cycle, right? \$\endgroup\$ Commented Oct 13, 2015 at 21:06
  • \$\begingroup\$ Related: codegolf.stackexchange.com/questions/48027/discrete-bakers-map/… \$\endgroup\$ Commented Oct 13, 2015 at 23:46

4 Answers 4


CJam, 34 bytes


Nothing fancy, it just applies the map until we get back to the input, and print the number of iterations that took.

Test it here.

  • \$\begingroup\$ First in! Look at you, shooting code faster than your shadow! \$\endgroup\$
    – agtoever
    Commented Oct 13, 2015 at 20:29

Python 2, 175 154 149 bytes

i=o='0'+i if len(i)%2 else i
while i!=o or c==0:
 for x,y in zip(i[:j][::-1],i[j:]):a+=x+y
print c

Ideone link

Thanks to agtoever for 27 bytes!

  • 1
    \$\begingroup\$ No need for the lambda. Once the length is even, it stays even. \$\endgroup\$
    – agtoever
    Commented Oct 13, 2015 at 21:29
  • \$\begingroup\$ Excellent point, thanks! \$\endgroup\$
    – Celeo
    Commented Oct 13, 2015 at 21:35
  • \$\begingroup\$ Change ` while 1` with while i!=o|c==0 and drop the if i==o:break. Saves 5. Maybe (note sure) you also don't need a. Just use i. Saves an assignment (4 bytes). Also the assignment of j can be put outside the loop. \$\endgroup\$
    – agtoever
    Commented Oct 14, 2015 at 8:59
  • \$\begingroup\$ Thanks for the additional saves, @agtoever. I got a TypeError when attempting to implement the while i!=c|c==0 replacement, but still was able to save some bytes with a standard ` or `. \$\endgroup\$
    – Celeo
    Commented Oct 14, 2015 at 16:21

Pyth, 21 bytes

I'm typing this on my phone, so please make sure to notify me of any mistakes.


Try it online.


APL (Dyalog Extended), 37 bytes

≢{⊃,/↓⍉⌽@1⊢2 ¯1⍴{2|≢⍵:0,⍵⋄⍵}⍵}⌂traj⊤⎕

Try it online!

A full program which takes a single number as input.

The traj function does a lot of heavy lifting here(thanks to Bubbler for suggesting it and helping ot golf this).

The (,,⍤0)/ idiom from APLcart is used to interleave lists together, but instead this uses ,/↓⍉⌽ since it is a matrix.


≢{⊃,/↓⍉⌽@1⊢2 ¯1⍴{2|≢⍵:0,⍵⋄⍵}⍵}⌂traj⊤⎕
                                   ⊤⎕ convert input to base-2
 {                           }⌂traj   calculate trajectory when the following function is applied repeatedly:
                {2|≢⍵:0,⍵⋄⍵}⍵         prepend a 0 if there are an odd number of bits
           2 ¯1⍴                     cut into two rows
       ⌽@1⊢                          apply reverse to first row
   ,/↓⍉                              transpose, concatenate into a vector
  ⊃                                  unenclose
≢                                    get length of the resulting list

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.