Mathematicians who refer to the problem as the *3x+1* problem
were never brainwashed by FORTRAN (as I was) into the belief that
*n*, not *x*, stands for an integer.

This work has been ongoing for several years, and fragments of earlier approaches appear on these pages. An attempt has been made to label these fragments, and they are referenced among the later entries of the table of contents, below.

Currently, I've obtained a detailed mapping of the residue sets which constitute the abstract Collatz predecessor tree. Systematic features of this structure permit development of formulas whose infinite summation indicates the presence of all the odd positive integers therein. The recursive program which develops details of this structure starting from the root node {5[8]} is effectively an inductive/constructive proof of the Collatz conjecture. An image of a paper representing this approach to a proof is available.

I hope someone who can formalize mathematical proofs will see the potential here and take the appropriate set of ideas and sketch or complete a formal proof of the conjecture using them.

You may communicate with me by e-mail at *kconrow@ksu.edu*. Reports
of errors and constructive comments will be particularly welcome.

3*n*+1 Problem Statement and References

3*n*+1 Predecessor Tree, Three Views

The notion of a predecessor tree and details of the general,
binary, and abstract versions of the predecessor tree are presented.

Glossary of Terms Used

Hand-made examples show the method of developing successive predecessor sets during elaboration of the abstract predecessor tree.

A brief guide to Maple programs which support the abstract predecessor tree gestalt.

The following items are repeated therein with a little more description.

Program Treegrow -- Tracing the Left Descent Assemblies in the Abstract Tree

Program Rsetprog -- Construction of the Abstract Predecessor Tree

Program Nbigpath -- Generating the General Predecessor Tree

Excepting time and space imitations,

Algorithm Idit -- Locating an Arbitrary Integer in the Abstract Predecessor Tree

An algorithm is presented for identifying the l.d.a. which contains an arbitrary odd integer

Program IDtheLDA -- Characterization of the l.d.a. for an Arbitrary Integer

Program Fullmap -- Mapping the trajectory from any Arbitrary Odd Integer to 1:

Less ambitious than nbigpath, two programs work together to accept a specification of an arbitrary left descent assembly and produce, then plot, the Collatz trajectory embodying the requested path.

Some of the Plots of "Designer" Paths are "Works of Art"

Though not useful in pursuit of a proof, there is clearly an open field here for producing computer art.

What insights/viewpoints distinguish this work from others?

Brief Overview of Logical Connections in this Web Site and Proof

Proof Develops from the Abstract Predecessor Tree Properties

A relatively brief overview is given of the proof to be presented in these pages.

Comparison of Binary Tree Requirements with the Graph-Forming Capabilities of L.d.a.s for the (3

It is argued from a table of properties that the individual nodes within the binary predecessor tree are incapable of forming any graph other than a binary tree.

Argument via Construction of a Binary Tree

The individual nodes in the binary predecessor tree have properties which can produce only a binary tree.

Concise Statement of Arguments Leading to a Proof.

This repeats four major components of the previous 10 pages selected because they seem most cogent to a proof of the Collatz conjecture. Readers who already know nearly everything are advised to start here.

Set Densities From Finite Left Descent Assembly Element Sets

The proposition that the sets being summed in the cardinality table represent sums determined from densities measured in finite sets is explored thoroughly.

Behavior of Powers of 2 and 3 in (2

This gives a numeric argument for the directed nature of the Collatz graph.

Mapping the Odd Integers>1, the Trees, and the List of Left Descent Assemblies Into One Another

Only mapping the members of a set of left descent assemblies from the abstract predecessor tree into their respective positions in the binary predecessor tree is lacking.

Two Paradoxes Encountered

One paradox notes different estimates of the odd/even ratio of the integers in the Collatz predecessor tree. The other notes that left descent assemblies should lead to higher numbers on average, contrary to fact. Actually, neither is a paradox; both are explained in detail.

Metrics of Infinity

Can it be that using densities as a metric and recognizing that the Collatz itineraries involve only integers avoids many traps otherwise encountered when considering infinite sets?

Approaches to Dealing with the Infinity Problem in the 3n+1 Conjecture

Here's a listing of various approaches to solving the infinity problem with references to other sections of this work and some discussion.

Several Arguments Toward a Proof

Several arguments are presented side by side for easy comparison.

Why an Arithmetic Argument Fails; Why Twins (etc.) Arise

Subsets of integers arising in the stepwise development of the abstract tree have overlapping magnitudes. The proof that these subsets are all disjoint requires a more sophisticated argument.

An example of the trajectory of a long left descent assembly as seen using the state
transition diagram is provided.

State Transition Diagram for Steps Within
One Left Descent Assembly

The allowed transitions within left descents are detailed in support of
the elaboration of the abstract predecessor tree and the consequent
left descent assemblies.

Details of the Path Within State Transition
Diagram for Left Descent to 27

An transition diagram is provided.

State Transition Diagram for Multiple Chained Left Descent Assemblies

An attempt is made to show how
sequential transitions from left descent assembly to extension to l.d.a
to extension .... are supported by the allowed individual transitions.

Early Proof Attempt Based on State Diagrams

This early proof attempt
depends only on the state transition diagram and the graph forming properties
of the l.d.a. graphical elements. Much of the content is repetitious to the
current work.

Observational Development of Integer Sieve
for 3*n*+1 Conjecture

Computer runs give results suggesting
that the left descent assemblies constitute a sieve which covers the odd
positive integers.
*A Priori* Sieve for the Odd Integers
>1 Using the 3*n*+1 World View

A method for using the predecessor
tree's structural features (left descent assemblies and extensions) to
generate a sieve for the odd integers is described.

All Left Descent Subset Formulas
Represent Disjoint Sets

It is pointed out that the method of
construction of formulas of left descent assembly set members results
entirely in disjoint subsets.

Proofs of Some Little Pieces of the Structure

A very few oddments, here and there,
are given proofs.

Summation of the densities of the sets of integers identified in all the left descent assemblies provides for the totality of the integers.

Finite Sums in the Cardinality Table

The sums of the densities of the sets of integers represented in larger and larger samples of left descent assemblies approaches the totality of the integers more and more closely.

Limits to Conclusions Drawn from the State Transition Diagram

It has been suggested that the state transition diagram is less than omnipotent in its support of left descent assemblies and the abstract predecessor tree.

What is Dull (Interesting?) About the Extensions?

The extension sets are tightly interleaving progressions to infinity such that every odd integer can at length be found among them.

Maple Provides the Clue in the Left Descent to 27

This was the discovery event (AHAH!) for this whole work.

Numeric Residue Set Values for the Descent from 445 to 27

Detailed exposition of the residue set descent to 27; offers a contrast to the immediately preceding index entry.

Showing Complete Paths and the Huge Scatter in the Instances of a Given Left Descent Assembly

A single example of complete paths developed from a single terminating left descent assembly.

Shortcut to Numeric Values of the Coefficients in the

It is just a matter of knowing the number of steps in the left descent assembly and the sum of the i's in the successive (3n+1)/2^i steps.

Picture of Integer Filling Through 3 Generations of Left Descent Assemblies

Also referred to as the bedroom wallpaper picture.

Extensions Do Pass Some (Limited) Control

A first hint arose here that certain patterns of development of the predecessor tree are propagated through iteration sequences which include extensions.

Using the symbols {s,b,e} to denote fragments of the paths in the binary predecessor tree and encoding those as {'10','11','0'} achieves a shorter bit string representation of a path than the parity bit string. Naively, at least, this undercuts the thesis of Feinstein's proof.

Infinite Steps or Infinite Sums -- Which Is More Convincing?

The various threads of the arguments introduced in the above pages are pulled together not only to argue that Feinstein's proof of the unprovability of the Collatz conjecture is incorrect, but also that this work provides such a proof.

E-Mail from Oleg developing scaling transformations to form a more general (3

Converging Sequences:(3

Some quick diagnostic tests, state transition diagrams, and samples of the predecessor trees for these analogs are presented.

Comparison of Behaviors of Members of the (3n+3

A table detailing the differences in features of the analogous (3n+3

Observations within the (3n+3

The retention of powers of 3 in segments of the itineraries and the appearance of left descent assemblies among these trees is noted.

Analogs of Collatz Sequences which Fail to Converge to an Integer

We look at cases of (ax+b)/2^i where a is not 3 and/or b is not 1).

Diverging Trajectories from (5n+1)/2

This is the case which made everyone apprehensive that the Collatz trajectories might include one or more divergent ones.

If you want a quick trip through my work, look at a somewhat outdated (from 2005 or so) 24 slide show, either serially or through an index, which contains a few pointers to illustrative material. Always use your browser's back button to return to the slide show if you look at this auxiliary material.

Now in May/June, 2006, I'm trying to streamline, condense, improve the
organization of the components, etc. I'll try to do so without worsening
the already dense and sometimes confused presentation. I've made a
new attempt to produce a very concise
presentation of the
main arguments I believe will produce a proof of the Collatz conjecture.

A draft paper (in February 2007)
giving the
abstract predecessor structure but prior to recognition of the duplication
of integers among the resdiue sets.
A more recent (after the duplication of integers in resitue sets was realized)
simplified version of the proof is also
provided. This contains many detailes elided from the current paper.

(3n+1)/2^i Predecessor Tree as a General Tree

(3n+1)/2^i Predecessor Tree as a Binary Tree

Collatz Graph Nodes and Edges in Isolation

Collatz Graph nodes and Edges in Binary Predecessor Tree Context

Abstract (3n+1)/2^i Predecessor Tree Defined Iteratively

State Transition Diagram within Left Descent Assemblies

State Transition Diagram for Multiple Chained Left Descent Assemblies

State Transition Table for the (5n+1)/2

State Transition Diagram for Predecessors in the (5n+1)/2

State Transition Diagram for the (3n+3)/2

Binary Predecessor Tree for the (3n+3)/2

State transition diagram for Successors in the (5n+1)/2

State Transition Diagram for the (3n+3^j)/2

Predecessor Tree (as a General Tree) for (3*

Abstract Predecessor Tree, 3 Levels, With Set Names

Abstract Tree for Paths

Stepwise Downward Development of Set Contents in Abstract Predecessor Tree

Stepwise Upward Development of Subset Contents in Abstract Predecessor Tree

Subsets Nested to Show Progressive Diminution of Unresolved Extension Elements

Table of Cardinalities of Subsets Sharing {a,b} in Abstract Predecessor Tree

Cumulative Filling of the Integers, Fibonacci-Wise

Location of Left Descent Assemblies of Zero to Three Steps in the Cardinality Table

Location of Two Lengthy Left Descent Assemblies, and Scope of Left Descent Assemblies of Those Lengths in the Cardinality Table

Diagram of Integer Coverage by Growth of the Abstract Predecessor Tree

Diagram of Integer Coverage by Growth in the Cardinality Table

Relationship of Pascal Triangle to Fibonacci Numbers

Sample Characterization of Arbitrary Integer in Abstract Predecessor Tree

Listing of Extensions for Left Descent Assemblies<=100061

Several Examples of Complete Left Descent Assemblies

Predecessor Tree for (3n+3

I will modify or add to these pages from time to time as I get feedback from readers or make new discoveries myself.

Let me emphasize that I know no proof with adequate mathematical rigor exists here. That is why I've put these pages up. I hope I'm writing this well enough both to attract other amateurs to the problem and to attract one or more professional mathematicians to the problem of developing a formal proof on the basis of some or all of the structure presented here. At least it should encourage some fresh thinking.

KSU Home Page Index to Terms Used