Digraphs From a New Josephus Transformation

Overview

The classical Josephus problem involves eliminating individuals in a circle based on a fixed skip number. This research uses a similar rule, allowing skip numbers to vary according to a permutation. This defines a Josephus transformation, creating a mapping among all permutations of length n. We use these transformations to define the directed edges of a digraph (directed graph) where each permutation serves as a vertex. As n increases, the structure of the digraph becomes increasingly complex. To analyze the digraph's structure, we investigate in-degrees and cycles, proving any cycle's length is always a multiple of n. By reformulating reverse transformations as a System of Distinct Representatives (SDR) problem alongside congruence-set methods, we classify vertices, deeply analyze vertices with any fixed in-degree, and uncover significant structural symmetries, parity properties, and quantitative patterns emerging despite the digraph's chaotic nature. Through this investigation, we found that classifying the vertices of in-degree i by their first entry reveals symmetry. The most striking result is discovering a special vertex whose in-degree admits a precise arithmetic characterization rather than a purely combinatorial one. Specifically, its in-degree equals sum of the number of ordered factorizations for integers from 1 to n-1. We conjecture that this vertex attains the maximum in-degree and can be expressed in closed form. This study initiates a new combinatorial dynamical system on permutations, bridging combinatorial dynamics with number theory. We reveal that the Josephus transformation's complex behavior is ultimately governed by elegant arithmetic properties.

Awards (2)

• The Scientific and Technological Research Council of Türkiye TUBITAK: 1st Prize Award
• American Mathematical Society: Honorable Mention and One-Year Membership to AMS (for 5 projects with up to 3 team members per project)

Competition history

• ISEF 2026 Mathematics · Entry MATH009

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.