Collatz meets Fibonacci

The MAA Mathematics Magazine, Volume 95, 2022 - Issue 2, p. 130-136

Michael, Bjarki and Henning

The Collatz map is defined for a positive even integer as half that integer, and for a positive odd integer as that integer threefold, plus one. The Collatz conjecture states that when the map is iterated the number one is eventually reached. We study permutations that arise as sequences from this iteration. We show that permutations of this type of length up to 14 are enumerated by the Fibonacci numbers. Beyond that excess permutations appear. We will explain the appearance of these excess permutations and give an upper bound on the exact enumeration.

Download the paper

• The MAA Mathematics Magazine, Volume 95, 2022 - Issue 2, p. 130-136
• arXiv

Presentations

• Umraðanir í Collatz-ferlinu, Conference of the Icelandic Mathematics Society, October 2013 (Bjarki presented)

• Permutations arising from the Collatz process and automatic discovery of patterns, MIT Combinatorics Seminar, October 2013 (Henning presented)

• Collatz meets Fibonacci, abstract / poster, Permutation Patterns, July 2014 (Michael presented)

Later work (last updated 3 October 2026)

• Project Euler problem 494: Collatz prefix families (2014). A programming challenge that asks for the number of the permutations studied here of length 90; its given values, 5, 55 and 6771 for lengths 5, 10 and 20, show the Fibonacci numbers and then the excess explained here.
• M. B. Nathanson, Permutation patterns of the iterated Syracuse function, Integers 24A (2024). A similar question for the Syracuse function, the Collatz map on odd numbers: which permutation patterns its iterates have, and with what densities.
• All citing papers on Google Scholar (10)