\documentclass[10pt]{article}

\usepackage{fullpage}
\usepackage{setspace}
\usepackage{parskip}
\usepackage{titlesec}
\usepackage[section]{placeins}
\usepackage{xcolor}
\usepackage{breakcites}
\usepackage{lineno}
\usepackage{hyphenat}





\PassOptionsToPackage{hyphens}{url}
\usepackage[colorlinks = true,
            linkcolor = blue,
            urlcolor  = blue,
            citecolor = blue,
            anchorcolor = blue]{hyperref}
\usepackage{etoolbox}
\makeatletter
\patchcmd\@combinedblfloats{\box\@outputbox}{\unvbox\@outputbox}{}{%
  \errmessage{\noexpand\@combinedblfloats could not be patched}%
}%
\makeatother


\usepackage{natbib}




\renewenvironment{abstract}
  {{\bfseries\noindent{\abstractname}\par\nobreak}\footnotesize}
  {\bigskip}

\titlespacing{\section}{0pt}{*3}{*1}
\titlespacing{\subsection}{0pt}{*2}{*0.5}
\titlespacing{\subsubsection}{0pt}{*1.5}{0pt}


\usepackage{authblk}


\usepackage{graphicx}
\usepackage[space]{grffile}
\usepackage{latexsym}
\usepackage{textcomp}
\usepackage{longtable}
\usepackage{tabulary}
\usepackage{booktabs,array,multirow}
\usepackage{amsfonts,amsmath,amssymb}
\providecommand\citet{\cite}
\providecommand\citep{\cite}
\providecommand\citealt{\cite}
% You can conditionalize code for latexml or normal latex using this.
\newif\iflatexml\latexmlfalse
\providecommand{\tightlist}{\setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}%

\AtBeginDocument{\DeclareGraphicsExtensions{.pdf,.PDF,.eps,.EPS,.png,.PNG,.tif,.TIF,.jpg,.JPG,.jpeg,.JPEG}}

\usepackage[utf8]{inputenc}
\usepackage[english]{babel}



\usepackage{float}








\begin{document}

\title{Generating functions for nth Collatz iteration}



\author[1]{Benedict Irwin}%
\affil[1]{University of Cambridge}%


\vspace{-1em}



  
  \date{June 15, 2024}


\begingroup
\let\center\flushleft
\let\endcenter\endflushleft
\maketitle
\endgroup








\sloppy




\section*{Generating Function for $n^{th}$ Collatz Iteration}
We can consider the generating function for the Collatz map applied to the positive integers. Define 
\begin{equation}
C(n) = \begin{cases} n/2 & n \bmod 2 = 0 \\ 3n+1 & n \bmod 2 = 1 \end{cases}
\end{equation}
and define the $m^{th}$ composition of the function as $C_m(n)$, such that $C_0=n$ and $C_1(n)=C(n)$ and $C_2(n)=C(C(n))$.

The generating function for positive integers is 
\begin{equation}
G_0(x) = \frac{x}{(1-x)^2}
\end{equation}
for the first iteration we have numbers $4,1,10,2,16,3,...$ 
\begin{equation}
G_1(x) = \frac{x}{(1-x^2)^2}(4+x+2x^2)
\end{equation}
for the second iteration giving $2,4,5,1,8,10,11,2,14,...$ we have
\begin{equation}
G_2(x) = \frac{x}{(1-x^4)^2}(2+4x+5x^2+x^3+4x^4+2x^5+x^6)
\end{equation}
the next iteration is 
\begin{equation}
G_3(x) = \frac{P_3(x)}{(1-x^8)^2}
\end{equation}
in general this gives 
\begin{equation}
G_n(x) = \frac{P_n(x)}{(1-x^{2^n})^2}
\end{equation}
for a polynomial of which seems to be order $2^{n+1}-1$ these polynomials appear to be related to the current iteration sequence by the following relationship \begin{equation}
P_n(x) = \left(\sum_{k=1}^{2^n} C_n(k)x^k\right) + \left(\sum_{k=2^n+1}^{2^{n+1}-1} (C_n(k)-2 C_n(k-2^n))x^k\right)
\end{equation}
which we can write as 
\begin{equation}
P_n(x) = \left(\sum_{k=1}^{2^{n+1}-1} C_n(k)x^k\right) -2  \left(\sum_{k=2^n+1}^{2^{n+1}-1} C_n(k-2^n)x^k\right)
\end{equation}
We could consider the Cauchy product of this and the simple series \begin{equation}
\frac{1}{(1-x^{2^n})^2} = 1 + 2 x^{2^n} + 3 x^{2\cdot2^n} + 4 x^{3 \cdot 2^n} + \cdots
\end{equation}
what does this mean? This means that for any level of iteration, we can describe the coefficient for any number, however large, using the first few function evaluations and a composition. However the expressions rapidly become complicated, with $2^{n+1}$ terms.

What conditions would then be required for a coefficient to be $1$? For a given iteration this will depend on the number of ways to write a target number $t$, as the sum of an integer in the range $[1,2^n-1]$ and any of $[0,2^n,2\cdot2^n,3\cdot2^n,\cdots]$, for one iteration that's combinations in $[1,2,3]+[0,2,4,6,8,\cdots]$ which can make $[1,2,3]$,$[3,4,5]$,$[5,6,7]$ and so on indicating there are multiple ways to make $3,5,7,\cdots$.

All of the coefficient terms are positive which is nice. The only way a coefficient can be $1$ in this iteration is if it is $1$ in the polynomial, and multiplied by the $1$ in the expanded series.

This means we can look at a subset of the polynomial, namely $P_n(x)$. We can then ask, how can a coefficient become $1$ in $P_n(x)$? We can see that $C_n(k)>2C_n(k-2^n)$ for $k\in[2^n+1,2^{n+1}-1]$ to keep the terms positive and non-zero.

\selectlanguage{english}
\FloatBarrier
\end{document}

