A Priori Sieve for All Odd Integers >1 Using the 3n+1 World View

I will present,  as briefly as I can,  the sieving procedure which I claim will reach all the odd positive integers >1.  I will present it as if were an a priori truth although it was,  in fact,  the result of a long developmental process.

First,  we need some definitions.  All this is predicated on views of a predecessor tree showing where every odd integer comes from in the 3n+1 process.

The extensions are the odd positive integers congruent to 5 mod 8 (i.e.  fitting the formula 8n+5 for all non-negative integers n).  They are so-called because the extensions of any binary predecessor tree element (e.g.  17 whose extensions are 69,  277,  1109,  4437,  17749,  70997,  ...)  all go to the same odd integer (13 in this example)  in the Collatz 3n+1 trajectories.

Left descents are the series (possibly null)  of odd integers obtained from an extension by use the recursive formula
T(k):=(-1+T(k-1)*2^p(k))/3     where p(k)  is 2 when T(k-1)  is congruent to 1 mod 3 and
                                                            p(k)  is 1 when T(k-1)  is congruent to 2 mod 3. 

Left descents are terminated when T(k-1)  is congruent to 0 mod 3. 

A left descent assembly is an extension and its complete left descent.  All elements of all left descent assemblies have formulas dn+c (where d is some 2^a*3^b).  This unit serves as the sieving template in what follows.  The left descent assembly of the example is 13,  17,  11,  7,  9.

Think of the Sieve of Eratosthenes.  Think of the left descent assemblies.  The first one is at n=0,  c=5.  The sieving process involves striking out for all values of n from 0 to infinity every integer reached by every member of the assembly.  Each member of an assembly causes the striking out of every element of the arithmetic progression indicated by its dn+c formula.  The second left descent assembly is at n=0,  c=13; do the same with it.  And so on.  Soon we encounter values of extensions which are already sieved by earlier activity.  Skip any such.  The process goes on forever,  of course.

The values of d and c for the formulas for the elements of the left descent assemblies are easily derived by tracing the path down the assembly to a leaf set using the formulas above and then tracing the path back up again to its root extension using the Collatz 3n +1 and divide by 2^p routine.  This process is illustrated separately in each direction downward,  and upward.

These directions suffice to permit an ab initio sieving which will cover all the odd positive integers >1.

One can identify any arbitrary odd integer in that data structure as the ith element in the nth instance of such-and-such a left descent assembly.  (I've been identifying left descents with a string composed of an 'e',  some series composed of 'b's and/or 's's concluded with a 't'.)  The left descent assemblies are all unique.  The ability to precisely locate any odd integer in the sieving structure lends credence to the notion that all odd integers are indeed reached by the sieving process.

Overall,  this sieving structure boils down to a list of lists.  There is,  first,  a list of extensions which are heads of left descents.  Under each header there is a list of left descents.  Alternatively,  one could say there is a list of left descent assemblies.  Two files are provided showing the first few hundred extensions which head the sieving assemblies and the first few dozen complete sieving assemblies.

This description of the structure is just a restatement of the structure of the abstract predecessor tree after the subsets have been separately identified throughout.  But it does seem to provide an intuitively more compelling feeling that the process will not stop short of the goal of reaching all integers uniquely.  At least,  this additional viewpoint may serve as an alternative one for teasing out the basis for a proof of the Collatz conjecture.

I've already argued that the abstract predecessor tree contains all the odd integers,  and I already made arguments that every odd integer has a unique path to it (hence a unique position in the tree).


My Collatz Home Page         Index to Terms Used