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
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.jswhich is generated by themakefileabove, and - a fixed frame
a291939-3d.htmlfor 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>