2^a*3^b*n+c -- The general form of the arithmetic expressions which denote the set memberships of the fully anchored subsets in the abstract predecessor tree, used when the powers of 2 and 3 seem relevant.
3n+1 problem -- Mathematicians prefer the
name "3x+1" or "Collatz 3x+1" problem. Proving this unproved conjecture is
the subject of these pages.
8n+5 -- The
formula representing the infinite set of integers obtained by taking n
as 0, 1, 2, 3, ... , or,
equivalently 5[8], all the integers congruent to 5 mod 8.
abstract tree -- In this
work, a binary tree whose nodes contain infinite sets of
integers. The abstract tree contains the whole set of extensions
({8n+5} or 5[8] integers) as its root and follows the partitioning
of the integers as it develops all possible left descents (in the binary
tree) by separating the s-descendant subset, the
b-descendant subset, and the leaf subset at every level of its
development.
b-descendant -- The kind of
descendant in a left descent in the binary predecessor tree bigger
than its parent, or the set at a level in the abstract predecessor
tree containing all those descendants bigger than their immediate
parents. These children arise when the parent (set) is
congruent to 1 mod 3, i.e. in 1[3].
b-step -- The steps in an l.d.a. are labeled b steps
when they connect a parent to a b-descendant, allowing the
letter b to be used as an element in the
e{s|b}t notation for l.d.a.s.
.
binary tree -- A tree in which
a parent may bear only zero, one, or two children, and
the left child is distinguished from the right child. In this
work, the binary tree is a predecessor tree rooted at one in which
a series of left children constitute a "left descent", a node with
no left child is called a "leaf node", and right children are
called "extensions". Every node in the tree has a right child.
conjecture -- Any mathematical proposition
believed to be true but which has not been rigorously shown to be
true. The conjecture studied in these pages is that the Collatz
3n+1 trajectory leads to 1 from any positive integer.
descendant rules -- The rules
which specify the calculation of the next level in the predecessor trees
from the parental value. Effectively, they provide the
inverse of the Collatz process by calculating an odd integer
(Collatz) predecessor from an odd integer (Collatz)
successor, thus facilitating predecessor tree construction.
disjoint graphs -- Two graphs are
disjoint if the union of their nodes is null. One possibility for
failure of the Collatz conjecture is that there is a separate,
disjoint predecessor tree from that headed by 1.
dn+c -- The general form of
the arithmetic expressions which denote the set memberships in the
abstract predecessor tree, usually used when the powers of 2 and 3
are not particularly relevant and/or before subsetting is completed so
that the subsets are not yet unique to a particular left descent.
Equivalently referred to c[d].
e -- The symbol used to denote the
extension (header) of a left descent in the string which characterizes each
one.
e(sb)t notation -- An
alphabetic string descriptive of a fully anchored left descent. It
starts with e to denote an extension as the header,
ends with t to denote termination in a leaf node,
and contains from zero to many s's and b's indicating in
order the sequence of steps from top to bottom (extension to leaf)
in the left descent.
extension -- A synonym for a
right descendant in the binary predecessor tree, so named because
every element in a right descent produces the odd Collatz successor
identical with that produced by the node which heads the right
descent. An extension heads every left descent. An alternative term,
"proxy", might have better served to connote the way extensions produce the same result
as their header element.
extended hexadecimal Collatz
trajectories can sometimes contain a greater number of successive
divisions by 2 than can be represented by the decimal digits 1 through
9. To provide a single digit representation for these cases, the
familiar hexadecimal system of computer science is extended as follows,
'123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz', to
provide digit values from 1 through 61.
Fibonacci series -- The
recursively defined series in which F(0)=0 and F(1)=1 and
F(n)=F(n-2)+F(n-1) for n>=2. This series (and its multiples
by 2^i, i>=1) is observed in the cardinalities of
occurrences of formulas sharing a common {a,b} pair for a given
value of a (see entry for formula).
finite sum -- A summation performed over
a finite number of terms. In this work, finite sums were calculated
to confirm the convergence of infinite sums and measure the coverage of
the integers by the predecessor tree.
formula -- Used in these pages to denote an
algebraic expression of the form dn+c or
2^a*3^b*n+c which characterizes a composite
set or a unique subset in the abstract predecessor tree.
general tree -- A tree in
which a node may bear any number (zero or more) of
children. In this work, the general form of the predecessor
tree shows the smallest child and all its extensions as the infinite set
of children of each parental node.
generation tree -- A tree depicting the
effects of some directed transition whose results are shown as parents
and whose sources are shown as children. In this context,
the generation trees are usually called
predecessor trees (which see, below) (all three
forms).
infinite sum -- A summation performed
over an infinite number of terms. In this work, the infinite
summations of the densities of integers in various disjoint
subsets converge to finite values which measure
various aspects of the coverage of the integers by the predecessor tree.
instance, instantiation --
A reference to a particular application of a left descent assembly
(perhaps used as a sieving element) in which a particular value of
n is used across the formulas of all the elements of the left
descent. (The two words are used almost interchangeably
here.)
l.d.a. -- Abbreviation for left
descent assembly; see definition herein below.
leaf node -- A node in a tree
which bears no children. In this work, predecessor tree nodes
are leaf nodes when they contain integers which are multiples of 3
(i.e., in the abstract tree, a set of integers congruent to
0 mod 3).
left descent -- The sequence
of nodes, every one a left child in the binary tree view of the
predecessor tree, appearing below a header extension node
{5[8]},
created by use of either 1 or 2 as the value of p(k) in the
descendant rules, and terminating in a leaf node {0[3]}. See also
some context. See also the
definition of "sequence vector" later in this glossary.
left descent assembly -- The
recurring structural unit, consisting of a left descent including
both its header extension and its terminating leaf node, whose
infinite instantiations provide a certain fraction of the odd integers
present in the predecessor tree. (This is often abbreviated as
l.d.a.) L.d.a.s are a restricted subset of sequence vectors.
(Occasionally, "assemblage" slips out in place of "assembly").
Maple V -- The Symbolic Algebra software without which this
work could not conceivably have ever left the ground.
mod -- The arithmetic operator whose result is
the remainder of an integer division. For example, 5 mod 3
is 2, and 55 mod 24 is 7. Equivalently, 5[3]=2 and 55[24]=7.
node -- In this work, a node is a
vertex in a tree. The general and the binary predecessor tree
nodes contain odd integer values, but the abstract tree nodes
contain sets of odd integers. (More generally, a node is a vertex
in any graph and may contain any sort of value.)
o -- A variable denoting the integer
whose placement in the abstract predecessor tree is the object of
any particular execution of the placement algorithm.
Pascal triangle -- A presentation of the
successive sets of the binomial coefficients in the form of a
triangle. Since the abstract predecessor tree traces out the
various combination of s and b steps, the number of
ways to reach paths with c s's and d b's in
it is given by C(c,d), equal to the binomial
coefficient. This pictorial representation enables a quick
visualization of the reason the Fibonacci series describes the number of
ways to reach any particular power-of-2 depth in left descents.
predecessor tree -- A predecessor tree
gives the result of an operation as a parent and the source(s) as the
child(ren). In our case, the Collatz successor appears as a
parent, and the predecessor(s) appear(s) as child(ren) in the tree.
Any Collatz trajectory can be followed as a path from deep in the general
predecessor tree upwards to its final destination at 1.
recursion -- A repetitive process in which calculation of each new
value in a series uses values appearing earlier in the series.
Both calculation of successive
extensions and successive elements of the Collatz trajectory are recursive processes.
The Fibonacci series is a classical example of recursion.
right descent -- The
infinite sequence of nodes, appearing as right children below
every node in the binary tree, and each having a value determined
recursively from its parent, n, as
4*n+1.
root -- The distinguished node in a graphical
structure known as a tree which is parental to the entire graphical
structure. In the Collatz 3n+1 problem, the value in the root
node is 1.
s-descendant -- The kind of
descendant in a left descent in the binary predecessor tree
smaller than its parent, or the set at some level in the
abstract predecessor tree containing all those descendants smaller than
their immediate parents. These children arise when the parent
(set) is congruent to 2 mod 3.
sequence vector -- A more general
notation
for representing a trajectory in a Collatz iteration inclusive of paths
which include arbitrary numbers of steps which involve arbitrary numbers
of division by 2 at each step. I quote liberally from email from
Mensanator (May 10, 2006) whose definition is more complete and precise
than any I would have produced.
"A 'sequence vector' must start with an odd number and end with at
least one iteration of n/2 (to reach a terminating odd number).
The data structure is simply a list of integers such as [1,2]. It is
implied from the definition that there is a (3n+1) to the left of each
integer in the list, each integer represents the count of consecutive
n/2 iterations. Thus [1,2] defines the sequence
Crudely put, a sequence vector is an l.d.a. gone wild; it is not
constrained to start at an integer in {5[8]}, nor to end in an integer
in {0[3]}, nor limited to only one or two divisions by 2. (These 3
criteria do apply to l.d.a.s.)
s-step -- The steps in an l.d.a. are labeled s steps
when they connect a parent to an s-descendant, allowing the
letter s to be used as an element in the e{s|b}t notation for
l.d.a.s.
sieve -- A process by which a set
(here, the odd integers) may be repeatedly scanned to mark
those satisfying a certain property (here, inclusion in one of the
infinite instantiations of a left descent assembly) and identify
new scanning elements (here a new left descent assembly) for use
in repetition of the process. Compare the Sieve of
Eratosthenes, which scans for composites to identify primes and
eventually assigns all integers as either prime or composite.
state transition diagram -- A directed
graph which shows states of a system as its nodes and the transitions which may
occur between them as its edges. The state of a system is given by the
values of some characteristic variable(s) of the system. State changes are indicated by
arrows indicating allowed transitions, with an annotation on each arrow
indicating the circumstance under which the particular transition
occurs. The state transition diagram offers a compact and understandable
overview of potential system dynamics.
t -- The symbol used in the string
characterizing each kind of left descent to denote that the left descent
has been terminated in a leaf node. Note that the t does NOT
correspond to an element in the descent (unlike the e, s,
and b characters which DO correspond to elements in the descent).
trajectory -- The sequence of
integers visited by successive Collatz steps from some starting integer
(presumably) on the way to 1. We limit our discussion to the
odd integers.
(3n+1) (n/2) (3n+1) (n/2) (n/2)
". Thank you, Mensanator.
My Collatz Home Page