Hailstone Patterns

In a recent e-mail, Dan again brought up the subject of the image referred to in the following sci.math post (emphasis added). As I needed something to try out my latest programming language (PLT Scheme), I decided to have a look.

From: Dan (30pack@sbcglobal.net)
Subject: Re: Thoughts on the Collatz conjecture 
Newsgroups: sci.math
Date: 2003-08-15 18:14:02 PST 

Thanks to all for your responses to my original post.

I am still convinced that the conjecture is true, because after
hastily throwing together a computer program that I believe makes the
case.

My argument here is, as each level of the Collatz tree grows new
branches are born derived from a smaller integer start number and so
does the density "bands" (see below) and their symmetry.  This causes
a symmetrical squeeze play so to speak for other possible counter
examples start numbers and trees.

I did a computer program where integer start numbers are entered in
order where start number n = 1,2,3,4,5,6..n with there associated
sequences.  Each start # turns on a corresponding numbered pixel and
all the path members turn on their respected pixels. These pixels stay
on.

Naturally some of these pixels are on when they get hit again for an
"on" because of the branching tree affect and also returning back to
4,2,1 and terminating on 1. What happens as each new starting  (n) the
(5) density bands out ahead of the all white band become more apparent
after about 32 "y" rows of all "on" (white) pixels. This would be an
integer start number the size of n =32*640 = 20480.

I set this thing up for reading across --- 
               640 pixels where x ( n)  (start #)= 1 to 640 and y=1
Then where x = 1 to 640 and n=641 to 1280 and y=2 etc.
Y is set for a max. of 350 pixels.  It bypasses any on pixel that is
not viewable on screen where y >350.

It creates an interesting effect with 6 distinct bands with each of
the 5 bands having distinct symmetrical density patterns out ahead of
(n) the seed that is the all white band behind the seed.

This density band effect could be do to certain delta factors out
ahead of the seed or something to do with 2^n?

The short basic program is listed below with plenty of documentation
so someone can translate to Java, c++ or any other language.

‘ = Docs

4 ‘ A Collatz conjecture pixel evaluation
5 ' This program turns on the appropriate pixel for each starting
integer and all its sequence members.
 Pixels once on, stay on.
10 CLS
12 Screen 9: ‘ Set graphics screen mode to 350 X 640 pixels
15 DEFDBL A: ‘Double precision for any variable beginning with A
20 A=1:A3=A:A4=1:Y=1:A5=640:A6=640: PSET(A,Y): ‘   "A" is starting
integer (seed) and turns on pixel x(A) = 1 and  Y = 1: This line never
used again.
30 A1$=STR$(A): ‘  Line 30-54 checks to see if integer is odd or even.
40 A2=LEN(A1$)
50 J$=MID$(A1$,A2,1): IF J$= "1" THEN GOTO 200
51 IF J$= "3" THEN GOTO 200
52 IF  J$= "5" THEN GOTO 200
53 IF  J$= "7" THEN GOTO 200
54 IF  J$= "9" THEN GOTO 200
60 A3=A3/2:A=A3:GOSUB 500: IF A =< 1  THEN 320 ELSE 30:' This line
handles even integers and goes to subroutine that evaluates the
correct x and y pixel to turn on.
200 A3=(A*3) +1:A=A3:GOSUB 500:GOTO 60: ' Handles odd integers of seed
and its sequence.  Ect.
320 A4=A4+1:A=A4:A3=A4:GOSUB 500:GOTO 30: 'Retrieves the next seed and
repeats the whole process creating a new sequence from that seed.
500 IF A>A6 THEN A6=A6+A5:Y=Y+1:ELSE 530: ' Sets Up "A" for right row (Y)
510 If Y>350 THEN Y=1:GOTO 540: ' If integer value in any sequence is 
> (350*640) then this line bypasses the pixel command (PSET) because
pixel will not be in a viewable area of the screen.
515 IF A>A6 THEN 500: ' Go back to line 500 and add another 640 to variable A6
520 IF A=< A6 AND Y>1 THEN
Y=Y-1:A7=Y*A5:A8=A-A7:Y=Y+1:PSET(A8,Y):Y=1:GOTO 540: ' Sets up x(A8)
value when y>1 and thus the correct x,y coordinates for any applicable
integer with a value > 640.
530 If Y=1 THEN PSET(A,Y): GOTO 540:' A branch from 500 where Else means Y=1
540 A6=A5:Y=1:RETURN: ' Resets variables and  returns for next integer.
600 END

Please excuse the hastily thrown together code. Should have done a
renumber also!

You have to think of each row of 640 pixels as rows cut off at that
point and then stacked on each other where you can easily view how
these density patterns out ahead of the seed number are formed. This
would probably go unnoticed if the line stayed continuous as in the
number line.

This creates 5 distinct and  fascinating density band patterns that
grow in width as the first solid white band or seed band grows in width.
Please note, when first starting out the bottom (last) density pattern
starts to show a checkerboard pattern on an angle.

If nothing more, its interesting!

As always, any evaluations or comments are welcome.

Dan

This image looks consistent with Dan's description. The origin (0,0) is in the upper left corner. Adjectives such as "above" or "greater" will mean downwards or to the right in the image. Let's see what we can make of it.

First, some terminology. Collatz sequences are sometimes called Hailstone numbers for the way the value of x rises and falls through the sequence. Keeping the weather metaphor:

HAILSTONE: A number that is larger than its predecessor. A HAILSTONE results from the application of 3x+1.
TROPOSPHERE: For any sequence starting at n, the TROPOSPHERE is the area of the image of all points less than n. All points less than n have already been plotted and appear as the solid white band at the top of the image. A HAILSTONE disappears from view when it drops into the TROPOSPHERE.
STRATOSPHERE: The region of the image above the TROPOSPHERE. The STRATOSPHERE is the Collatz sequence's excursion, the part of the sequence where x is greater than its initial value of n.
CONTRAIL: The track of pixels left by a sequence as it traverses the STRATOSPHERE. A CONTRAIL starts when the HAILSTONE first enters the STRATOSPHERE and ends when it a) drops into the TROPOSPHERE or b) becomes an odd number at which point it becomes a new HAILSTONE initiating a new CONTRAIL.

To make sense of the image, it is handy to review a few things about Collatz sequences that are a consequence of the x/2, 3x+1 rules.

every HAILSTONE is == 4 (mod 6)
a CONTRAIL alternates between == 4 (mod 6) and == 2 (mod 6), except for the terminating pixel which is either == 1 (mod 6) or == 5 (mod 6).
numbers == 0 (mod 6) or 3 (mod 6) are only found in the TROPOSPHERE.

Now we can adjust the image to take advantage of these facts. First, if we make the image width a multiple of 6, the HAILSTONES will all nicely line up in vertical columns. And if we color the pixels

0 (mod 6): red
1 (mod 6): green
2 (mod 6): blue
3 (mod 6): magenta
4 (mod 6): yellow
5 (mod 6): cyan

the image now starts to convey real meaning. HAILSTONES (yellow pixels) dominate the upper regions of the STRATOSPHERE. The CONTRAILS left by these HAILSTONES will be found in the lower levels of the SRATOSPHERE. The STRATOSPHERE is devoid of red or magenta pixels as noted above that they can only be found in the TROPOSPHERE.

Now that all the HAILSTONES are nicely aligned, we still have those diagonal patterns. This indicates the presence of some meta-pattern on top of the mod 6 coloring. The displacement of adjacent points on the diagonal lines turns out to be 243 (3**5). But 243 is not a multple of 6, so we need to set our window width to 2*243 or 486 pixels to reveal the meta-pattern while maintaining the mod 6 alignment.

Voilà, order out of chaos:

In the following discussion, a HAILSTONE n will have image coordinates (h,v) such that

h = remainder of n/486
v = quotient of n/486

We see from the long column of yellow pixels on the right side of the image that 484 (mod 486) is a popular place for HAILSTONES to end up. And note the prominent blue column in the center of the image. If a CONTRAIL is more than 2 pixels in length, the second pixel of a CONTRAIL starting at 484 (mod 486) will be on that central blue line. It's halfway to the left and halfway up as one would expect from the x/2 rule. If the blue pixel image coordinates are both even, the next pixel in the CONTRAIL will also appear halfway to the left and halfway up, as in the example below for the HAILSTONE at (484,124):

Note that the third pixel is green, thus ending the CONTRAIL (it will, of course, initiate another CONTRAIL somewhere else in the STRATOSPHERE). The HAILSTONE at (484,122) descends all the way into the TROPOSPHERE, bouncing back and forth between blue and yellow columns:

So we see how a prominent yellow column leads to a prominent (but smaller) blue column which leads to a prominent (but smaller) yellow column which leads to a prominent blue column, etc.

Note also that the prominent yellow column at 484 (mod 486) has a prominent cyan column adjacent to it. Not a coincidence. Every yellow pixel at h:484 whose v is odd, becomes congruent to 485 (mod 486) when divided by 2. Thus, half the CONTRAILS that start in the yellow column 484 terminate in column 485:

But how did column 484 (mod 486) get to be so prominent in the first place? Up until now, we haven't investigated what happens when a CONTRAIL terminates (always on a green or cyan pixel). Green and cyan pixels are odd numbers, so the next number will be a yellow pixel. Let's follow the CONTRAILS of pixel (484, 63):

Lo and behold! We've got a resonator! The yellow pixel at 484 (mod 486) becomes a cyan pixel at 485 (mod 486) which becomes a yellow pixel at 484 (mod 486) which becomes a cyan pixel at 485 (mod 486), and so on. No wonder the column 484 has so many pixels, it's self-generating.

So how come it doesn't run off to infinity? Because the property that sustains the resonance cannot be maintained indefinitely. The binary resonator 2**n - 1 stops when it runs out of 1 bits. Something happens to stop the (mod 486) resonance. A quick look at the actual Collatz sequence will reveal what. That particular sequence originated with n = 3830. At iteration 19, the sequence hits a binary resonator. Halfway through, the CONTRAIL hits column 484 and the resonance begins:

            pixel    pixel
       n        v        h        n (binary)
--------  -------  ------- -----------------
    2047        4      103 11111111111         <-- binary resonance starts
    6142       12      310 1011111111110
    3071        6      155 101111111111
    9214       18      466 10001111111110
    4607        9      233 1000111111111
   13822       28      214 11010111111110
    6911       14      107 1101011111111
   20734       42      322 101000011111110
   10367       21      161 10100001111111
   31102       63      484 111100101111110     <-- (mod 486) resonance starts
   15551       31      485 11110010111111
   46654       95      484 1011011000111110
   23327       47      485 101101100011111
   69982      143      484 10001000101011110
   34991       71      485 1000100010101111
  104974      215      484 11001101000001110
   52487      107      485 1100110100000111
  157462      323      484 100110011100010110
   78731      161      485 10011001110001011
  236194      485      484 111001101010100010
  118097      242      485 11100110101010001
  354292      728      484 1010110011111110100 <-- (mod 486) resonance ends
  177146      364      242 101011001111111010

Aha! The resonance stopped when we got an even pixel v coordinate. As seen earlier, when both v and h are even, the CONTRAIL goes to the blue column in the center of the image, breaking the column 484:485 resonance. But before dropping into the TROPOSPHERE, it hits column 484 a second time:

            pixel    pixel
       n        v        h        n (binary)
--------  -------  ------- -----------------
  336310      691      484 1010010000110110110
  168155      345      485 101001000011011011
  504466     1037      484 1111011001010010010
  252233      518      485 111101100101001001
  756700     1556      484 10111000101111011100
  378350      778      242 1011100010111101110

And it hits it again after dropping into the TROPOSPHERE, but only manages to toss a single HAILSTONE into the STRATOSPHERE.

            pixel    pixel
       n        v        h        n (binary)
--------  -------  ------- -----------------
    1942        3      484 11110010110
     971        1      485 1111001011
    2914        5      484 101101100010
    1457        2      485 10110110001
    4372        8      484 1000100010100
    2186        4      242 100010001010

Checking a couple other yellow columns, 322 (mod 486) and 376 (mod 486), showed that although they may get hit as many as four times in a single Collatz sequence, they don't "ring" when struck like 484 (mod 486) does.

I don't what significance this has in proving the Collatz Conjecture, but it is certainly one of those many items that make it endlessly fascinating.