Python 2, 30 bytes

lambda n:int(bin(n)[3:]+'1',2)

Takes the binary expansion of n and moves the initial 1 to the end.

• 4
  \$\begingroup\$ That is witchcraft. \$\endgroup\$

  Leaky Nun

  – Leaky Nun

  2016年06月26日 01:40:48 +00:00

  Commented Jun 26, 2016 at 1:40
• 1
  \$\begingroup\$ ಠ_ಠ what is this \$\endgroup\$

  downrep_nation

  – downrep_nation

  2016年06月26日 05:41:45 +00:00

  Commented Jun 26, 2016 at 5:41

Python 2, 32 bytes

a=lambda n:n and(n%2+a(n/2))*2-1

33 bytes:

a=lambda n:n and 2*a(n/2)-(-1)**n

Uses the recursive formula on the OEIS page.

• a(2*n) = 2*a(n)-1
• a(2*n+1) = 2*a(n)+1

• \$\begingroup\$ Why a=? Do you need it? \$\endgroup\$

  NoOneIsHere

  – NoOneIsHere

  2016年06月26日 05:07:37 +00:00

  Commented Jun 26, 2016 at 5:07
• \$\begingroup\$ @NoOneIsHere To recurse. \$\endgroup\$

  xnor

  – xnor

  2016年06月26日 06:34:55 +00:00

  Commented Jun 26, 2016 at 6:34

Java 7, (削除) 65 (削除ここまで) 53 bytes

int f(int n){return(n-Integer.highestOneBit(n))*2+1;}

Using the algorithm for k=2 Josephus from Wikipedia. Thanks to Leaky Nun for finding the builtin.

• \$\begingroup\$ i&i-1 saves 2 bytes \$\endgroup\$

  Leaky Nun

  – Leaky Nun

  2016年06月26日 01:19:06 +00:00

  Commented Jun 26, 2016 at 1:19
• \$\begingroup\$ Spare parens ftw >_> \$\endgroup\$

  Geobits

  – Geobits

  2016年06月26日 01:20:41 +00:00

  Commented Jun 26, 2016 at 1:20
• \$\begingroup\$ int f(int n){return(n-Integer.highestOneBit(n))*2+1;} \$\endgroup\$

  Leaky Nun

  – Leaky Nun

  2016年06月26日 01:30:35 +00:00

  Commented Jun 26, 2016 at 1:30
• \$\begingroup\$ Dammit, I was doing highestOneBit manually and got it to 56 just now. I didn't know there was a built-in for it :/ \$\endgroup\$

  Geobits

  – Geobits

  2016年06月26日 01:31:38 +00:00

  Commented Jun 26, 2016 at 1:31
• 2
  \$\begingroup\$ Yeah, I use Java 7 for golfing just to avoid shady (imo) lambda nonsense :P \$\endgroup\$

  Geobits

  – Geobits

  2016年06月26日 01:33:56 +00:00

  Commented Jun 26, 2016 at 1:33

Pyth, (削除) 22 (削除ここまで) (削除) 13 (削除ここまで) (削除) 12 (削除ここまで) 9 bytes

Credits to Geobit's algorithm for saving 9 bytes. It works like magic.

Credits to xnor's witchcraft for saving 3 bytes. It is simply witchcraft.

(削除) heu+G=Z%e.f!/G%ZQ2ZQQY (削除ここまで)
(削除) u?sIlH1+2GSQ1 (削除ここまで)
(削除) hyaefgQT^L2 (削除ここまで)
i.<.BQ1 2

Test suite.

Jelly, 4 bytes

Since xnor came up with this algorithm, I will make this community wiki.

Bṙ1Ḅ

Try it online!

Explanation

Bṙ1Ḅ
B convert to binary
 ṙ1 left-rotate by 1
 Ḅ convert from binary

VBA, (削除) 57 (削除ここまで) 67 bytes

Well, this technically ought to work (57 bytes):

Function Z(N):Z=2*(N-2^Int(Log(N)/Log(2)))+1:End Function

But actually, because occasionally the log value of a power of two is not quite an exact multiple of the log of 2, we need a few more bytes:

Function Z(N):Z=2*(N-2^Int(Log(N)/Log(2))):Z=1-Z*(Z<N):End Function

If there were a built-in binary converter, it would be much shorter.

The recursion version is a tie, basically, but needs a line-feed for the IF

Function Y(N):Y=1:If N>1 Then Y=2*Y(N2円)+2*(N2円=N/2)+1
End Function

J, 10 bytes

(1&|.)&.#:

Using the formula where a(n) = n written in binary and rotated left by 1 place. Similar to what is used in @xnor's solution.

Using 19 bytes, we can play the game according to the rules in the challenge.

[:(2&}.,{.)^:_>:@i.

This solution only performs array manipulation in order to reach a final player.

Usage

Extra commands used for formatting multiple input/output with multiple functions.

 f =: (1&|.)&.#:
 g =: [:(2&}.,{.)^:_>:@i.
 (,.f"0,.g"0) i. 10
0 0 0
1 1 1
2 1 1
3 3 3
4 1 1
5 3 3
6 5 5
7 7 7
8 1 1
9 3 3

Explanation

(1&|.)&.#: Input: n
 #: Convert to binary
( )&. Compose next function on the binary value
 1&|. Rotate left by 1 place
( )&. Compose the inverse of the previous function on the result
 #: The inverse: convert from binary to decimal and return result
[:(2&}.,{.)^:_>:@i. Input: n
 i. Creates the range [0, 1, ..., n-1]
 >:@ Increment each in the range to get [1, 2, ..., n]
[:( )^:_ Nest the function until the result does not change and return
 2&}. Drop the first two items in the list
 {. Get the head of the list
 , Join them together. This makes it so that the head of the list
 is always the current player and the one after the head is the
 player to be removed

Python, 29 bytes

f=lambda n:n&n-1<1or f(n-1)+2

Outputs 1 as True when n is a power of 2, checked by n&n-1 being 0. Otherwise, outputs 2 higher than the previous value.

28 bytes:

Adapting grc's general solution to the case k=2 gives a better solution

f=lambda n:n and-~f(n-1)%n+1

Rather than explicitly checking for powers of 2, it zeroes out the result before incrementing each time f(n-1) catches up to n-1

• code-golf