OEIS/A291939

First number on layer n of hailstone chain

The sequence had keyword unkn until March 2018, and there were only 5 terms:

• 1, 12, 19, 27, 37

The original comment was:

If hailstone chains are strictly drawn in numerical order at right angles with consistent 
direction, overlaps occur. The first set of numbers that do not overlap could be considered the 
'first layer'. Once an overlap is needed, all numbers farther up the chain (inclusive) are on a 
higher layer. This is the sequence of the first numbers to appear on layer n.

Hailstone chain is a synonym for Collatz sequences or the 3n+1 problem - see Index entries for sequences related to 3x+1 (or Collatz) problem.

Generating Perl Program

First 5 terms of A291939

After some experimenting it became clear that the description is incomplete, and that it is difficult to develop the sequence with 2-dimensional paper and pencil. The Perl program below generates the sequence, and it has a more detailled description at the beginning. The latest version of the program and its auxilliary files for the 3D visualization can be found on a Github repository.

#!perl

# Build b-file of OEIS A291939 from Collatz sequences in A070165
# @(#) $Id$
# 2018-03-25, dr.georg.fischer@gmail.com
#------------------------------------------------------
# Usage:
#	wget https://oeis.org/A070165/a070165.txt
#	perl a291939.pl 0 a070165.txt > b291939.txt
#   perl a291939.pl mode infile > outfile
#       mode = 0: print the raw b-file for A291939
#       mode = 1: insert additional comments for the 3D structure
#       mode = 2: show additional trace data
# Sequence:
#     1, 12, 19, 27, 37, 43, 51, 55, 75, 79, ... 9997
# Explanation:
# Take the Collatz sequences (CSs) from A070165, and build a 3-dimensional 
# structure representing all CSs up to some starting number (10000).
# In that 3D structure, the y direction is downwards, x is to the right, 
# and the "layer" z is outside.
# Process all CSs with increasing starting number coln = 1, 2, 3 ... 10000.
# Begin at the end of any CS (4, 2, 1), and proceeding up to
# the starting number. Name the elements e[1] = 1, e[2] = 2, e[3] = 4 etc.
# Position the trailing element e[1] = 1 at coordinates (x,y,z) = (0,0,0). 
# Investigate all e[i] (i > 1):
# for even e[i] "go right" = store e[i] at (e[i-1].(x+1), e[i-1].y, e[i-1].z), 
# for odd  e[i] "go down"  = store e[i] at (e[i-1].x, e[i-1].(y+1), e[i-1].z),
# whenever that position is not occupied by a different number, 
# otherwise "go out", i.e. increase the layer z by one for all new elements
# to be stored from now on.
# The target sequence A291939 = a(n) consists of the starting 
# values of the CSs which reach a z coordinate of n for the first 
# time.
#--------------------------------------------------------
use strict;
my $mode = 1; # 0 = b-file only, 1 = with 3D coordinates, 2 = more trace output
if (scalar(@ARGV) > 0) {
    $mode = shift(@ARGV);
}
my $bfn = 1; # index for target b-file
my $layer = 1;
my @elems; # maps elements of a CS to their coordinates (x,y,z)
$elems[1] = "0,0,0";
my %coords; # maps (x,y,layer=z) -> elements of a CS
$coords{$elems[1]} = 1;
print <<"GFis";
# b-file for A291939, n=1..1769, generated by perl $0 $mode a070165.txt
1 1
GFis
my @colseq = ();
my $curr_layer = 0;
while (<>) {
    next if ! m{\A\d}; # no digit in column 1 -> skip initial comment lines
	# 9/20: [9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
	s/\s+//g; # remove all spaces
    my ($pair,$cs) = split(/\:/);
    my ($coln, $count) = split(/\//, $pair); # CS starts at $coln and has $count elements
    $cs =~ s{[\[\]]}{}; # remove square brackets
    @colseq = split(/\,/, $cs);
    if ($mode >= 2) {
        print "# evaluate CS($coln) = " . join(" ", @colseq) . "\n";
    }
    my ($x, $y, $z) = split(/\,/, $elems[1]);
    my $ind = scalar(@colseq) - 1; 
    $ind --; # element's indexes run backwards in contradiction to the explanation above
    while ($ind >= 0) {
        my $elcurr = $colseq[$ind];
        if (defined($elems[$elcurr])) {
            ($x, $y, $z) = split(/\,/, $elems[$elcurr]); 
        } else { # undefined - append to chain
            if (($elcurr & 1) == 0) { # even -> go right
                $x ++;
                &investigate($coln, $elcurr, $x, $y, $curr_layer);
            } else { # odd -> go down
                $y ++;
                &investigate($coln, $elcurr, $x, $y, $curr_layer);
            }
        } # undefined
        $ind --;
    } # while $ind
} # while <>
#--------
sub investigate {
    my ($coln, $elcurr, $x, $y, $z) = @_;
    if (defined($coords{"$x,$y,$z"})) { 
        my $stelem = $coords{"$x,$y,$z"};
        if ($stelem ne $elcurr) { # collision
            $curr_layer ++;
            $z = $curr_layer;
            if ($mode >= 1) {
                print "# collision ,$x,$y,$z,$elcurr,$coln // $stelem, layer=$curr_layer\n";
            }
            $bfn ++; 
            print "$bfn $coln\n"; # print the b-file entry
            &allocate($elcurr, $x, $y,$z);
        } # else same element - ignore
    } else { # undefined
        &allocate($elcurr, $x, $y,$z);
    } # undefined
} # investigate
#--------
sub allocate {
    my ($elcurr, $x, $y, $z) = @_;
    $coords{"$x,$y,$z"} = $elcurr;
    $elems[$elcurr] = "$x,$y,$z";
    if ($mode >= 1) {
        print "# coords ,$x,$y,$z,$elcurr\n";
    }
} # allocate

Input Collatz sequences

The program reads the first 10000 Collatz sequences from a070165.txt:

content of https://oeis.org/A070165/a070165.txt follows:
This file has 10000 rows showing the following for each row:
  a) Starting number for Collatz sequence ending with 1 (a.k.a. 3x+1 sequence).
  b) Number of terms in sequence (a.k.a. number of halving and tripling steps to reach 1).
  c) Actual sequence as a vector.

1/4: [1, 4, 2, 1]
2/2: [2, 1]
3/8: [3, 10, 5, 16, 8, 4, 2, 1]
4/3: [4, 2, 1]
5/6: [5, 16, 8, 4, 2, 1]
6/9: [6, 3, 10, 5, 16, 8, 4, 2, 1]
7/17: [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
8/4: [8, 4, 2, 1]
9/20: [9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
10/7: [10, 5, 16, 8, 4, 2, 1]
11/15: [11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
12/10: [12, 6, 3, 10, 5, 16, 8, 4, 2, 1]
13/10: [13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
14/18: [14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
15/18: [15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1]
16/5: [16, 8, 4, 2, 1]
17/13: [17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
18/21: [18, 9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
19/21: [19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
20/8: [20, 10, 5, 16, 8, 4, 2, 1]
...
10000/30: [10000, 5000, 2500, 1250, 625, 1876, 938, 469, 1408, 704, 352, 176, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

makefile

With mode=0 the program generates the b-file for A291939 only. With mode=1 it outputs additional comment lines which can be used to build a visualization of the underlaying 3D structure. The generation of the files is controlled by a Unix makefile:

#!make

# draw Collatz sequences, OEIS A070165 -> A291939
# @(#) $Id$
# 2018-03-23, Georg Fischer
#----------
MODE=0
SIZE=100
all: bfile
#----------
wget:
	wget https://oeis.org/A070165/a070165.txt
bfile:
	perl a291939.pl $(MODE) a070165.txt | tee b291939.txt
a291939-3d.js: makefile a291939.pl a070165.txt
	grep -E "^[0-9]" a070165.txt | head -$(SIZE) > cs100.tmp
	perl a291939.pl 1 cs100.tmp > mode1.tmp 
	grep -E "# coords" mode1.tmp | cut -d " " -f 3 >> $@
	echo var vec = [0,0,0,1 > $@
	perl a291939.pl 1 cs100.tmp | grep -E "# coords" | cut -d " " -f 3 >> $@
	echo ]\; >> $@
	echo var colls = [0,0,0,1,1 >> $@
	grep -E "# collision" mode1.tmp | cut -d " " -f 3 >> $@
	echo ,0,0,0,0,0]\; >> $@
	cat $@
deploy: 
	echo either make deploy-windows or make deploy-linux
deploy-windows:
	cp -v *.js *.html c:/users/gfis/xampp/htdocs/threejs
deploy-linux:
	sudo cp -v *.js *.html        /var/www/html/threejs
	sudo chown -R georg:www-data  /var/www/html/threejs/*
	sudo chmod 750                /var/www/html/threejs/* 

3D Visualization

For the visualization, the Javascript library Three.js is used. There is

• a variable data file a291939-3d.js which is generated by the makefile above, and
• a fixed frame a291939-3d.html for the display of the sequence which is shown below.

Once that HTML file with the Javascript functions has been loaded (that may take about 15 s), the generated 3D structure is shown as a sequence of colored cubes, with the Collatz sequence elements written inside. The interesting part is the region with red elements in the upper left. Each layer has a different color, and the beginnings of the layers (which form sequence A291939) are highlighted with white edges and a pointer to the corresponding CS sequence number (1, 12, 19, 27, 37 ...). The structure can be

• rotated by clicking and moving the mouse,
• zoomed by turning the mouse wheel,
• shifted up, down, left and right by the cursor arrow keys.

Only the first 100 Collatz sequences were processed for this example (parameter SIZE in the makefile). The resulting structure is already rather extended because of the CS sequences with more than 100 elements (for example 27).

The HTML file must be stored on a webserver together with the Javascripts from the threejs.org distribution which are referenced at the beginning of the body of a291939-3d.html.

<!DOCTYPE html>
<html lang="en">
<!--3D visualization of OEIS A291939 
    @(#) $Id$
    2018-03-25, dr.georg.fischer@gmail.com
-->
<head>
    <title>A291939.3D</title>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, user-scalable=no, minimum-scale=1.0, maximum-scale=1.0">
    <style>
        body {
            color: #ccc;
            font-family:Monospace;
            font-size:13px;
            text-align:center;
            font-weight: bold;
            background-color: #fff;
            margin: 0px;
            overflow: hidden;
        }
        #info {
            color:#ccc;
            position: absolute;
            top: 0px; width: 100%;
            padding: 5px;
        }
        a {
            color: red;
        }
    /*
    */
    </style>
</head>
<body>
    <div id="container"></div>
    <div id="info">
        <a href="http://threejs.org" target="_blank" rel="noopener">three.js</a> - OEIS A291939 by Georg Fischer
    </div>
    <script src="js/three.min.js"></script>
    <script src="THREE.MeshLine.js"></script>
    <script src="js/renderers/Projector.js"></script>
    <script src="js/controls/OrbitControls.js"></script>
    <script src="js/Detector.js"></script>
    <script src="js/libs/stats.min.js"></script>
    <script src="a291939-3d.js"></script>
    <script>
    var xmax = 0;
    var ymax = 0;
    var zmax = 0;
    </script>
    <script>
    function world(scene, myfont) {
        var center = new THREE.Vector3(0, 0, 0);
        var points = [];
        var elems  = [];
        var layers = []; // 
        xmax   = 0;
        ymax   = 0;
        zmax   = 0;
        var i = 0;
        while (i < vec.length) { // determine maximums
            var xcor = vec[i ++]; if (xcor > xmax) { xmax = xcor; }
            var ycor = vec[i ++]; if (ycor > ymax) { ymax = ycor; }
            var zcor = vec[i ++]; if (zcor > zmax) { zmax = zcor; }
            i ++;
        } // while maximums
        var sizex   = parseInt(xmax * 0.66); // slightly shifted to the left
        var sizey   = parseInt(ymax / 2);
        var sizez   = parseInt(zmax / 2);
        var width  = 1; // of the cubes
        var fact = 10;
        i = 0;
        while (i < vec.length) {
            var xcor = vec[i ++];
            var ycor = vec[i ++];
            var zcor = vec[i ++];
            var elem = vec[i ++];
            layers.push(zcor);
            elems.push(elem);
            var x = center.x + (xcor - sizex) * fact;
            var y = center.y + (ycor - sizey) * fact;
            var z = center.z + (zcor - sizez) * fact;
            points.push(new THREE.Vector3(x, -y, z));
        } // while i
    
        var materials = [
            new THREE.MeshBasicMaterial({ color: 0xffffff, overdraw: 0.5 }),
            new THREE.MeshBasicMaterial({ color: 0xffffff, overdraw: 0.5 })
            ];
        var color3 = new THREE.Color(0xffffff);
        var icoll = 0; // index for collisions
        for (i = 0; i < points.length - 1; i ++) {
            var group  = new THREE.Group();
            var elem = elems[i];
            color3.setHSL((0.1 + layers[i] * 0.7) / zmax, 1.0, 0.5);
            var geometry = new THREE.BoxGeometry(width * fact, width * fact, width * fact);
            geometry.translate(points[i].x, points[i].y, points[i].z);
            var material = new THREE.MeshBasicMaterial(
                    { color: color3, opacity: 0.4, transparent: true} );
            var matwhite = new THREE.MeshBasicMaterial(
                    { color: 0xffffff, opacity: 0.4, transparent: false} );
            group.add(new THREE.Mesh(geometry, material));
            if (elem == colls[icoll+ 3]) { // element moves to next layer
                var line = new THREE.LineSegments(new THREE.EdgesGeometry(geometry)
                        , new THREE.LineBasicMaterial({ color: 0xffffff }));
                group.add(line);
                var geop = new THREE.Geometry();
                geop.vertices.push(new THREE.Vector3(points[i].x + fact*0.5, points[i].y + fact*0.5, points[i].z+ fact*0.5));
                var endp = new THREE.Vector3(points[i].x + fact*2, points[i].y + fact*2, points[i].z+ fact*2);
                geop.vertices.push(endp);
                line = new THREE.Line(geop, new THREE.LineBasicMaterial({ color: 0xffffff }))
                group.add(line);
                var geot = new THREE.TextGeometry(colls[icoll + 4], 
                        { font: myfont, size: fact/3, height: fact/16, curveSegments: 8 });
                geot.translate
                    ( points[i].x + fact*2
                    , points[i].y + fact*2
                    , points[i].z + fact*2
                    );
                group.add(new THREE.Mesh(geot, matwhite));
                icoll += 5;
                // next layer
            } else {
                var line = new THREE.LineSegments(new THREE.EdgesGeometry(geometry)
                        , new THREE.LineBasicMaterial({ color: color3 }));
                group.add(line);
            }
            var geometry2 = new THREE.TextGeometry(elem, 
                    { font: myfont, size: fact/3, height: fact/16, curveSegments: 8 });
            geometry2.translate
                    ( points[i].x - fact / 3
                    , points[i].y
                    , points[i].z - fact / 4
                    );
            group.add(new THREE.Mesh(geometry2, materials));
            scene.add(group);
        } // for i 
    } // world
    </script>
    <script>        
        if ( ! Detector.webgl ) {
            Detector.addGetWebGLMessage();
        }
        var stats;
        var camera;
        var controls;
        var scene;
        var renderer;
        var loader = new THREE.FontLoader();
        loader.load( 'fonts/helvetiker_regular.typeface.json', function ( font ) {
            // all remaining main code must be placed in this block
            init( font );
            // render(); // remove when using next line for animation loop (requestAnimationFrame)
            animate();
        } ); // load

        function init( myfont ) {
            scene = new THREE.Scene();
            scene.background = new THREE.Color( 0x000000 ); // 0xcccccc );
            world( scene, myfont );
            renderer = new THREE.WebGLRenderer();
            renderer.setPixelRatio( window.devicePixelRatio );
            renderer.setSize( window.innerWidth, window.innerHeight );
            var container = document.getElementById( 'container' );
            container.appendChild( renderer.domElement );
            camera = new THREE.PerspectiveCamera( 33, window.innerWidth / window.innerHeight, 1, 10000 );
            camera.position.z = 20 * xmax;
            controls = new THREE.OrbitControls( camera, renderer.domElement );
            controls.addEventListener( 'change', render ); // remove when using animation loop
            // enable animation loop when using damping or autorotation
            controls.enableDamping = true;
            controls.dampingFactor = 0.25;
            controls.enableZoom = true;
            
            if (false) { // lights
                var lights = [];
                lights[ 0 ] = new THREE.PointLight( 0xffffff, 1, 0 );
                lights[ 1 ] = new THREE.PointLight( 0xffffff, 1, 0 );
                lights[ 2 ] = new THREE.PointLight( 0xffffff, 1, 0 );
                lights[ 0 ].position.set( 0, 200, 0 );
                lights[ 1 ].position.set( 100, 200, 100 );
                lights[ 2 ].position.set( - 100, - 200, - 100 );
                scene.add( lights[ 0 ] );
                scene.add( lights[ 1 ] );
                scene.add( lights[ 2 ] );
            } else { // lights                         
                var 
                light = new THREE.DirectionalLight( 0xffffff );
                light.position.set( 1, 1, 1 );
                scene.add( light );
                light = new THREE.DirectionalLight( 0x002288 );
                light.position.set( -1, -1, -1 );
                scene.add( light );
                light = new THREE.AmbientLight( 0x222222 );
                scene.add( light );
            } // lights
            stats = new Stats();
            container.appendChild( stats.dom );
            window.addEventListener( 'resize', onWindowResize, false );
        } // init
        
        function onWindowResize() {
            camera.aspect = window.innerWidth / window.innerHeight;
            camera.updateProjectionMatrix();
            renderer.setSize( window.innerWidth, window.innerHeight );
        }
        function animate() {
            requestAnimationFrame( animate );
            controls.update(); // required if controls.enableDamping = true, or if controls.autoRotate = true
            stats.update();
            render();
        }
        function render() {
            var time = Date.now() * 0.0001;
            time = 0.0;
            for ( var i = 0; i < scene.children.length; i ++ ) {
                var object = scene.children[i];
                object.rotation.y = time; // * ( i % 2 ? 1 : -1 );
            }
            renderer.render( scene, camera );
        }
    </script>
</body>
</html>