% Options for packages loaded elsewhere
\PassOptionsToPackage{unicode}{hyperref}
\PassOptionsToPackage{hyphens}{url}
%
\documentclass[
]{article}
\usepackage{amsmath,amssymb}
\usepackage{iftex}
\ifPDFTeX
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
  \usepackage{textcomp} % provide euro and other symbols
\else % if luatex or xetex
  \usepackage{unicode-math} % this also loads fontspec
  \defaultfontfeatures{Scale=MatchLowercase}
  \defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1}
\fi
\usepackage{lmodern}
\ifPDFTeX\else
  % xetex/luatex font selection
\fi
% Use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
\IfFileExists{microtype.sty}{% use microtype if available
  \usepackage[]{microtype}
  \UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\makeatletter
\@ifundefined{KOMAClassName}{% if non-KOMA class
  \IfFileExists{parskip.sty}{%
    \usepackage{parskip}
  }{% else
    \setlength{\parindent}{0pt}
    \setlength{\parskip}{6pt plus 2pt minus 1pt}}
}{% if KOMA class
  \KOMAoptions{parskip=half}}
\makeatother
\usepackage{xcolor}
\setlength{\emergencystretch}{3em} % prevent overfull lines
\providecommand{\tightlist}{%
  \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{-\maxdimen} % remove section numbering
\ifLuaTeX
  \usepackage{selnolig}  % disable illegal ligatures
\fi
\IfFileExists{bookmark.sty}{\usepackage{bookmark}}{\usepackage{hyperref}}
\IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available
\urlstyle{same}
\hypersetup{
  pdftitle={Collatz conjecture or 3n+1 Conjecture},
  hidelinks,
  pdfcreator={LaTeX via pandoc}}

\title{Collatz conjecture or 3n+1 Conjecture}
\author{}
\date{}

\begin{document}
\maketitle

\hypertarget{collatz-conjecture-or-3n1-conjecture}{%
\section{Collatz conjecture or 3n+1
Conjecture}\label{collatz-conjecture-or-3n1-conjecture}}

\hypertarget{collatz-conjecture-or-3n1-conjecture-1}{%
\section{Collatz conjecture or 3n+1
Conjecture}\label{collatz-conjecture-or-3n1-conjecture-1}}

Also called Collatz conjecture, Syracuse problem, Ulam conjecture,
Kakutani's problem, Thwaites conjecture, hailstone problem.

\hypertarget{statement}{%
\subsection{Statement}\label{statement}}

Pick any positive integer \texttt{n}. Apply one rule:

\begin{itemize}
\tightlist
\item
  If \texttt{n} even → divide by 2
\item
  If \texttt{n} odd → multiply by 3, add 1
\end{itemize}

Each application produces a new integer. Feeding that integer through
our same rule produces another. Step by step, our starting \texttt{n}
traces a trajectory through natural numbers --- each step carries our
previous value forward into a new one.

Our conjecture claims: every trajectory eventually lands on 1,
regardless of which positive integer you picked.

\hypertarget{example-trajectories}{%
\subsection{Example Trajectories}\label{example-trajectories}}

Starting at 6:

\texttt{6\ →\ 3\ →\ 10\ →\ 5\ →\ 16\ →\ 8\ →\ 4\ →\ 2\ →\ 1}

(8 steps)

Starting at 7:

\texttt{7\ →\ 22\ →\ 11\ →\ 34\ →\ 17\ →\ 52\ →\ 26\ →\ 13\ →\ 40\ →\ 20\ →\ 10\ →\ 5\ →\ 16\ →\ 8\ →\ 4\ →\ 2\ →\ 1}

(16 steps)

Starting at 27 --- famous for wild behavior:

\texttt{27\ →\ 82\ →\ 41\ →\ 124\ →\ 62\ →\ 31\ →\ ...\ →\ 1}

(111 steps, peaks at 9,232 along our way before crashing to 1)

\hypertarget{why-hailstone}{%
\subsection{Why ``Hailstone''}\label{why-hailstone}}

Plot a trajectory. Vertical axis shows value, horizontal axis shows step
count. Values hop up \& down wildly before crashing to 1. Resembles a
hailstone rising inside a storm updraft until gravity wins.

\hypertarget{what-mathematicians-have-verified}{%
\subsection{What Mathematicians Have
Verified}\label{what-mathematicians-have-verified}}

Every positive integer up to 2\^{}68 (approximately 2.95 × 10\^{}20) has
had its trajectory computed on modern hardware. Every single one lands
on 1. No counterexample observed.

\hypertarget{why-no-proof-exists-yet}{%
\subsection{Why No Proof Exists Yet}\label{why-no-proof-exists-yet}}

Our odd-step multiplies by 3 \& adds 1 --- injects growth. Our even-step
halves --- injects shrinkage. Trajectories dance between growing \&
shrinking in ways nobody has yet tamed with formal proof.

Paul Erdős offered \$500 for a proof or disproof \& commented that
mathematics lacks tools strong enough for such problems.

Terence Tao proved a weaker density statement in 2019 --- see next
section for unpacking.

\hypertarget{what-terence-tao-proved-in-2019}{%
\subsection{What Terence Tao Proved in
2019}\label{what-terence-tao-proved-in-2019}}

Tao's result sounds close to our conjecture but stops short of proving
it. Learning why reveals how mathematicians measure partial progress on
a hard problem.

\textbf{His theorem, informal:} for any function \texttt{f(n)} growing
to infinity arbitrarily slowly (think \texttt{log\ log\ log\ n} ---
grows slower than molasses), almost all starting integers \texttt{n}
have a Collatz trajectory that eventually dips below \texttt{f(n)}.

\textbf{What ``almost all'' means here} --- a density-theoretic
statement, not a universal one:

\begin{itemize}
\tightlist
\item
  \textbf{Natural density 1} --- as you scan positive integers up to
  \texttt{N}, a fraction approaching 100\% of them comply. Count how
  many integers ≤ \texttt{N} obey Tao's theorem, divide by \texttt{N},
  take \texttt{N\ →\ ∞}, get 1.
\item
  \textbf{Logarithmic density 1} --- Tao's actual formulation uses a
  weighted density where each \texttt{n} carries weight \texttt{1/n}
  (smaller integers count more). A set can hold logarithmic density 1
  while still missing infinitely many integers.
\end{itemize}

\textbf{Why this leaves our conjecture open:}

\begin{itemize}
\tightlist
\item
  A set of density 0 can still contain infinitely many integers. Tao's
  theorem permits an infinite sparse set of starting integers whose
  trajectories never reach 1 --- as long as that set thins out fast
  enough to carry density 0.
\item
  Tao himself titled his result ``almost all orbits of our Collatz map
  attain almost bounded values.'' Two ``almost''s. Neither one rules out
  a counterexample.
\item
  A real proof of 3n+1 must eliminate \emph{every} potential outlier,
  not just show most integers comply.
\end{itemize}

\textbf{Why Tao's progress still matters:}

Previous results proved weaker density bounds (e.g., natural density
bounded below 1) or restricted which integers could escape. Tao's method
--- borrowed from ergodic theory \& probability --- pushed density all
our way up to 1. Going from ``density 1'' to ``every single integer''
remains our open frontier, \& no one knows how wide that gap actually
runs.

\hypertarget{known-constraints-on-possible-counterexamples}{%
\subsection{Known Constraints on Possible
Counterexamples}\label{known-constraints-on-possible-counterexamples}}

If some starting integer fails to reach 1, its trajectory must do one of
two things:

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\tightlist
\item
  Shoot off toward infinity, growing without bound
\item
  Fall into a cycle of length greater than our known trivial cycle
  \texttt{4\ →\ 2\ →\ 1\ →\ 4\ →\ ...}
\end{enumerate}

Any hypothetical non-trivial cycle must contain at least 186,265,759,595
odd terms. Nobody has ever observed such a cycle.

\hypertarget{why-1-4-2-1-doesnt-break-our-rule}{%
\subsection{Why 1 → 4 → 2 → 1 Doesn't Break Our
Rule}\label{why-1-4-2-1-doesnt-break-our-rule}}

New learners spot an apparent paradox: if ``reaching 1'' ends our
trajectory, why does our rule still produce a value when applied to 1?
Applying 3n+1 to 1 gives \texttt{3\ ×\ 1\ +\ 1\ =\ 4}, then
\texttt{4\ →\ 2\ →\ 1\ →\ 4} forever. Doesn't that contradict ``every
trajectory halts at 1''?

\textbf{Short answer:} our function stays defined on every positive
integer. Our \emph{convention} --- not our \emph{function} --- declares
victory when we hit 1.

Mathematicians call \texttt{4\ →\ 2\ →\ 1\ →\ 4\ →\ ...} our
\textbf{trivial cycle}. Every trajectory that ever reaches 1 enters this
loop \& cycles forever. By convention we stop counting steps at our
first arrival at 1 because our conjecture asks ``does every starting
integer eventually reach 1?'' --- not ``does our function halt?'' Our
function has no halt instruction. Our stopping rule sits outside our
function, imposed by us, not built into our math.

\textbf{What a ``non-trivial cycle'' would mean:}

Imagine integers \texttt{a\ →\ b\ →\ c\ →\ ...\ →\ a} looping among
themselves, never touching 1. A counterexample to 3n+1 could take
exactly this shape --- a set of numbers that all obey 3n+1 yet remain
trapped in their own closed orbit, isolated from 1's orbit.

Example shape (purely hypothetical, none known):

::

\begin{verbatim}
N → (3N+1)/2 → ... → N'' → ... → N
\end{verbatim}

Every single step obeys 3n+1. Every step produces another integer in our
cycle. None of those integers ever equals 1.

\textbf{What computer searches have ruled out:}

Exhaustive computation has verified no such cycle exists with fewer than
roughly 186 billion odd terms along its loop. Our trivial cycle (length
3) remains our only known cycle. But ``ruled out below a huge number'' ≠
``ruled out forever.'' No proof eliminates non-trivial cycles at all
sizes.

\textbf{Putting our two options together:}

If any counterexample to 3n+1 exists, it either (a) escapes to infinity
or (b) lives inside a non-trivial cycle we haven't found. Both remain
mathematically possible; both remain empirically unobserved. Collapsing
this gap from ``unobserved'' to ``impossible'' equals solving Collatz.

\hypertarget{variants}{%
\subsection{Variants}\label{variants}}

\begin{itemize}
\tightlist
\item
  \textbf{5n+1 problem} --- some trajectories appear to escape toward
  infinity. No universal funnel to 1.
\item
  \textbf{3n-1 problem} --- contains multiple cycles, so no universal
  claim holds.
\item
  \textbf{Generalized Collatz maps} --- a family of piecewise-linear
  integer maps with similar unresolved questions.
\end{itemize}

Tiny rule changes produce wildly different landscapes. Only our specific
3n+1 rule (so far) seems to funnel every integer down to 1.

\hypertarget{why-it-matters}{%
\subsection{Why It Matters}\label{why-it-matters}}

Our conjecture crosses number theory, dynamical systems, \&
computational complexity. Jeffrey Lagarias called it ``an
extraordinarily difficult problem, completely out of reach of present
day mathematics.'' Simple rules produce behavior unpredictable from our
rules alone --- a signature of chaotic integer dynamics.

John Conway showed in 1972 that certain Collatz-like generalizations
land in undecidable territory --- no algorithm can answer whether every
trajectory terminates. Whether our plain 3n+1 itself sits in that
undecidable zone remains unknown.

\hypertarget{further-reading}{%
\subsection{Further Reading}\label{further-reading}}

\begin{itemize}
\tightlist
\item
  Lagarias, Jeffrey C. --- \emph{The 3x+1 problem: An overview} (2010)
\item
  Tao, Terence --- \emph{Almost all orbits of the Collatz map attain
  almost bounded values} (2019)
\item
  Conway, John H. --- \emph{Unpredictable Iterations} (1972)
\end{itemize}

\hypertarget{license}{%
\subsection{License}\label{license}}

Public domain. Copy, modify, redistribute freely.

\end{document}
