I'm playing around with Project Euler's Problem 220, and I'm a little confused about the Wikipedia article on the topic, Dragon Curve. On the topic of calculating the direction of the nth turn without having to draw the entire curve, it says:
First, express n in the form k * 2^m where k is an odd number. The direction of the nth turn is determined by k mod 4 i.e. the remainder left when k is divided by 4. If k mod 4 is 1 then the nth turn is R; if k mod 4 is 3 then the nth turn is L.
For example, to determine the direction of turn 76376:
76376 = 9547 x 8. 9547 = 2386x4 + 3 so 9547 mod 4 = 3 so turn 76376 is L
- Is there a clever way to figure out if n can be expressed as k2^m, apart from checking divisibility by successive powers of 2?
- What does it mean if n cannot be expressed in such a way?
(The problem involves calculating the position of a point on a Dragon curve with length 2^50, so actually drawing the curve is out of the question.)