Observational Development of Integer Sieve for 3n+1 Conjecture

This page takes its point of departure from the huge output file of the program treegrow.   This program produces an output line for every element of every left descent assemblage up to the programmed limits of magnitude of number reached and depth reached.  The format of the output is illustrated in a selected set of lines of the output,  depicting the 2^a3^b*n+c format for the formulas.

If we arrange the extension headers for the left descents in order of increasing value of the constant term,  we quickly realize that they behave like a sieve.   Once the constant (i.e. first  (zeroth?)  instantiation)  for the formula for an extension has appeared,  the integers calculated by formula for higher instantiations never appear as the constants in formulas for later extensions or left descent elements.   (I'm using the word 'instantiate' to denote to process of determining all the higher values reached by a formula by using values of 1, 2, 3, ... for n,  the initial instance being that resulting from n=0.)   Thus,  the initial instances of the extensions are very prime-like in their behavior.   Just as with the Sieve of Eratosthenes,  the density of the extensions decreases as the magnitude of the number reached increases.

When the sieving is done for each extension in turn,  not only do the higher instances of the extension element get sieved,  but also all the higher instances of the various left descent elements below the extension act like sieves also.   As many integers are sieved for each value of n as there are elements in each left descent.   To emphasize this point,  the sieving unit may be called a left descent assemblage.  A set of linear formulas,  those of the elements of the left descent assemblage,  determines the higher integers to be sieved;  it is not simple multiples which are sieved as in the sieve of Eratosthenes.   The sieving occurs in aggregates,  not in singles.

Just as any given prime results in identification of an infinite number of composites in the process of Eratosthenes sieving, so,  too,  does every extension and all the elements of its left descent,  when instantiated to higher numbers,  result in the identification of an infinite number of integers to be sieved.   The numbers reached by higher instantiations of each element in all the left descents never appear among the constants in any formula.  This is a necessary condition since we wish to cover the odd integers uniquely -- if one expression with n=0 were to give the same integer as another formula with n>0,  a given integer would be reached more than once.

The manner in which the first few l.d.a.s and their first few instantiations fill the number line is illustrated in a picture which looks like psychodelic wall paper  (or would if prepared on a larger scale,  with a complete set of l.d.a.s.,  and more differentiated colors).   The number line is wrapped at a length chosen to match integral or simple mixed fractions of integral d  (from dn+c)  to emphasize the periodic nature of the instantiations.   Perhaps this will give an impression of why/how the sieving described here works.

This sieve-like behavior was an unexpected development.   We simply gathered the extension elements which emerge from the down-and-up-again process which results in specific expressions for the extension elements which head each left descent.  That process dissected the extension set into two categories.   Those that emerge from the process are prime-like,  and those which do not emerge fail to do so because they appear among the projections to higher numbers from lower left descent assemblages.  Two illustrations are provided to give concrete examples of all this,  one showing extensions alone and the other showing complete left descent assemblages.

The file of extension headers fails to illustrate the point about sieving involving an entire left descent assemblage, not just the extension element heading it  The second illustrative file of left descent assemblages repairs that omission on a smaller selection of left descents.  The integer values reached by the first six left descent sieving units have been worked out to show the initial elements of the infinite series of integers sieved by each left descent element.  The reader may wish to verify that the integers listed there are not repeated later in the file.

This suggests that there is here a phenomenon very like that responsible for the fundamental theorem of arithmetic,  which is that every integer greater than 1 is either prime or composite, and every composite number can be factored uniquely into prime factors.  Here we say that every odd integer greater than 1 can be uniquely identified as either a member of a first instance of some left descent assemblage  (in which n=0 in the dn+c formula so that the constant c represents the integer)  or is a member of a higher instance of a left descent assemblage  (whence the integer is represented by the linear expression dn+c, n>0).   We have shown elsewhere that any integer can be uniquely located in this scheme.

A sweeping generalization like this could hardly be justified on the basis of observations in finite files of
extensions or left descent assemblages.   But this position was reached after
development of three versions of the 3n+1 predecessor tree,
"counting" the contents of the abstract predecessor tree in various ways,
developing down and up methodology for dividing the nodes in the abstract predecessor tree up into left descent paths,
assigning algebraic expressions to each element of each such path,
programming the production of huge samples of such expressions, and
producing arguments to the effect that only a tree can represent the 3n+1 predecessor graph, prior to discovery of this sieve-like behavior.

Describing the structure of the integers using a sieve from the 3n+1 viewpoint maps into the description of the fully subsetted abstract connection tree.   It may offer a means to proof of the conjecture which its equivalent may fail to suggest,  or features gleaned from each viewpoint may combine to lead to a useful proof.

My Collatz Home Page         Index to Terms Used