A345117 a(n) is the index (in Z/nZ) of the first already visited element in the process of moving around Z/nZ, starting at 0 with stride 1 and increasing stride by 1 after each step.
0, 1, 0, 2, 1, 0, 3, 4, 1, 0, 10, 3, 2, 1, 0, 8, 11, 3, 17, 1, 0, 6, 9, 21, 3, 10, 1, 0, 4, 6, 12, 16, 3, 21, 1, 0, 5, 28, 6, 15, 26, 3, 38, 1, 0, 45, 18, 9, 6, 28, 15, 3, 7, 1, 0, 10, 21, 20, 52, 6, 8, 29, 3, 32, 1, 0, 59, 10, 36, 21, 27, 6, 46, 62, 3, 15, 1
Offset: 1
Examples
For n = 3 we start with Z/3Z represented as [0,1,2]. In the first step we mark the zero to obtain [0*,1,2] and move one step (to 1). Then we mark the 1 to obtain [0*,1*,2] and move two steps (to 0*). We have landed on a number already visited, so the process ends here, and as we have landed on 0 last, a(3) = 0. For n = 4 we start with [0,1,2,3]. After the first step we get [0*,1,2,3] and we land at 1. After the second step we have [0*,1*,2,3] and we have landed at 3. In the penultimate step we mark the 3 to get [0*,1*,2,3*] and move 3 steps (to 2). We mark the 2 and move 4 steps to the 2*, which we have already visited. Therefore, a(4) = 2. For n = 5 the list of steps is as follows: [0,1,2,3,4] -> [0*,1,2,3,4] -> [0*,1*,2,3,4] -> [0*,1*,2,3*,4] -> we land on 1 again, therefore a(5) = 1. For n = 7 the list of steps is as follows: [0,1,2,3,4,5,6] -> [0*,1,2,3,4,5,6] -> [0*,1*,2,3,4,5,6] -> [0*,1*,2,3*,4,5,6] -> [0*,1*,2,3*,4,5,6*] -> we land on 3 again, therefore a(7) = 3. Note: the '*' after a number means that this number was already visited.
Links
- Sean A. Irvine, Java program (github)
Programs
-
Python
def a(n): row = ['x' for i in range(n)] free = True count = index = 0 while(free): row[index] = count count += 1 index = (index + count) % n if row[index] != 'x': free = False return index