How Can a Petri Net Unveil the Mystery of the Collatz Conjecture?

The Collatz problem is famous for its deceptively simple rules. Starting from an integer, if it is even you divide it by two; if it is odd you multiply by three and add one. Repeating the process, every number seems to end at 1, yet no one has proved this for all integers.

A research team decided to look at the problem from a different angle: using a Petri net. In a Petri net, “places” represent integers and “transitions” encode the inverse rules of the procedure. Instead of moving forward from a number, the net starts at 1 and rebuilds all possible predecessors.

Building the net up to n = 1000 produced 1,000 places and 667 transitions. Among them, 417 are source nodes (no predecessors), 333 are sink nodes (no successors) and 218 are “orphans”, reachable only via the division‑by‑2 rule. Token flow through the net simulates every path that could lead to 1, revealing a tree‑like structure.

This approach lets us study the conjecture with discrete‑event system theory: recurrence, reachability and liveness become testable properties. Moreover, the modelling opens the door to parametric or inductive extensions that go beyond the finite bound of the net.

In short, the Petri net provides a clear, systematic view of the “reverse journey” toward 1, turning a numeric puzzle into a token‑flow problem.

A Petri net is a graphical model for concurrent systems, composed of places, transitions, and directed arcs. In the Collatz conjecture case, each place corresponds to an integer n ≥ 1, while transitions represent the two inverse rules: from n one can go to 2·n (inverse of the division‑by‑2) and, if n is odd, to (n‑1)/3 (inverse of 3n+1). The net therefore is the inverse of the Collatz graph, with arcs pointing toward predecessors.

The notion of “marking” indicates how many tokens reside in each place. Starting with a marking that places a token in 1, firing transitions generates all possible paths toward larger numbers. The reachability property allows us to check whether a given integer is reachable from 1, i.e., whether a sequence of transitions leads to it in the original graph. Liveness guarantees that, once a token is in a place, at least one transition remains enabled, preventing deadlock.

Recurrence analysis studies whether certain subsets of places are visited infinitely often in non‑terminating executions, providing hints about possible cycles in Collatz sequences. Moreover, the modeling can introduce parameters: for instance, a parametric transition representing n → k·n for any even k, extending the model to generalized versions of the problem.

From a computational standpoint, building the net up to nmax = 1000 requires generating all predecessors of each node, with O(nmax·log nmax) complexity for handling divisions and odd‑even checks. The results reveal a substantial number of “orphan” nodes—places that have only incoming arcs from 2·n transitions but no outgoing (n‑1)/3 arcs—highlighting the intrinsic asymmetry of the process.

Finally, formalizing the problem as a Petri net opens the door to automatic verification techniques such as model checking to prove global properties (e.g., “all tokens reach 1 within a finite number of steps”). This approach could bridge discrete‑event system theory and classical number theory, providing new tools to tackle a decades‑old unsolved problem.