[Question]
  [
## The challenge
Write a function that takes two positive integers \$n\$ and \$k\$ as arguments and returns the number of the last person remaining out of \$n\$ after counting out each \$k\$-th person.
This is a code-golf challenge, so the shortest code wins.
## The problem
\$n\$ people (numbered from \$1\$ to \$n\$) are standing in a circle and each \$k\$-th is counted out until a single person is remaining (see the corresponding [wikipedia article](http://en.wikipedia.org/wiki/Josephus_problem)). Determine the number of this last person.
E.g. for \$k=3\$ two people will be skipped and the third will be counted out. I.e. for \$n=7\$ the numbers will be counted out in the order \$3 \, 6 \, 2 \, 7 \, 5 \, 1\$ (in detail \$\require{cancel}1 \, 2 \, \cancel{3} \, 4 \, 5 \, \cancel{6} \, 7 \, 1 \, \cancel{2} \, 4 \, 5 \, \cancel{7} \, 1 \, 4 \, \cancel{5} \, 1 \, 4 \, \cancel{1} \, 4\$) and thus the answer is \$4\$.
## Examples
```
J(7,1) = 7      // people are counted out in order 1 2 3 4 5 6 [7]
J(7,2) = 7      // people are counted out in order 2 4 6 1 5 3 [7]
J(7,3) = 4      // see above
J(7,11) = 1
J(77,8) = 1
J(123,12) = 21
```
  
[Answer]
## Minsky Register Machine (25 non-halt states)
Not technically a function, but it's in a computing paradigm which doesn't have functions per se...
This is a slight variation on the main test case of my first [MRM interpretation challenge](https://codegolf.stackexchange.com/questions/1864/simulate-a-minsky-register-machine-i):
![Josephus problem as Minsky register machine](https://i.stack.imgur.com/fxECx.png)
Input in registers `n` and `k`; output in register `r`; it is assumed that `r=i=t=0` on entry. The first two halt instructions are error cases.
[Answer]
## Python, 36
I also used the formula from wikipedia:
```
J=lambda n,k:n<2or(J(n-1,k)+k-1)%n+1
```
Examples:
```
>>> J(7,3)
4
>>> J(77,8)
1
>>> J(123,12)
21
```
[Answer]
### Mathematica, ~~38~~ 36 bytes
Same Wikipedia formula:
```
1~f~_=1
n_~f~k_:=Mod[f[n-1,k]+k,n,1]
```
[Answer]
## GolfScript, 17 bytes
```
{{@+\)%}+\,*)}:f;
```
Takes `n k` on the stack, and leaves the result on the stack.
## Dissection
This uses the recurrence `g(n,k) = (g(n-1,k) + k) % n` with `g(1, k) = 0` (as described in the Wikipedia article) with the recursion replaced by a fold.
```
{          # Function declaration
           # Stack: n k
  {        # Stack: g(i-1,k) i-1 k
    @+\)%  # Stack: g(i,k)
  }+       # Add, giving stack: n {k block}
  \,*      # Fold {k block} over [0 1 ... n-1]
  )        # Increment to move from 0-based to 1-based indexing
}:f;
```
[Answer]
## C, 40 chars
This is pretty much just the formula that the above-linked wikipedia article gives:
```
j(n,k){return n>1?(j(n-1,k)+k-1)%n+1:1;}
```
For variety, here's an implementation that actually runs the simulation (99 chars):
```
j(n,k,c,i,r){char o[999];memset(o,1,n);for(c=k,i=0;r;++i)(c-=o[i%=n])||(o[i]=!r--,c=k);
return i;}
```
[Answer]
## dc, 27 bytes
```
[d1-d1<glk+r%1+]dsg?1-skrxp
```
Uses the recurrence from the Wikipedia article. Explanation: 
```
# comment shows what is on the stack and any other effect the instructions have
[   # n
d   # n, n
1-  # n-1, n
d   # n-1, n-1, n
1<g # g(n-1), n ; g is executed only if n > 1, conveniently g(1) = 1
lk+ # g(n-1)+(k-1), n; remember, k register holds k-1
r%  # g(n-1)+(k-1) mod n
1+  # (g(n-1)+(k-1) mod n)+1
]
dsg # code for g; code also stored in g
?   # read user input => k, n, code for g
1-  # k-1, n, code for g
sk  # n, code for g; k-1 stored in register k
r   # code for g, n
x   # g(n)
p   # prints g(n)
```
[Answer]
## J, 45 characters
```
j=.[:{.@{:]([:}.]|.~<:@[|~#@])^:(<:@#)>:@i.@[
```
Runs the simulation.
Alternatively, using the formula (31 characters):
```
j=.1:`(1+[|1-~]+<:@[$:])@.(1<[)
```
I hope Howard doesn't mind that I've adjusted the input format slightly to suit a dyadic verb in J.
Usage:
```
   7 j 3
4
   123 j 12
21
```
[Answer]
### GolfScript, ~~32~~ 24 bytes
```
:k;0:^;(,{))^k+\%:^;}/^)
```
*Usage:*
Expects the two parameters *n* and *k* to be in the stack and leaves the output value.
(thanks to Peter Taylor for suggesting an iterative approach and many other tips)
The old (recursive) approach of 32 chars:
```
{1$1>{1$(1$^1$(+2$%)}1if@@;;}:^;
```
This is my first GolfScript, so please let me know your criticisms.
[Answer]
## R, 48
```
J=function(n,k)ifelse(n<2,1,(J(n-1,k)+k-1)%%n+1)
```
Running Version with examples: <http://ideone.com/i7wae>
[Answer]
### Groovy, 36 bytes
```
def j(n,k){n>1?(j(n-1,k)+k-1)%n+1:1}
```
[Answer]
## Haskell, 68
```
j n=q$cycle[0..n]
q l@(i:h:_)k|h/=i=q(drop(k-1)$filter(/=i)l)k|1>0=i
```
Does the actual simulation. Demonstration:
> 
> GHCi> j 7 1  
> 
>  7  
> 
>  GHCi> j 7 2  
> 
>  7  
> 
>  GHCi> j 7 3  
> 
>  4  
> 
>  GHCi> j 7 11  
> 
>  1  
> 
>  GHCi> j 77 8  
> 
>  1  
> 
>  GHCi> j 123 12  
> 
>  21
> 
> 
> 
[Answer]
### Scala, 53 bytes
```
def?(n:Int,k:Int):Int=if(n<2)1 else(?(n-1,k)+k-1)%n+1
```
[Answer]
## C, 88 chars
Does the simulation, doesn't calculate the formula.  
Much longer than the formula, but shorter than the other C simulation.
```
j(n,k){
    int i=0,c=k,r=n,*p=calloc(n,8);
    for(;p[i=i%n+1]||--c?1:--r?p[i]=c=k:0;);
    return i;
}
```
Notes:  
1. Allocates memory and never releases.  
2. Allocates `n*8` instead of `n*4`, because I use `p[n]`. Could allocate `(n+1)*4`, but it's more characters.
[Answer]
## C++, 166 bytes
### Golfed:
```
#include<iostream>
#include <list>
int j(int n,int k){if(n>1){return(j(n-1,k)+k-1)%n+1;}else{return 1;}}
int main(){intn,k;std::cin>>n>>k;std::cout<<j(n,k);return 0;}
```
### Ungolfed:
```
#include<iostream>
#include <list>
int j(int n,int k){
    if (n > 1){
        return (j(n-1,k)+k-1)%n+1;
    } else {
        return 1;
    }
}
int main()
{
    int n, k;
    std::cin>>n>>k;
    std::cout<<j(n,k);
    return 0;
}
```
[Answer]
### Ruby, 39 bytes
```
def J(n,k)
n<2?1:(J(n-1,k)+k-1)%n+1
end
```
Running version with test cases: <http://ideone.com/pXOUc>
[Answer]
# Q, 34 bytes
```
f:{$[x=1;1;1+mod[;x]f[x-1;y]+y-1]}
```
Usage:
```
q)f .'(7 1;7 2;7 3;7 11;77 8;123 12)
7 7 4 1 1 21
```
[Answer]
## Ruby, 34 bytes
```
J=->n,k{n<2?1:(J(n-1,k)+k-1)%n+1}
```
[Answer]
# Powershell, 56 bytes
```
param($n,$k)if($n-lt2){1}else{((.\f($n-1)$k)+$k-1)%$n+1}
```
Important! The script calls itself recursively. So save the script as `f.ps1` file in the current directory. Also you can call a script block variable instead script file (see the test script below). That calls has same length.
Test script:
```
$f = {
param($n,$k)if($n-lt2){1}else{((&$f($n-1)$k)+$k-1)%$n+1}
}
@(
    ,(7, 1, 7)
    ,(7, 2, 7)
    ,(7, 3, 4)
    ,(7, 11, 1)
    ,(77, 8, 1)
    ,(123,12, 21)
) | % {
    $n,$k,$expected = $_
    $result = &$f $n $k
    "$($result-eq$expected): $result"
}
```
Output:
```
True: 7
True: 7
True: 4
True: 1
True: 1
True: 21
```
[Answer]
# [Nibbles](http://golfscript.com/nibbles/index.html), 6 bytes
```
+~/\,@0%+_@
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m708LzMpKSe1eMGCpaUlaboWq7Xr9GN0HAxUteMdICJQiTXRSoZGSjpAwlgpFioGAA)
Uses the formula as described on Wikipedia:
\$J(n,k) = g(n,k) + 1\$, where
$$\begin{align}g(1,k) &= 0 \\ g(n,k) &= (g(n-1,k)+k) \bmod n\end{align}$$
```
+~/\,@0%+_@
+~          Add 1
  /          fold right
   \          reverse
    ,          range from 1 to
     @          n
      0       with initial value 0
       %      modulo
        +      add
         _      k
          @     accumutalor
               item
```
[Answer]
# Haskell, 29
Using the formula from wikipedia.
```
1#_=1
n#k=mod((n-1)#k+k-1)n+1
```
[Answer]
# JavaScript (ECMAScript 5), 48 bytes
Using ECMAScript 5 since that was the latest version of JavaScript at the time this question was asked.
```
function f(a,b){return a<2?1:(f(a-1,b)+b-1)%a+1}
```
## ES6 version (non-competing), 33 bytes
```
f=(a,b)=>a<2?1:(f(a-1,b)+b-1)%a+1
```
## Explanation
Not much to say here. I'm just implementing the function the Wikipedia article gives me.
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), 11 bytes
```
L[Dg#²<FÀ}¦
```
[Try it online!](https://tio.run/##MzBNTDJM/f/fJ9olXfnQJhu3ww21h5b9/29oZMxlaAQA "05AB1E – Try It Online")
```
L           # Range 1 .. n
 [Dg#       # Until the array has a length of 1:
     ²<F }  #   k - 1 times do:
        À   #     Rotate the array
          ¦ #   remove the first element
```
[Answer]
# [8th](http://8th-dev.com/), 82 bytes
**Code**
```
: j >r >r a:new ( a:push ) 1 r> loop ( r@ n:+ swap n:mod ) 0 a:reduce n:1+ rdrop ;
```
**SED** (Stack Effect Diagram) is: `n k -- m`
**Usage and explanation**
The algorithm uses an array of integers like this: if people value is 5 then the array will be [1,2,3,4,5]
```
: j \ n k -- m
    >r                               \ save k
    >r a:new ( a:push ) 1 r> loop    \ make array[1:n]
    ( r@ n:+ swap n:mod ) 0 a:reduce \ translation of recursive formula with folding using an array with values ranging from 1 to n
    n:1+                             \ increment to move from 0-based to 1-based indexing
    rdrop                            \ clean r-stack
;
ok> 7 1 j . cr
7
ok> 7 2 j . cr
7
ok> 7 3 j . cr
4
ok> 7 11 j . cr
1
ok> 77 8 j . cr
1
ok> 123 12 j . cr
21
```
[Answer]
# [J](http://jsoftware.com/), 24 bytes
```
1+1{1([:|/\+)/@,.1|.!.0#
```
[Try it online!](https://tio.run/##FcexCoAgFEbh3af4q6Gk0K4OhiH0HgkNkURLQ2P17HYbPjjnyOlC8OjBMrV0UzP7R8dW6qlT9KhC9VWWolSoU/A1Orwe6RJiW/cTi0EzJi0jHIgZZv/mcRhAxrL8AQ "J – Try It Online")
An iterative approach based on the dynamic programming solution.
## Explanation
```
1+1{1([:|/\+)/@,.1|.!.0#  Input: n (LHS), k (RHS)
                       #  Make n copies of k
                 1|.!.0   Shift left by 1 and fill with zero
    1          ,.         Interleave with 1
             /@           Reduce using
           +                Addition
        |/\                 Cumulative reduce using modulo
  1{                      Select value at index 1
1+                        Add 1
```
[Answer]
# [J](http://jsoftware.com/), 19 bytes
```
1+(}:@|.^:({:@])i.)
```
[Try it online!](https://tio.run/##y/qvpKeepmBrpaCuoKNgoGAFxLp6Cs5BPm7/DbU1aq0cavTirDSqrRxiNTP1NP9rcqUmZ@QrGCqkKZhDmEYIpjGCaYikwgLEhImDlBsaGf8HAA "J – Try It Online")
### How it works
```
1+(}:@|.^:({:@])i.)   Left: k, Right: n
                i.    Generate [0..n-1]
        ^:            Repeat:
   }:@|.                Rotate left k items, and remove the last item
          ({:@])        n-1 (tail of [0..n-1]) times
1+                    Add one to make the result one-based
```
[Answer]
# [Dart](https://www.dartlang.org/), 33 bytes
```
f(n,k)=>n<2?1:(f(n-1,k)+k-1)%n+1;
```
[Try it online!](https://tio.run/##Tc1BCsIwEAXQfU8xi0oTOhUnFSrW1pWnCFkEpbQUo4TETcnZYxC0bj7/DQP/pq2LcWAGZ9715iTOdGSJFaVDOVfEN6akNt71ZBhfMoCXtuCgA5k6gGyQsFH4hfhHjfsVQIT0Y4OHVSRqJIGCVLJqs5RuOzzsRV9HxvxnFuBpJ@NYkS8D83Kn0EtSPEDXQ754KVQoeJseQ8oQ3w "Dart – Try It Online")
[Answer]
# [Japt](https://github.com/ETHproductions/japt), 15 bytes
```
_é1-V Å}h[Uõ] Ì
```
[Try it online!](https://ethproductions.github.io/japt/?v=1.4.6&code=X+kxLVYgxX1oW1X1XSDM&input=MTIzCjEy)
A byte could be saved by [0-indexing k](https://ethproductions.github.io/japt/?v=1.4.6&code=X+lWbinFfWhbVfVdIMw=&input=MTIzCjEx), but it isn't actually an index so I decided against that.
Explanation:
```
         [Uõ]      :Starting with the array [1...n]
_      }h          :Repeat n-1 times:
 é1-V              : Rotate the array right 1-k times (i.e. rotate left k-1 times)
      Å            : Remove the new first element
              Ì    :Get the last value remaining
```
[Answer]
# Japt `-h`, 10 bytes
```
õ
£=éVn1¹v
```
[Try it](https://ethproductions.github.io/japt/?v=1.4.6&code=9QqjPelWbjG5dg==&input=NzcsOAotaA==)
[Answer]
# [APL (Dyalog Unicode)](https://www.dyalog.com/), 17 bytes
```
{¯1↓⍺⌽⍵}⍣{1=≢⍺}∘⍳
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT///v/rQesNHbZMf9e561LP3Ue/W2ke9i6sNbR91LgIK1T7qmPGod/P/tEdtEx719j3qan7Uu@ZR75ZD640ftU181Dc1OMgZSIZ4eAb/N1RIUzDnMgKTxmDSECJkASKBPJCUoZExAA "APL (Dyalog Unicode) – Try It Online")
Takes input as `k f n`.
## Explanation
```
{¯1↓⍺⌽⍵}⍣{2=≢⍵}∘⍳
               ∘⍳ list from 1..n
        ⍣         (f⍣g) → apply f repeatedly till g is true
{¯1↓⍺⌽⍵}          f: rotate list through k elements, drop last
         {1=≢⍺}   g: is the length = 1, for the previous iteration?
```
# [APL (Dyalog Unicode)](https://www.dyalog.com/), 36 bytes
```
1+{⍺>1:⍺|⍵+⍵∇⍨⍺-1⋄0}
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT///31C7@lHvLjtDKyBZ86h3qzYQP@pof9S7Aiiga/iou8Wg9n/ao7YJj3r7HnU1P@pd86h3y6H1xo/aJj7qmxoc5AwkQzw8g/8bKqQBNSmYcxnBGMYwhiFczgLKAIpBlRkaGQMA "APL (Dyalog Unicode) – Try It Online")
Recursive function.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 7 bytes
```
RṙṖ¥ƬṖṪ
```
[Try it online!](https://tio.run/##y0rNyan8/z/o4c6ZD3dOO7T02Bog9XDnqv@Hlyv9/x9trqOAQEBsaGQc@z/aUEfBSEfBGMgFsixAorEA "Jelly – Try It Online")
## How it works
```
RṙṖ¥ƬṖṪ - Main link. Takes n on the left and k on the right
R       - Range; Yield [1, 2, ..., n]
   ¥Ƭ   - Do the following to a fixed point and collect intermediate steps:
 ṙ      -   Rotate k steps to the left
  Ṗ     -   Remove the last element
     Ṗ  - Remove the empty list (the fixed point)
      Ṫ - Return the single element left over
```
]