Yamagishi Complexity Torus LabYamagishi Lab

[Paper 614] In a Circle Where Every Second Person Leaves, the Last Seat Is the Head Count with Its Leading Binary 1 Moved to the End

Abstract

$n$ people sit in a circle in the order $1$ to $n$; counting from seat $1$, every $k$-th person leaves the circle. Which seat is left last (the Josephus problem)? For every second ($k=2$) and every third ($k=3$) person, the result of actually running the circle is matched with the formula. No new theorem or law is claimed.

First, removing every second person, the last seat is a binary rotation: writing $n$ in binary and moving its leading $1$ to the end gives the last seat. For every $n$ from $1$ to $1024$ this agreed with running the circle. For $41$ people $101001$ becomes $10011$, seat $19$; for $100$ people, seat $73$; for $1000$, seat $977$ (Section 2).

Second, removing every second person, the last seat is always odd: the rotated number always ends in $1$, and all $1024$ cases were odd. When the head count is a power of $2$, the rotation returns $1$ and seat $1$ remains (Section 2).

Third, and this is the core. The circle that removes every second person is a binary operation that halves the head count each round: with $n=2^m+L$, once $L$ people have left, $2^m$ remain, and the seat where counting resumes, $2L+1$, is the one left last, because in a circle of $2^m$ each round removes half and the starting seat keeps surviving (Section 3).

Fourth, the separator is how many are skipped: removing every third person ($k=3$) there is no short form like the binary rotation, and the answer comes from a recurrence that removes one person at a time or from a closed formula using a constant. For every $n$ from $1$ to $1000$ the circle and the recurrence agreed, and for $41$ people the last two were seats $16$ and $31$. The last seat was even for $500$ of the $1000$ head counts, so the odd bias disappears (Section 4).

Keywords: Josephus problem, binary representation, recurrence relation, elimination circle, recursion.

Scope (what is not claimed)

No new theorem or law is claimed: the binary formula for removing every second person and the recurrence for general $k$ are known (found, for example, in the book by Graham, Knuth and Patashnik and in Ball and Coxeter). Asymptotic formulas for general $k$ are not treated: only $k=2$ and $k=3$ are counted. The historical legend is not discussed: the pair of $41$ people and $k=3$ is used only as an example to check numbers. Relation to earlier papers: Paper 602 decided who wins at Nim by addition without carries, and Paper 608 counted the odd numbers in Pascal’s triangle by the ones in a binary numeral. Here too binary digits decide the answer, appearing as a different operation: moving the leading $1$ to the end. What is added is matching the circle with the formula up to $1024$ people, explaining why the rotation holds at the moment the count falls to $2^m$, and placing the separator on how many are skipped, showing in numbers that for $k=3$ there is no such short form and the parity bias disappears.

1. Notation and the Question

Setting: $n$ people form a circle in the order $1$ to $n$. Counting from seat $1$, the $k$-th person leaves, and counting restarts from the next person, until one remains. Write $J_k(n)$ for the last seat.

Question: is there a formula for $J_2(n)$, why does it take that form, and what changes for $k=3$?

2. Every Second Person

Computation 2.1: for $n=1$ to $1024$, the circle was actually run, removing one person at a time, and the last seat was found. Compared with $n$ in binary with its leading $1$ moved to the end, every case agreed.

people $n$binarylast seatlast seat in binary
$5$$101$$3$$11$
$6$$110$$5$$101$
$7$$111$$7$$111$
$8$$1000$$1$$1$
$41$$101001$$19$$10011$
$100$$1100100$$73$$1001001$
$1000$$1111101000$$977$$1111010001$
$1024$$10000000000$$1$$1$

Observation 2.2 removing every second person, the last seat is always odd. Moving the leading $1$ to the end makes the last digit always $1$; all $1024$ cases were odd: people in even seats always leave in the first round.

Observation 2.3 if the head count is a power of $2$, seat $1$ remains. $2^m$ in binary is a $1$ followed by $0$s, so moving the leading $1$ to the end gives $1$: for all $11$ powers of $2$ from $1$ to $1024$, seat $1$ remained.

3. Why a Rotation

Observation 3.1 this is the core: the circle removing every second person is a binary operation that halves the head count each round. In a circle of $2^m$, one round removes the even seats, leaving $2^{m-1}$, and the next round again starts from seat $1$; repeating, seat $1$ is left last: with $n=2^m+L$ ($0\le L<2^m$), once the $L$ people in seats $2,4,\dots,2L$ have left, $2^m$ remain, and counting resumes at seat $2L+1$. From then on it is a circle of $2^m$, so $J_2(n)=2L+1$.

Observation 3.2 $2L+1$ is “the number with its leading $1$ moved to the end”. $n=2^m+L$ in binary is a leading $1$ followed by the $m$ digits of $L$. Removing the leading $1$ leaves $L$; shifting it one place left and putting a $1$ at the end gives $2L+1$: for $41=32+9$, $2\times9+1=19$, matching the rotation of $101001$ into $10011$.

4. The Separator

Computation 4.1: for every third person ($k=3$), running the circle for $n=1$ to $1000$ and the recurrence removing one person at a time, $J_3(n)=((J_3(n-1)-1+3)\bmod n)+1$, agreed in every case.

people $n$last seat ($k=3$)
$5$$4$
$6$$1$
$7$$4$
$8$$7$
$41$$31$
$100$$91$
$1000$$604$

For $41$ people and $k=3$ the last two are seats $16$ and $31$, the seats that legend says Josephus and his friend took.

Observation 4.2 the separator is how many are skipped. With $k=2$ each round halves the head count, and the binary digits are the answer directly. With $k=3$ a round removes a third, but there is no short form like a base-$3$ rotation; the answer comes from the recurrence removing one person at a time or from a closed formula using a constant: the last seat was even for $500$ of the $1000$ head counts with $k=3$, and the bias “always odd” of $k=2$ disappears.

Note added in the 2nd edition: $k=3$ does have a closed formula. The formula of Halbeisen and Hungerbühler (1997) uses a constant $\alpha\approx0.8111$ and fixes the seat from the largest $m$ with $R=\mathrm{round}(\alpha(3/2)^{m})$ not above $n$. Checked here: the head counts where the seat wraps are $31$, $47$, $70$, with ratio approaching $3/2$; between them the seat rises by $3$; and “$3(n-R)$ plus the seat after the wrap” agreed for every $n$ from $5$ to $2000000$. What does not exist is a short form like the binary rotation.

Observation 4.3 beside Papers 602 and 608. Paper 602 decided Nim by addition without carries, and Paper 608 counted the odd numbers of Pascal’s triangle by binary ones. Here too binary digits decide the answer, but now neither as an addition nor as a count, but as a rearrangement: moving the leading $1$ to the end.

Observation 4.4 what is not said. Asymptotic formulas for general $k$ are not treated, nor is the historical legend. What is shown is the matching of the $k=2$ formula and the $k=3$ recurrence with the running circle, and that the form of the answer changes with how many are skipped.

5. Roll Call and Closing

  1. the last seat for every second person is a binary rotation (Computation 2.1): agreeing up to $1024$ people.
  2. seat $19$ for $41$ people, $977$ for $1000$ (Computation 2.1): $101001$ to $10011$.
  3. the last seat is always odd (Observation 2.2): even seats leave in the first round.
  4. seat $1$ for powers of $2$ (Observation 2.3): all $11$ of them.
  5. each round halves the head count (Observation 3.1): the core.
  6. after $L$ leave, $2^m$ remain and counting resumes at $2L+1$ (Observation 3.1): that seat remains.
  7. $2L+1$ is the leading $1$ moved to the end (Observation 3.2): $41=32+9$ gives $19$.
  8. every third person: recurrence agrees up to $1000$ (Computation 4.1): seat $604$ for $1000$.
  9. $41$ people, $k=3$: the last two are seats $16$ and $31$ (Computation 4.1): the seats of the legend.
  10. for $k=3$, even last seats are $500/1000$ (Observation 4.2): the separator is how many are skipped.

Closing: Removing every second person from a circle of $n$, the last seat is $n$ written in binary with its leading $1$ moved to the end. Up to $1024$ people this agreed with actually running the circle: seat $19$ for $41$ people, $977$ for $1000$; the last seat is always odd, and seat $1$ when the head count is a power of $2$. The circle removing every second person is a binary operation that halves the head count each round: with $n=2^m+L$, once $L$ have left, $2^m$ remain, and seat $2L+1$, where counting resumes, stays to the end. The separator is how many are skipped: removing every third person there is no such short form, and the recurrence agreed up to $1000$ people; the parity bias disappears too, with $500$ of $1000$ last seats even. Placed among the earlier papers: as in Papers 602 and 608 binary digits decide the answer, here appearing as a rearrangement. To be honest: neither asymptotic formulas for general $k$ nor the historical legend are entered; only $k=2$ and $3$ were counted.

Revision Record

2nd Edition (October 2026): The statements of the 1st edition that removing every third person has no formula and that the answer comes only from a recurrence went too far. A closed formula of Halbeisen and Hungerbühler (1997) exists (according to the section on it in the English Wikipedia article Josephus problem; the original paper was not read), and it was checked here for $n=5$ to $2000000$. The subtitle, the fourth item of the abstract, the scope note, Observation 4.2 and the closing now say that there is no short form like the binary rotation, and a note was added to Section 4. The tables do not change.

3rd Edition (October 2026): The dashes used as separators in the text were replaced by punctuation, and the subtitle was shortened. No claim, number or reference was changed.

References

  1. Ball, W. W. R., & Coxeter, H. S. M. (1987). Mathematical Recreations and Essays (13th ed.). Dover Publications.
  2. Graham, R. L., Knuth, D. E., & Patashnik, O. (1994). Concrete Mathematics: A Foundation for Computer Science (2nd ed.). Addison-Wesley.
  3. Yamagishi, Y. (2026). Who Wins at Nim Is Decided by Addition Without Carries [Paper 602]. Zenodo. 10.5281/zenodo.22805951
  4. Yamagishi, Y. (2026). The Odd Numbers in Pascal’s Triangle Are Counted by the Ones in the Row Number Written in Binary [Paper 608]. Zenodo. 10.5281/zenodo.23014462

Reference

Yamagishi, Y. (2026). In a Circle Where Every Second Person Leaves, the Last Seat Is the Head Count with Its Leading Binary 1 Moved to the End [Paper 614]. YOI: https://www.yamagishiyuuki.com/yoi/614
DOI: 10.5281/zenodo.23014482
ORCID: 0009-0006-8587-3450

PDF (English) · PDF (Japanese) · Date proof of the English PDF (OpenTimestamps .ots) · SHA256SUMS

The record page for this paper (in Japanese, with the PDFs in each language and the date proof): YOI 614. This paper is a preprint and has not been peer reviewed.