A clock face has n ticks, and its hand jumps k ticks anticlockwise at every step (a negative k jumps clockwise). Draw the face as the unit circle of the complex plane, with tick 0 at the number 1. One jump is the multiplication by the unit arrow
(cmath.exp(2j * math.pi * k / n)), so after j jumps the hand points at w^j = e^{2\pi i kj/n}. Because w^n = e^{2\pi i k} = 1, the number w is an n-th root of unity: n jumps always bring the hand back to 1. Often it comes back sooner. The order of w is the smallest m \ge 1 with w^m = 1.
Write clock_cycle(n, k) that returns a pair (m, cycle): the order m, and the list cycle of the m points the hand visits, w^0 = 1, w^1, \dots, w^{m-1}, in that order.
Press Run with print(sum(clock_cycle(12, 5)[1])) to see a curious fact: the points of a cycle longer than 1 add up to 0 (up to rounding). It will come back much later in this path.
Examples
Input: n = 4, k = 1
Output: (4, [1, 1j, -1, -1j])
Explanation: quarter turns visit all four ticks before coming back.
Input: n = 6, k = 4
Output: (3, [1, (-0.5-0.8660254037844386j), (-0.5+0.8660254037844386j)])
Explanation: each jump is 4/6 of a turn. After 3 jumps the hand has made exactly 2 turns.
Values like (6.1e-17+1j) for 1j count as correct. Mind that w ** 4 == 1 can be False for w = e^{2\pi i/4}: floating-point powers are rarely exactly 1.
Constraints
1 <= n <= 1000and-1000 <= k <= 1000- answers are compared with a tolerance of
1e-6; do not round
Goals
- Build the n-th roots of unity e^(2*pi*i*k/n) with cmath.exp
- Find the first power of a root of unity that lands back on 1
- Avoid testing floating-point results with == 1