Program Fullmap

The work of this web site is based on a structure which describes the Collatz predecessor tree in terms of l.d.a.s  (left descent assemblies)  and extensions.  While the structure is amply explained elsewhere in these pages,  readers often have difficulty gaining a full appreciation of the structure and its implications.  Another program, IDtheLDA,  has been written and posted here which accepts an arbitrary odd positive integer and proceeds to identify the l.d.a.  it resides in,  its position among the elements of that l.d.a.,  and which instantiation of that l.d.a. it occurs in.  This program is extremely useful in exploring the behavior of l.d.a.s and gaining an understanding of the abstract predecessor tree which serves as the high level summary of the entire family of l.d.a.s.

However,  merely establishing which l.d.a. an integer appears in does little to elucidate the manner in which the l.d.a.s are chained together through the extensions to form the complete binary predecessor tree.  The program which follows is designed to provide exactly that additional insight.  The reader who has studied the code of IDtheLDA will immediately see that this code uses many segments of that code unchanged or very slightly changed,  while making control modifications and output modification to further its different goal.

The listing below is captured directly from MapleV4's listing of the completed program, with indention and statement numbering as provided by MapleV4.  The variables are largely carried forward unchanged from IDtheLDA in name and function.  A new variable instwas keeps an early value calculated for the instantiation of an l.d.a. reached in the Collatz trajectory,  before inst takes up a more reasonable value.  suc and ssuc are two variables which in sequence give the values of the phantom successor of the header of the current l.d.a. in the binary tree version of the predecessor tree,  and its successor,  which has the value of the Collatz successor when the predecessor tree is depicted as a general tree. These two values serve to identify the point of entry into the next l.d.a. to be visited.

The high level logic is that the program loops through a series of oddi values,  each derived from the header reached in the previous l.d.a.  (stmts 24,70)  as modified by "undoing" the 4n+1 relationship  (stmts 78-79)  to find the new oddi value.  The stmts 66-70 are engaged in providing output for the start of the next iteration. oddi, updated in stmt 79, will find its way tortuously in the continued execution of the main loop to 1,  the root of the predecessor tree,  which completes the loop begun at stmt 5.

The residue sets denoting every element of every l.d.a. are expressed canonically as c[d],  meaning congruent to c modulo d,  where c<d.  It was discovered that frequently the numbers obtained by fullmap in the major loop of stmts 28-48 for the leaf node of the l.d.a. are non-canonical with c>d,  or even c>>d.  (This probably arises among many other elements of the l.d.a.s, but it suffices to make the residue designation for the leaf node canonical.)   Stmts 54 through 65 deal with that situation and the output of stmt 65 gives both the  (often bizarre)  original residue set designation  (from which its successors in the l.d.a. could be calculated)  followed by the corrected one  (presumably more familiar).

Since the entry point into a new l.d.a. can occur at any point along its length,  it was necessary to discover what point that was in the current l.d.a. to provide a compete picture.   Since p3 is tracking the l.d.a.'s number of elements,  and isw the value  (i.e. dn+c)  of each element,  the pos value is easily captured when the correct element goes by  (stmts 45 and 46)  for reporting from stmt 76. Much code is consumed by variable shuffles,  largely left over from IDtheLDA,  to keep track on both the input side (isX) and the output side (osX),  though very little is done on the output side except reporting the results.

The plevel argument controls the quantity of output.  If it is set at 10,  the normalization of the residue set designation is shown.  If plevel is 3, output is produced showing the growth of each l.d.a.  encountered.  If plevel is 0,  the sole output is that of stmts 76 and 77 to give only the transition from the previous l.d.a.  to the l.d.a. to be explored next.  This transition is given both as the phantom element which appears in the binary predecessor tree and its successor which is the "true" Collatz successor of the header of the previous l.d.a.  from the viewpoint of the general predecessor tree.  This is fairly scant information,  but using plevel at 3 or 10 produces prodigious amounts of output.

fullmap := proc(start, plevel)
local adj, cisc, cisd, hisw, inst, instwas, isc, isd, isw, ldastr, oddi, osc,
      osd, osuc, osw, pos, p2, p3, suc, ssuc;
   1   fopen(`\\maplev4\\mywork\\fullmap.lst`,APPEND,TEXT);
   2   fprintf(`\\maplev4\\mywork\\fullmap.lst`,`fullmap run with %d printlevel %d\n`,
        start,plevel);
   3   oddi := start;
   4   ssuc := oddi;
   5   while 1 < oddi do
   6     if `mod`(oddi,2) = 0 then
   7       ERROR(`Sought integer must be even. Quitting.\n`)
         end if;
   8     isw := oddi;
   9     pos := 1;
  10     if `mod`(oddi,3) = 0 and `mod`(isw,8) = 5 then
  11       ldastr := et;
  12       osd := 24;
  13       osc := 5;
  14       inst := 1/24*oddi-7/8
         else
  15       if not `mod`(isw,8) = 5 then
  16         while not `mod`(isw,8) = 5 do
  17           if `mod`(isw,2) = 1 then
  18             isw := 3/2*isw+1/2
               else
  19             isw := 1/2*isw
               end if
             end do
           end if;
  20       ldastr := e;
  21       p3 := 1;
  22       p2 := 3;
  23       hisw := oddi;
  24       suc := isw;
  25       isd := 8;
  26       if 2 < plevel then
  27         fprintf(`\\maplev4\\mywork\\fullmap.lst`,
             `isw: %d, isd: %d, lda to date: %s\n`,isw,isd,ldastr)
           end if;
  28       while not `mod`(isw,3) = 0 do
  29         p3 := p3+1;
  30         if `mod`(isw,3) = 1 then
  31           if `mod`(isw+isd,3) = 1 then
  32             isw := -1/3+4/3*isw+4/3*isd
               elif `mod`(isw+2*isd,3) = 1 then
  33             isw := -1/3+4/3*isw+8/3*isd
               else
  34             isw := -1/3+4/3*isw
               end if;
  35           ldastr := cat(ldastr,b);
  36           p2 := p2+2;
  37           isd := 4*isd
             elif `mod`(isw,3) = 2 then
  38           if `mod`(isw+isd,3) = 2 then
  39             isw := -1/3+2/3*isw+2/3*isd
               elif `mod`(isw+2*isd,3) = 2 then
  40             isw := -1/3+2/3*isw+4/3*isd
               else
  41             isw := -1/3+2/3*isw
               end if;
  42           ldastr := cat(ldastr,s);
  43           p2 := p2+1;
  44           isd := 2*isd
             end if;
  45         if isw = ssuc then
  46           pos := p3
             end if;
  47         if 2 < plevel then
  48           fprintf(`\\maplev4\\mywork\\fullmap.lst`,
               `isw: %d, isd: %d, lda to date: %s\n`,isw,isd,ldastr)
             end if
           end do;
  49       ldastr := cat(ldastr,t);
  50       cisd := 2^p2*3^p3;
  51       inst := floor(isw/cisd);
  52       cisc := isw-inst*cisd;
  53       isc := cisc;
  54       if isc < 0 or isd < isc then
  55         instwas := floor(isc/isd);
  56         if plevel = 10 then
  57           fprintf(`\\maplev4\\mywork\\fullmap.lst`,
               `adjusting c: %d, d: %d, instwas: %d`,isc,isd,instwas)
             end if;
  58         if isc < 0 then
  59           isc := isc+ceil(-isc/isd)*isd
             else
  60           isc := isc-floor(isc/isd)*isd
             end if;
  61         isw := isc;
  62         osc := isc;
  63         inst := 0;
  64         if plevel = 10 then
  65           fprintf(`\\maplev4\\mywork\\fullmap.lst`,
               ` to c: %d, d: %d, n: %d\n`,isc,isd,inst)
             end if
           end if;
  66       osuc := ssuc;
  67       osw := isw;
  68       osd := 3*isd;
  69       osc := isc;
  70       oddi := suc;
  71       while `mod`(suc,8) = 5 do
  72         suc := 1/4*suc-1/4
           end do;
  73       ssuc := 3/2*suc+1/2;
  74       while `mod`(ssuc,2) = 0 do
  75         ssuc := 1/2*ssuc
           end do
         end if;
  76     fprintf(`\\maplev4\\mywork\\fullmap.lst`,
         `csuc:%d, lda:%s, n:%d, osd: %d, n*d: %d, n*d+c: %d, osc: %d,
         pos'n: %d\n\n`,osuc,ldastr,inst,osd,inst*osd,isw,osc,pos);
  77     fprintf(`\\maplev4\\mywork\\fullmap.lst`,
         `Watch for phantom %d and successor %d ex reduced %d\n`,
         suc,ssuc,oddi);
  78     while `mod`(oddi,8) = 5 and 1 < oddi do
  79       oddi := 1/4*oddi-1/4
         end do
       end do;
  80   fclose(`\\maplev4\\mywork\\fullmap.lst`)
end proc

From fullmap(127,10) one gets:

fullmap run with 127 printlevel 10
isw: 1093, isd: 8, lda to date: e
isw: 1457, isd: 32, lda to date: eb
isw: 971, isd: 64, lda to date: ebs
isw: 647, isd: 128, lda to date: ebss
isw: 431, isd: 256, lda to date: ebsss
isw: 287, isd: 512, lda to date: ebssss
isw: 191, isd: 1024, lda to date: ebsssss
isw: 127, isd: 2048, lda to date: ebssssss
isw: 169, isd: 8192, lda to date: ebssssssb
isw: 225, isd: 32768, lda to date: ebssssssbb
csuc:127, lda:ebssssssbbt, n:0, osd: 98304, n*d: 0, n*d+c: 225, osc: 225, pos'n: 8

Watch for phantom 273 and successor 205 ex reduced 1093
isw: 205, isd: 8, lda to date: e
isw: 273, isd: 32, lda to date: eb
adjusting c: 273, d: 32, instwas: 8 to c: 17, d: 32, n: 0
csuc:205, lda:ebt, n:0, osd: 96, n*d: 0, n*d+c: 17, osc: 17, pos'n: 1

Watch for phantom 51 and successor 77 ex reduced 205
isw: 77, isd: 8, lda to date: e
isw: 51, isd: 16, lda to date: es
adjusting c: 51, d: 16, instwas: 3 to c: 3, d: 16, n: 0
csuc:77, lda:est, n:0, osd: 48, n*d: 0, n*d+c: 3, osc: 3, pos'n: 1

Watch for phantom 19 and successor 29 ex reduced 77
isw: 29, isd: 8, lda to date: e
isw: 19, isd: 16, lda to date: es
isw: 25, isd: 64, lda to date: esb
isw: 33, isd: 256, lda to date: esbb
csuc:29, lda:esbbt, n:0, osd: 768, n*d: 0, n*d+c: 33, osc: 33, pos'n: 1

Watch for phantom 7 and successor 11 ex reduced 29
isw: 13, isd: 8, lda to date: e
isw: 17, isd: 32, lda to date: eb
isw: 11, isd: 64, lda to date: ebs
isw: 7, isd: 128, lda to date: ebss
isw: 9, isd: 512, lda to date: ebssb
csuc:11, lda:ebssbt, n:0, osd: 1536, n*d: 0, n*d+c: 9, osc: 9, pos'n: 3

Watch for phantom 3 and successor 5 ex reduced 13
isw: 5, isd: 8, lda to date: e
isw: 3, isd: 16, lda to date: es
csuc:5, lda:est, n:0, osd: 48, n*d: 0, n*d+c: 3, osc: 3, pos'n: 1

Watch for phantom 1 and successor 1 ex reduced 5

127 is in the 8th position in the lda ebssssssbbt,  an lda whose leaf node in 225[98304].  Details of the rest of the lda elements can be calculated directly from this.  The exit from an lda always occurs from its header,  so it is 1093 from which its phantom successor ((n-1)/4 gives 273) and its Collatz successor (usual calculation gives 205) are determined and the latter used for oddi for the next stage.

With fullmap(127,0),  a much reduced output is produced revealing only hints of the detail which has been traversed.

csuc:127, lda:ebssssssbbt, n:0, osd: 98304, n*d: 0, n*d+c: 225, osc: 225, pos'n: 8

Watch for phantom 273 and successor 205 ex reduced 1093
csuc:205, lda:ebt, n:0, osd: 96, n*d: 0, n*d+c: 17, osc: 17, pos'n: 1

Watch for phantom 51 and successor 77 ex reduced 205
csuc:77, lda:est, n:0, osd: 48, n*d: 0, n*d+c: 3, osc: 3, pos'n: 1

Watch for phantom 19 and successor 29 ex reduced 77
csuc:29, lda:esbbt, n:0, osd: 768, n*d: 0, n*d+c: 33, osc: 33, pos'n: 1

Watch for phantom 7 and successor 11 ex reduced 29
csuc:11, lda:ebssbt, n:0, osd: 1536, n*d: 0, n*d+c: 9, osc: 9, pos'n: 3

Watch for phantom 3 and successor 5 ex reduced 13
csuc:5, lda:est, n:0, osd: 48, n*d: 0, n*d+c: 3, osc: 3, pos'n: 1

Watch for phantom 1 and successor 1 ex reduced 5

Here csuc is the calculated successor from a previous iteration which serves as point of departure for this one.  lda gives the current l.d.a.  in the e(s|b)kt notation.  The next five fields give somewhat repetitive information about the leaf node of the current l.d.a.  The final field gives the position in this l.d.a.  at which entry from the header node of the previous one occurred.  Note the variability of this value from l.d.a.  to l.d.a.


My Collatz Home Page        Index to Terms Used