Josephus problem (counting out)

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

Rɪᴋᴇʀ · Accepted Answer · 2017-04-09 15:03:54Z

5

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;

edited Apr 9 '17 at 15:03

Rɪᴋᴇʀ

6,14043069

answered Jun 2 '12 at 18:41

Peter Taylor

40.3k456144

\$\begingroup\$ Can you add an explanation, please? \$\endgroup\$ – Sherlock9 Nov 26 '15 at 18:49
\$\begingroup\$ @Sherlock9, I managed to figure out what I was doing despite almost 3.5 years having passed. Who says that GolfScript is read-only? ;) \$\endgroup\$ – Peter Taylor Nov 26 '15 at 21:45
\$\begingroup\$ Ahem. s/read/write/ \$\endgroup\$ – Peter Taylor Nov 26 '15 at 22:40
\$\begingroup\$ 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. \$\endgroup\$ – Sherlock9 Nov 27 '15 at 5:30
\$\begingroup\$ @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. \$\endgroup\$ – Peter Taylor Nov 27 '15 at 6:47

| show 1 more comment

Community · Accepted Answer · 2017-04-13 12:39:13Z

14

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: Josephus problem as Minsky register machine

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.

edited Apr 13 '17 at 12:39

Community♦

1

answered May 20 '12 at 21:46

Peter Taylor

40.3k456144

\$\begingroup\$ I think you have to adjust your machine slightly. If I read it correctly the output is zero-indexed, isn't it? \$\endgroup\$ – Howard May 21 '12 at 13:45
\$\begingroup\$ I was thinking the other way: if k=1 then r=0. Hmm, I have to think about this one again... \$\endgroup\$ – Howard May 21 '12 at 14:40
\$\begingroup\$ As I read your diagram, i is simply counting from 2 to n while r is the register which accumulates the result. \$\endgroup\$ – Howard May 21 '12 at 15:39
\$\begingroup\$ @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). \$\endgroup\$ – Peter Taylor May 21 '12 at 16:19

add a comment |

grc · Accepted Answer · 2012-05-20 08:51:48Z

7

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

answered May 20 '12 at 8:51

grc

18.2k93176

add a comment |

Rɪᴋᴇʀ · Accepted Answer · 2017-04-09 15:04:42Z

6

Mathematica, 38 36 bytes

Same Wikipedia formula:

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

edited Apr 9 '17 at 15:04

Rɪᴋᴇʀ

6,14043069

answered May 20 '12 at 10:37

Mr.Wizard

2,4811316

1

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

add a comment |

breadbox · Accepted Answer · 2012-05-20 08:48:08Z

5

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

answered May 20 '12 at 8:48

breadbox

6,7832344

4

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

add a comment |

Rɪᴋᴇʀ · Accepted Answer · 2017-04-09 15:04:13Z

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)

Gareth · Accepted Answer · 2012-05-20 13:41:20Z

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:

Rɪᴋᴇʀ · Accepted Answer · 2017-04-09 15:04:03Z

4

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.

edited Apr 9 '17 at 15:04

Rɪᴋᴇʀ

6,14043069

answered May 20 '12 at 12:36

Cristian Lupascu

8,15922048

1

\$\begingroup\$ 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 \@.. \$\endgroup\$ – Peter Taylor May 21 '12 at 7:27
\$\begingroup\$ @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. \$\endgroup\$ – Cristian Lupascu May 21 '12 at 8:23
1

\$\begingroup\$ 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 /. \$\endgroup\$ – Peter Taylor May 21 '12 at 9:21
1

\$\begingroup\$ {,{\2$+\)%}*)\;}:f; Make sure you understand why it works ;) \$\endgroup\$ – Peter Taylor May 21 '12 at 17:12
1

\$\begingroup\$ One final trick: rather than using 2 characters to access k inside the loop and then 2 more to discard it at the end, we can pull it inside using + to get down to 17 characters: {{@+\)%}+\,*)}:f; I doubt that can be improved. \$\endgroup\$ – Peter Taylor May 21 '12 at 18:13

| show 9 more comments

Paolo · Accepted Answer · 2012-05-21 12:50:27Z

3

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

edited May 21 '12 at 12:50

answered May 21 '12 at 12:43

Paolo

67658

add a comment |

Rɪᴋᴇʀ · Accepted Answer · 2017-04-09 15:05:08Z

3

Groovy, 36 bytes

def j(n,k){n>1?(j(n-1,k)+k-1)%n+1:1}

edited Apr 9 '17 at 15:05

Rɪᴋᴇʀ

6,14043069

answered May 20 '12 at 9:15

Prince John Wesley

669156

add a comment |

ceased to turn counterclockwis · Accepted Answer · 2012-05-21 00:20:22Z

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

Rɪᴋᴇʀ · Accepted Answer · 2017-04-09 15:05:17Z

2

Scala, 53 bytes

def?(n:Int,k:Int):Int=if(n<2)1 else(?(n-1,k)+k-1)%n+1

edited Apr 9 '17 at 15:05

Rɪᴋᴇʀ

6,14043069

answered May 20 '12 at 8:51

Prince John Wesley

669156

add a comment |

ugoren · Accepted Answer · 2012-05-20 10:01:48Z

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.

Michelfrancis Bustillos · Accepted Answer · 2016-04-19 13:23:22Z

1

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

answered Apr 19 '16 at 13:23

Michelfrancis Bustillos

535414

2

\$\begingroup\$ You could save bytes on the J function, by using the ternary operator. \$\endgroup\$ – TuukkaX Jun 26 '16 at 9:52
\$\begingroup\$ intn in your golfed version won't compile \$\endgroup\$ – Felipe Nardi Batista Oct 24 '17 at 10:56
\$\begingroup\$ you can remove space in #include <list> \$\endgroup\$ – Felipe Nardi Batista Oct 24 '17 at 10:56

add a comment |

Arjun · Accepted Answer · 2017-04-03 11:21:13Z

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)

\$\begingroup\$ Isn't it supposed to take two inputs? \$\endgroup\$ – Erik the Outgolfer Sep 28 '17 at 16:45 — Erik the Outgolfer, Sep 28 '17 at 16:45

Rɪᴋᴇʀ · Accepted Answer · 2017-04-09 15:04:29Z

1

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

edited Apr 9 '17 at 15:04

Rɪᴋᴇʀ

6,14043069

answered May 20 '12 at 8:17

Cristian Lupascu

8,15922048

add a comment |

Rɪᴋᴇʀ · Accepted Answer · 2017-04-09 15:04:55Z

1

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

edited Apr 9 '17 at 15:04

Rɪᴋᴇʀ

6,14043069

answered May 28 '12 at 13:22

tmartin

3,8571016

add a comment |

Rɪᴋᴇʀ · Accepted Answer · 2017-04-09 15:05:01Z

1

Ruby, 34 bytes

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

edited Apr 9 '17 at 15:05

Rɪᴋᴇʀ

6,14043069

answered Jun 3 '12 at 9:47

Hauleth

1,2031416

add a comment |

alephalpha · Accepted Answer · 2015-05-07 05:28:49Z

0

Haskell, 29

Using the formula from wikipedia.

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

answered May 7 '15 at 5:28

alephalpha

22.2k33096

add a comment |

Luke · Accepted Answer · 2017-01-22 11:35:29Z

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.

Riley · Accepted Answer · 2017-07-27 20:30:40Z

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

Chaos Manor · Accepted Answer · 2017-09-18 08:14:00Z

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

miles · Accepted Answer · 2017-09-18 09:14:54Z

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

Bubbler · Accepted Answer · 2018-12-06 07:25:55Z

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

Elcan · Accepted Answer · 2018-12-06 08:22:28Z

0

Dart, 33 bytes

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

Try it online!

answered Dec 6 '18 at 8:22

Elcan

35616

add a comment |

Kamil Drakari · Accepted Answer · 2018-12-06 21:42:11Z

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

Shaggy · Accepted Answer · 2018-12-10 16:52:40Z

0

Japt `-h`, 10 bytes

õ
£=éVn1¹v

Try it

answered Dec 10 '18 at 16:52

Shaggy

19.2k21768

add a comment |

mazzy · Accepted Answer · 2018-12-10 16:58:34Z

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

asked	6 years, 11 months ago
viewed	2,940 times
active	4 months ago

Josephus problem (counting out)

The challenge

The problem

Examples

28 Answers 28

GolfScript, 17 bytes

Dissection

Minsky Register Machine (25 non-halt states)

Python, 36

Mathematica, 38 36 bytes

C, 40 chars

dc, 27 bytes

J, 45 characters

GolfScript, 32 24 bytes

R, 48

Groovy, 36 bytes

Haskell, 68

Scala, 53 bytes

C, 88 chars

C++, 166 bytes

Golfed:

Ungolfed:

J, 8 bytes

Ruby, 39 bytes

Q, 34 bytes

Ruby, 34 bytes

Haskell, 29

JavaScript (ECMAScript 5), 48 bytes

ES6 version (non-competing), 33 bytes

Explanation

05AB1E, 11 bytes

8th, 82 bytes

J, 24 bytes

Explanation

J, 19 bytes

How it works

Dart, 33 bytes

Japt, 15 bytes

Japt -h, 10 bytes

Powershell, 56 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golf math sequence or ask your own question.

Linked

Related

Hot Network Questions

Japt `-h`, 10 bytes