After brute-forcing for small values of N (using the following program), I got two sequences. Luckily both are on OEIS.
Brute-force program
def solve(N, right_shift = False):
if right_shift:
arr = [i for i in range(1, N + 1)]
while arr.__len__() > 1:
arr = [arr[-1]] + arr[: arr.__len__() - 1]
arr.pop()
return arr[0]
else:
arr = [i for i in range(1, N + 1)]
while arr.__len__() > 1:
arr = arr[1:] + [arr[0]]
arr.pop(0)
return arr[0]
for N in range(1, 100):
print(solve(N, right_shift = False), end = " ")
For the right rotate version: A080079 - OEIS
For the left rotate version: A006257 - OEIS (Josephus Problem).
So, now you have to solve them separately.
- For the left rotate version, there is an O(\log{(N)}) solution in Python.
def left_rotate(n):
return 0 if n==0 else 2 * (n - 2 ** int(math.log(n, 2))) + 1
- For the right rotate version, a set of recurrence relations was provided on \text{OEIS}.
a(0) = 0, a(2\times n) = 2\times a(n), a(2\times n + 1) = 2\times a(n) - 1 + 2\times [n==0].
2 Likes
-
Thanks a lot for the the help .
-
I will be forever greatful to You.
-
Thanks for letting me know about this beautiful website https://oeis.org/
It will be very helpful
1 Like