Month: December 2020

I am working through the practice problems in Forth Application Techniques (6th ed.) and something struck my curiosity. Page 51 has a problem asking me to define a word called avalanche that computes an avalanche numbers sequence. The rules:

• If the number on the stack is odd, multiply it by 3 and add 1.
• If the number on the stack is even, divide it by two.
• If the number on the stack is one, stop.

My solution was

: even? ( n -- flag ) odd? 0= ;
: avalanche begin dup 1 <> while dup even? if 1 rshift dup . else 3 * 1 + dup . then repeat ;

Which gives, e.g.,

17 avalanche <cr> 52 26 13 40 20 10 5 16 8 4 2 1  ok

I was curious what sequences resulted, starting with other numbers, so I added this word:

: avalanche-range ?do i dup . avalanche cr loop ;

The first twenty numbers give:

20 1 avalanche-range <cr> 1 
2 1 
3 10 5 16 8 4 2 1 
4 2 1 
5 16 8 4 2 1 
6 3 10 5 16 8 4 2 1 
7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 
8 4 2 1 
9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 
10 5 16 8 4 2 1 
11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 
12 6 3 10 5 16 8 4 2 1 
13 40 20 10 5 16 8 4 2 1 
14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 
15 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1 
16 8 4 2 1 
17 52 26 13 40 20 10 5 16 8 4 2 1 
18 9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 
19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 
 ok

So, it seems that avalanche number sequences rise and fall, but ultimately come back down and terminate on 1, in an avalanche-like effect. Observation shows that all sequences end up being supersets of other sequences at some point, with the exception of the base sequence [ 1 ]. If it is true that all sequences do settle on 1, then consequently all positive whole numbers are included in some sequence.

I got the idea to map some of the sequences out as a tree, with the sequences working inwards (from branch to root). A branch consists of a sequence of numbers being divided in half, and a branch merges into another branch where an odd number must be multiplied. Since we are dealing with infinitely long branches, I made some practical limitations of having the “trunk” limited to 12 nodes, the main branches limited to 6 nodes, the third set of branches limited to 3 nodes, and not exploring the branches any more deeply than those three levels. We start with the trunk being the sequence [ 5096, 2048 … 2, 1 ], a sequence familiar to computer programmers. This was the result:

The graph has a tantalizing hint of pattern, but not consistent pattern. You see the six nodes of one level-two branch do not have level-three branches. Also the node with value 5096 does not branch out, as you might intuitively suppose.

Again assuming that all sequences converge on 1, then all whole numbers are in some branch. Yet no branch (referring to a single straight line) shares a number with any other branch, except at the points of branching off.

I did a quick search on startpage.com for avalanche number sequences but was unable to find more information on this subject. If somebody has a good link, please share it in the comments.