# The Switching Sequence

## Intro

The Switching sequence is defined like so:

Start with n people standing in a circle (6 for this example).

 1  2
6    3
5  4


Starting from person 1, the person that is to the left of the "chosen" person is removed.

 1
6    3
5  4


The removed person can "switch" the removal method up:

• If the removed person is even (which it is in this case), the next removed person will be to the right of the next "chosen" person.
• If the removed person is odd, the next removed person will be to the left of the next "chosen" person.

The next chosen person is also dependent on the previously removed person.

• If the removed person is even, the next chosen person will be to the right of the previous chosen person.
• If the removed person is odd, see above, but replace "right" with "left".

So the next chosen person is then 6.

Now we remove the person to the right of 6, which is 5:

 1
6    3
4


Because 5 is odd, the removed person is now to the left. The new chosen person is 1.

We now remove 3:

 1
6
4


We continue this process, until we're left with 1 number - in this example, the final number is 1. So therefore S(6) = 1.

The first few numbers are:

 n | S(n)
---------
1 | 1
2 | 1
3 | 3
4 | 1
5 | 5
6 | 1
7 | 3
8 | 6
9 | 5
10 | 6
11 | 9


Your task is to make a program (or a function) that returns S(n) (the nth number in the Switching sequence) when given n, using the least amount of bytes.

Example inputs and outputs:

1  -> 1
10 -> 6
13 -> 13


You are guaranteed to get a positive integer.

This is , so shortest code in bytes wins!

Note: There is no OEIS sequence (what?), to save you the trouble of searching.

• No hits on oeis, to save people the search.
– xnor
Oct 29, 2016 at 6:17
• Obviously 2 never remains, but does 7? Oct 29, 2016 at 6:54
• @JonathanAllan I just checked for the first 1000 terms, and the result is currently "no". I'm not sure though - should I put that as a "side challenge" thing that people can attempt to prove or something? It's for brownie points, so it doesn't detract from the challenge. Oct 29, 2016 at 6:56
• Maybe it will be obvious once someone comes up with a method other than by following your instructions... Oct 29, 2016 at 7:00
• How do you expect people solving this without an OEIS? Someone push an OEIS, please? Oct 29, 2016 at 7:12

# Python 2, 183 94 bytes

-4 bytes thanks to Artyer (use input() and print rather than def and return)
-1 byte thanks to FlipTack (use print-~p[0] rather than print p[0]+1)

p=range(input())
d=i=1
while p[1:]:m=p.pop(i)%2;i-=m+m-(d<0);d=-m|1;i+=d;i%=len(p)
print-~p[0]


repl.it

This just follows the instructions given, I've noticed some pattern, maybe it could be exploited?

The only changes are:

• to use 0 based indexing (so even people are odd and vice-versa) - this is saves 5 bytes in the golfed logic and is corrected at the end with +1
• to use 1 as left and -1 as right (to use a range - just like everyone is facing outwards instead)
• to change the logic of the step where the next chosen individual is found to account for poping from the list making the "pointer" index already step one to the right in the list (or to the left in original terminology).

Ungolfed:

def circle(n):
people = range(n) # p
direction = 1 # d
removeIndex = 1 # i
while n > 1:
removingMod2 = people.pop(removeIndex) % 2 # m
removeIndex -= removingMod2 + removingMod2 - (direction == -1)
direction = -removingMod2 or 1
removeIndex += direction
n -= 1
removeIndex %= n
return people[0] + 1

• Can the last line be print-~p[0]? Jan 29, 2017 at 9:32
• Why yes it can! Jan 29, 2017 at 11:23