×

On Collatz words, sequences, and trees. (English) Zbl 1310.11033

Summary: Motivated by recent work of M. Trümper [Chin. J. Math. (New York) 2014, Article ID 756917, 21 p. (2014; Zbl 1303.11037)], we consider the general Collatz word (up-down pattern) and the sequences following this pattern. We derive recurrences for the first and last sequence entries from repeated application of the general solution of a binary linear inhomogeneous Diophantine equation. We solve these recurrences and also discuss the Collatz tree.

MSC:

11B83 Special sequences and polynomials
11B37 Recurrences
11D04 Linear Diophantine equations

Citations:

Zbl 1303.11037

Software:

OEIS
PDFBibTeX XMLCite
Full Text: arXiv EMIS

Online Encyclopedia of Integer Sequences:

a(n) is the number of integers m which take n steps to reach 1 in ’3x+1’ problem.
a(n) = (2^(2*n + 1) + 1)/3.
Triangle read by rows: T(0,0)=1, T(n,m) = binomial(n,m) * gcd(n,m)/n.
Triangle in which row n is a sorted list of all numbers having total stopping time n in the Collatz (or 3x+1) iteration.
The number of odd numbers that require n Collatz (3x+1) iterations to reach 1.
Smallest positive integer solution x of 9*x - 2^n*y = 1.
a(n) = 32*n - 27 for n >= 1. Second column of triangle A238475.
a(n) = 128*n - 107 for n >= 1. Third column of triangle A238475.
a(n) = 64*n - 11 for n >= 1. Third column of triangle A238476.
Smallest positive integer solution x of (3^3)*x - 2^n*y = 1 for n >= 0.
Rectangular array showing the starting values M(n, k), k >= 1, for the Collatz operation (ud)^n, n >= 1, ending in an odd number, read by antidiagonals.
Rectangular companion array to M(n,k), given in A239126, showing the end numbers N(n, k), k >= 1, for the Collatz operation (ud)^n, n >= 1, ending in an odd number, read by antidiagonals.
a(n) = 32*n - 1, n >= 1. Fourth column of triangle A239126, related to the Collatz problem.
a(n) = 18*n - 1, n >= 1, the second column of triangle A239127 related to the Collatz problem.
Smallest positive integer solution x = a(n) of (3^4)*x - 2^n*y = 1 for n >= 0.
Rectangular array giving all start values M(n, k), k >= 1, for Collatz sequences following the pattern (udd)^(n-1) ud, n >= 1, read by antidiagonals.
Rectangular companion array to M(n,k), given in A240222, showing the end numbers N(n, k), k >= 1, for the Collatz operation (udd)^(n-1) ud, n >= 1, read by antidiagonals.