Content is user-generated and unverified.

Josephus problem in Brainfuck

Problem

Read integers N and K. N people stand in a circle numbered 1 to N. Starting from person 1, count K people clockwise and eliminate that person. Repeat until one remains. Output the survivor's number.

Strategy

Instead of simulating the circle (which would need a dynamic array), the program uses the classic O(N) recurrence:

text

J(1, K) = 0                          (0-indexed)
J(n, K) = (J(n−1, K) + K) mod n      for n = 2 … N
answer  = J(N, K) + 1                (convert to 1-indexed)

This reduces the problem to a simple loop with one addition and one modulo per iteration — no need for a linked list or array of alive flags.

Modulo via repeated subtraction

BF has no division or modulo instruction. The program computes a mod b by repeatedly subtracting b from a while a ≥ b.

Each a ≥ b comparison uses the race technique: copy a and b to work cells, decrement both in lockstep until one reaches zero. If the b-copy reaches zero first (or at the same time), a ≥ b holds and the program subtracts b from the real a. Otherwise the modulo is complete.

EOF portability

Every , is preceded by [-]. The digit-detection loop rejects any non-digit byte, so trailing newlines and all three EOF conventions (0, unchanged, 255) are handled correctly.

Memory layout

text

  Cell    Purpose
  ──────  ────────────────────────────
   0      N (parsed from input)
   1      K (parsed from input)
   2      result (recurrence value J)
   3      i (current step, 2 … N)
   4      loop counter (N − 1, counts down)
   5–11   work cells (modulo, comparison)
  20–26   input-parse temps + digit check
  30–39   decimal output (divmod, digits)

Raw code (2217 characters)

brainfuck

>>>>>>>>>>>>>>>>>>>>[-],[>+>+<<-]>>[<<+>>-]<--------------------------
---------------------->++++++++++<[->[>+>+<<-]>>[<<+>>-]+<[<->>-<[-]]>
[<<<[-]>>>-]<<<]>>>>>[-]<<<<[>>>>+<<<<-]<[-]>>>>>[<<<<<<<<<<<<<<<<<<<<
<<<<<<[>>>>>>>>>>>>>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<<-]>>>>>>>>>>>>>>>>>>
>>>[<<<<<<<<<<<<<<<<<<<<<++++++++++>>>>>>>>>>>>>>>>>>>>>-]<[>+>+<<-]>>
[<<+>>-]<------------------------------------------------[<<<<<<<<<<<<
<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>-]<[-],[>+>+<<-]>>[<<+>>-]<------------
------------------------------------>++++++++++<[->[>+>+<<-]>>[<<+>>-]
+<[<->>-<[-]]>[<<<[-]>>>-]<<<]>>>>>[-]<<<<[>>>>+<<<<-]<[-]>>>>>]<<<<<<
[-],[>+>+<<-]>>[<<+>>-]<----------------------------------------------
-->++++++++++<[->[>+>+<<-]>>[<<+>>-]+<[<->>-<[-]]>[<<<[-]>>>-]<<<]>>>>
>[-]<<<<[>>>>+<<<<-]<[-]>>>>>[<<<<<<<<<<<<<<<<<<<<<<<<<[>>>>>>>>>>>>>>
>>>>>>+<<<<<<<<<<<<<<<<<<<<-]>>>>>>>>>>>>>>>>>>>>[<<<<<<<<<<<<<<<<<<<<
++++++++++>>>>>>>>>>>>>>>>>>>>-]<[>+>+<<-]>>[<<+>>-]<-----------------
-------------------------------[<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>
>>>-]<[-],[>+>+<<-]>>[<<+>>-]<----------------------------------------
-------->++++++++++<[->[>+>+<<-]>>[<<+>>-]+<[<->>-<[-]]>[<<<[-]>>>-]<<
<]>>>>>[-]<<<<[>>>>+<<<<-]<[-]>>>>>]<<<<<<<<<<<<<<<<<<<<<<<<<<[>>>>+>+
<<<<<-]>>>>>[<<<<<+>>>>>-]<-<++>[<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]
<[<<<+>>>-]>>>>>[-]+[<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<<<[>>>+>+<<
<<-]>>>>[<<<<+>>>>-]<<[>[>+>+<<-]>>[<<+>>-]+<[<<->->>-<[-]]>[<<<[-]>>>
-]<<<]>>[-]<[>+<[-]]>>[-]+<[>>>-<<-<-]>[<<<<<[>>+>+<<<-]>>>[<<<+>>>-]<
[<<<->>>-]>>>-]<<<[-]>[-]>>>>]<<<<<<<+>-]<<+[>>>>>>>>>>>>>>>>>>>>>>>>>
>>>+<<<<<<<<<<<<<<<<<<<<<<<<<<<<-]>>>>>>>>>>>>>>>>>>>>>>>>>>>>>[-]>[-]
++++++++++<<[->>-[>+>+<<-]>>[<<+>>-]<[>+<[-]]>>+<[>-<-]>[<<<<+>[-]++++
++++++>>>-]<<<<<]++++++++++>>[<<->>-]>>>>>[-]<<<<<[-]++++++++++<[->-[>
+>+<<-]>>[<<+>>-]<[>+<[-]]>>+<[>-<-]>[>>+<<<<<[-]++++++++++>>>-]<<<<]+
+++++++++>[<->-]>>>>>[[>+<-]>+++++++++++++++++++++++++++++++++++++++++
+++++++.[-]>+<<]<<<<<<[>>+>+<<<-]>>>[<<<+>>>-]<[>+<[-]]>>>>>>[<<<<<<+>
>+>>>>-]<<<<[>>>>+<<<<-]<[<+>-]<[>+<[-]]>[<<<[>>>>>>>+<<<<<<<-]>>>>>>>
++++++++++++++++++++++++++++++++++++++++++++++++.[-]>[-]+<<<<<-]<<<<++
++++++++++++++++++++++++++++++++++++++++++++++.

Test results

text

 N   K   Survivor  Status (eof0 / unch / e255)
───  ──  ────────  ────────────────────────────
  5   2  3         OK / OK / OK
  7   3  4         OK / OK / OK
  1   1  1         OK / OK / OK
  6   1  6         OK / OK / OK
 10   2  5         OK / OK / OK
  4   2  1         OK / OK / OK
 13   2  11        OK / OK / OK
 20   3  20        OK / OK / OK
 41   3  31        OK / OK / OK
100   2  73        OK / OK / OK

All cases also verified with trailing newline appended.

Limits

Single-byte cells mean N + K must be ≤ 255 (the intermediate value result + K must not overflow a byte before the modulo reduces it). The output is limited to 0–255, but since the survivor number is at most N, this is not an additional constraint. For the given test cases (N ≤ 100, K ≤ 3) this is well within range.

Content is user-generated and unverified.