Avalanche Numbers

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.

Bit Twiddling in Forth

Bit twiddling is fundamentally the same as in other programming languages. However, Forth allows us to change base for easy interactive bit twiddling:

: binary 0x2 base ! ;

To set a bit (to 1) we use bit-wise or. E.g.

binary 10100011 00001000 or . <cr> 10101011  ok

To clear a bit, we need bit-wise and.

binary 10100011 11011111 and . <cr> 10000011  ok

Toggling a bit uses bit-wise xor. Here we toggle two bits:

binary 10100011 00110000 xor . <cr> 10010011  ok

We can pull the value of a bit with and. In Forth, zero values are false, while non-zero values are true.

binary 10100011 00100000 and [if] ." bit is set!" [else] ." bit is clear!" [then] <cr> bit is set! ok

We can pull, say, the second byte out of a 16 bit word with a mask and the appropriate bit-wise rshift.

binary 1001010111001011 hex ff00 and 8 rshift binary . <cr> 10010101  ok

The following words are made available for convenience:

\ Copyright 2020 Christopher Howard

\ Licensed under the Apache License, Version 2.0 (the "License");
\ you may not use this file except in compliance with the License.
\ You may obtain a copy of the License at

\     http://www.apache.org/licenses/LICENSE-2.0

\ Unless required by applicable law or agreed to in writing, software
\ distributed under the License is distributed on an "AS IS" BASIS,
\ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
\ See the License for the specific language governing permissions and
\ limitations under the License.

: binary 0x2 base ! ;

: bit ( w n -- f ) 1 swap lshift and ;

: set ( w n -- w ) 1 swap lshift or ;

: clear ( w n -- w ) 1 swap lshift invert and ;

: toggle ( w n -- w ) 1 swap lshift xor ;

: byte0 ( w -- c ) 0xff and ;

: byte1 ( w -- c ) 0xff00 and 0x8 rshift ;

Example use:

binary 10010101 dup dup decimal 2 bit . 3 bit . 4 bit . <cr> 4 0 16 ok
binary 10010101 decimal 2 set 3 set binary . <cr> 10011101  ok
binary 10010101 decimal 2 clear 3 clear binary . <cr> 10010001  ok
binary 10010101 decimal 2 toggle 3 toggle binary . <cr> 10011001  ok
binary 1001010111001011 byte0 . <cr> 11001011  ok
binary 1001010111001011 byte1 . <cr> 10010101  ok

XL6009 Voltage Boost Converters

XL6009 Boost Converter in NPN Transistor Switch

The large module is the the XL6009 Boost Converter, which is boosting a 5 V source to 21 V. There is a small screw on it that you can turn to select other voltages (i think it goes up to 35 V).

It is tied into an NPN transistor, set up for switching. The base of the switch is driven by a 5 V signal from the Uno, with a 10k resistor, which turns on the collector-emitter path, which being driven by the 21 V source, with a 1k resistor, and providing current for the LED.

I needed a 21 V source for my EPROM programming project, but needed it to be controlled by a 5 V AVR pin.

A pack of XL6009 Boost Converters is available for about $12 from Amazon.

EPROM Reader Rev. 2

Slightly improved hand-made reader for our old 32K and 64K EPROMs

The original design was rather painful to work with, and ugly, so I put this together which is a little nicer. The button, switch, chip socket, and cable socket are one ElectroCookie Snappable PCB. I like those PCBs as they have three-hole strips.

I found some decent sockets that fit the old chips (2732A and 2764 EPROMs). In retrospect, I maybe should have got a zero-insertion force sockets where you just drop the chip in and pull the lever to tighten.

With this setup, I can have one ribbon cable going from this board to the Mega. I didn’t know what kind of cable or cable-connectors I needed to fit this 36 pin setup, so I made a cable using the commonplace loose-end Arduino ribbon cable. The pins bend rather easily, but it is better than the previous setup.

reader connected to Mega

I’m still using magnet wire – for which I’ve developed a love/hate relationship. The magnet wire looks nice, is easy to cut, and one roll lasts pretty much forever. But it is rather a pain because (1) you have to boil the coating off the ends of each piece of wire with solder before you use it, and (2) you have to put a blob off solder in the hole first and then reheat it to stick the magnet wire in. Regular insulated wire, that is sized correctly for the hole, is sounding very appealing at this point. But, it works.

Magnet wire on bottom of PCB

Something fun I learned in the process: I wrote a Forth script for testing the pin connections. The output of the script comes from Mega over UART (serial), but I used vte style escape codes to keep the display fixed and updated on one part of the terminal screen.

Rev. 2 board Forth testing script