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,4

Links

Table of n, a(n) for n=1..77.

Sean A. Irvine, Java program (github)

Formula

a(n) = A000217(A212652(n)) mod n. - Rémy Sigrist, Jun 08 2021

Example

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.

Prog

(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

Crossrefs

Cf. A000217, A212652.

Sequence in context: A368099 A256130 A257566 * A188286 A363154 A101603

Adjacent sequences: A345114 A345115 A345116 * A345118 A345119 A345120

Keyword

nonn,easy

Author

Josip Ivica, Jun 08 2021

Status

approved