GENERATING FUNCTION FOR nth COLLATZ ITERATION We can consider the generating function for the Collatz map applied to the positive integers. Define C(n) = n/2 & n \bmod 2 = 0 \\ 3n+1 & n \bmod 2 = 1 and define the mth composition of the function as Cm(n), such that C₀ = n and C₁(n)=C(n) and C₂(n)=C(C(n)). The generating function for positive integers is G_0(x) = {(1-x)^2} for the first iteration we have numbers 4, 1, 10, 2, 16, 3, ... G_1(x) = {(1-x^2)^2}(4+x+2x^2) for the second iteration giving 2, 4, 5, 1, 8, 10, 11, 2, 14, ... we have G_2(x) = {(1-x^4)^2}(2+4x+5x^2+x^3+4x^4+2x^5+x^6) the next iteration is G_3(x) = {(1-x^8)^2} in general this gives G_n(x) = {(1-x^{2^n})^2} for a polynomial of which seems to be order 2n + 1 − 1 these polynomials appear to be related to the current iteration sequence by the following relationship P_n(x) = \left(^{2^n} C_n(k)x^k\right) + \left(^{2^{n+1}-1} (C_n(k)-2 C_n(k-2^n))x^k\right) which we can write as P_n(x) = \left(^{2^{n+1}-1} C_n(k)x^k\right) -2 \left(^{2^{n+1}-1} C_n(k-2^n)x^k\right) We could consider the Cauchy product of this and the simple series {(1-x^{2^n})^2} = 1 + 2 x^{2^n} + 3 x^{2\cdot2^n} + 4 x^{3 \cdot 2^n} + \cdots 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 2n + 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, 2n − 1] and any of [0, 2n, 2 ⋅ 2n, 3 ⋅ 2n, ⋯], for one iteration that’s combinations in [1, 2, 3]+[0, 2, 4, 6, 8, ⋯] 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, ⋯. 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 Pn(x). We can then ask, how can a coefficient become 1 in Pn(x)? We can see that Cn(k)>2Cn(k − 2n) for k ∈ [2n + 1, 2n + 1 − 1] to keep the terms positive and non-zero.