# Josephus problem (counting out)

## 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). 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 1 2 3 4 5 6 7 1 2 4 5 7 1 4 5 1 4 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


## 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;

• Can you add an explanation, please? – Sherlock9 Nov 26 '15 at 18:49
• @Sherlock9, I managed to figure out what I was doing despite almost 3.5 years having passed. Who says that GolfScript is read-only? ;) – Peter Taylor Nov 26 '15 at 21:45
• Ahem. s/read/write/ – Peter Taylor Nov 26 '15 at 22:40
• Sorry. I've only started learning Golfscript two or three days ago and I every time I read your code, I kept thinking I'd missed something. ... Ok, I'm still missing something, how does folding {k block} over [0..n-1] get you g(0,k) 0 k to start with? Sorry, if I'm posting these questions in the wrong place. – Sherlock9 Nov 27 '15 at 5:30
• @Sherlock9, fold works pairwise, so the first thing it does is evaluate 0 1 block. Very conveniently, that happens to be g(1, k) (2-1) block. So it's starting at g(1,k) 1 rather than g(0,k) 0. Then after executing the block, it pushes the next item from the array (2) and executes the block again, etc. – Peter Taylor Nov 27 '15 at 6:47

## 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:

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.

• I think you have to adjust your machine slightly. If I read it correctly the output is zero-indexed, isn't it? – Howard May 21 '12 at 13:45
• I was thinking the other way: if k=1 then r=0. Hmm, I have to think about this one again... – Howard May 21 '12 at 14:40
• As I read your diagram, i is simply counting from 2 to n while r is the register which accumulates the result. – Howard May 21 '12 at 15:39
• @Howard, I looked up the comments I made when I first wrote this and you're right. Whoops. Now corrected (I believe - will test more thoroughly later). – Peter Taylor May 21 '12 at 16:19

## 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


### Mathematica, 38 36 bytes

Same Wikipedia formula:

1~f~_=1
n_~f~k_:=Mod[f[n-1,k]+k,n,1]

• If[#<2,1,Mod[#0[#-1,#2]+#2,#,1]]& – alephalpha May 7 '15 at 5:27

## 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;}

• Save a character: j(n,k){return--n?(j(n,k)+k-1)%-~n+1:1;}. – ugoren May 20 '12 at 10:06

## 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)


## 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  ### 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.

• 1- has special opcode (. Similarly 1+ is ). You don't have to use alphabetic characters for storage, so you could use e.g. ^ instead of J and not need a space after it. You have far more $s than are usual in a well-golfed program: consider whether you can reduce them using some combination of \@.. – Peter Taylor May 21 '12 at 7:27 • @PeterTaylor Thanks a lot for these great tips! It's pretty hard to grasp all the Golfscript operators and I overlooked these two very straightforward one. Only by applying the first two suggestions I manage to shorten the code by 5 chars. I'll also try to remove the $ references. – Cristian Lupascu May 21 '12 at 8:23
• Also, recursion isn't really GolfScript's thing. Try flipping it round and doing a loop. I can get it down to 19 chars (albeit untested code) that way. Hint: unroll the function g from the Wikipedia article, and use , and /. – Peter Taylor May 21 '12 at 9:21
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 ### Scala, 53 bytes def?(n:Int,k:Int):Int=if(n<2)1 else(?(n-1,k)+k-1)%n+1  ## 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. ## 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; }  • You could save bytes on the J function, by using the ternary operator. – Yytsi Jun 26 '16 at 9:52 • intn in your golfed version won't compile – Felipe Nardi Batista Oct 24 '17 at 10:56 • you can remove space in #include <list> – Felipe Nardi Batista Oct 24 '17 at 10:56 # J, 8 bytes 1&|.&.#: 1&|.&.#: 10 5 1&|.&.#: 69 11 1&|.&.#: 123456 115841 1&|.&.#: 123245678901234567890x NB. x keeps input integral 98917405212792722853 All credit to Roger Hui, co-inventor of J and all-round uber-genius www.jsoftware.com for free j software across many platforms Explanation (J works right-to-left) #: convert input to binary &. a&.b <=> perform b, perform a, perform reverse of b 1&|. rotate bitwise one bit left So 1&|.&.#: 10 a. #: convert input (10) TO binary -> 1 0 1 0 b. 1&|. rotate result 1 bit left -> 0 1 0 1 c. due to the &. perform convert FROM binary -> 5 (answer)  • Isn't it supposed to take two inputs? – Erik the Outgolfer Sep 28 '17 at 16:45 ### 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 # 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


## Ruby, 34 bytes

J=->n,k{n<2?1:(J(n-1,k)+k-1)%n+1}


Using the formula from wikipedia.

1#_=1
n#k=mod((n-1)#k+k-1)n+1


# 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.

# 05AB1E, 11 bytes

L[Dg#²<FÀ}¦


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


# 8th, 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


# J, 24 bytes

1+1{1([:|/\+)/@,.1|.!.0#


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
|/\                 Cumulative reduce using modulo
1{                      Select value at index 1


# J, 19 bytes

1+(}:@|.^:({:@])i.)


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


# Dart, 33 bytes

f(n,k)=>n<2?1:(f(n-1,k)+k-1)%n+1;


Try it online!

# Japt, 15 bytes

_é1-V Å}h[Uõ] Ì


Try it online!

A byte could be saved by 0-indexing k, 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


# Japt -h, 10 bytes

õ
£=éVn1¹v


Try it

# 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
`