Sequences A232559 and A232561, Spanning Trees of N
OEIS sequences A232559 and A232561 are permutations of ℕ (the natural numbers) arranged as if reading rows of a tree that organises the numbers by how they can be reached through repeated application of simple functions, starting at 0.
For A232559 the allowed functions are:
- Even x can be replaced with x+1
- Positive x can be replaced with 2x
Every natural number can be reached in exactly one way by this process. Here is a "tree" arrangement of numbers, with the starting value 0 at the top, and each number x joined with child nodes valued x+1 and/or 2x, and putting the smaller one first whenever there is a branch:
0 | 1 | 2.. / \ 3' `4. / / \ 6 5 `8 / \ | / \ 7 12 10 9 16 | | \ / | | | \ 14 13 24 11 20 18 17 32 /| | |\ | |\ |\ | |\ . . . (13 numbers) . . .Scanning across each row we get the sequence: 0, 1, 2, 3, 4, 6, 5, 8, 7, 12, 10, 9, 16, 14, 13, 24, 11, 20, 18, 17, 32, 15, 28, 26, 25, 48, 22, 21, 40, 19, 36, 34, 33, 64, ... which is A232559 in the OEIS except for the omission of the leading 0.
Looking at the path from 0 to a number in the tree and considering the binary representations of each number, we see that the transformation rules are equivalent to:
- Change a final digit 0 to 1
- Add a digit 0 at the end
and there is clearly only one way to get from 0 to any given number, related directly to its binary representation.
The number of nodes at each level of the tree is: 1, 1, 2, 3, 5, 8, 13, ... (the Fibonacci numbers).
Going through the rows from right-to-left instead, we get A48679 (this time including the root 0) and is merely the same tree but putting each 2x child to the left of its x+1 sibling if any:
0 | 1 | 2.. / \ ,4 `3. / \ \ 8 `5 `6 / \ | / \ 16 9 10 12 7 / | | | \ / | | . . . (8 numbers) . . .Expressed in binary, the terms of A48679 are: 0, 1, 10, 100, 11, 1000, 101, 110, 10000, 1001, 1010, 1100, 111, ... and can be obtained by taking the "Fibbinary numbers" A3714 and replacing any occurrence of 01 with 1.
The functions being used the generate the natural numbers in this way are two of the simplest functions in ℕ->ℕ and arise in many other contexts. In the hierarchy of fast-growing functions they are f0(x) = x+1 and f1(x) = x×2; they are also the functions H1(n) and Hω(n) in the Hardy hierarchy.
The Base-3 Variant
Going back to the first sequence, let's change the rules to these:
- Any x of the form 3n or 3n+1 can be replaced with x+1
- Positive x can be replaced with 3x
This also generates a tree that contains each natural number exactly once:
0 | .1.. / \ 2 `3.. / / \ 6 4 `9.. / \ / \ | \ 7' 18 5 12 10 `27. /| / | | | \ | \ | \ 8 21 19 54 15 13 36 11 30 28 81 | |\ |\ |\ |\ |\ |\ | |\ |\ |\ . . . (20 numbers) . . .Scanning across each row we get the sequence: 0, 1, 2, 3, 6, 4, 9, 7, 18, 5, 12, 10, 27, 8, 21, 19, 54, 15, 13, 36, 11, 30, 28, 81, 24, 22, 63, ... which is A232561 in the OEIS (again omitting the leading 0). This time the length of each row of the tree is 1, 2, 3, 6, 11, 20, 37, 68, ... (A1590, the Tribonacci numbers) and our rules have a similar interpretation in terms of base-3 representations:
- Add 1 to a final digit 0 or 1
- Add a digit 0 at the end
Youtube maths teacher Domotro (Dimitri Zucker) talks about both of these trees, and their generalisation to other bases, in this video, referring to the iterative process as "numberation".
This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2024 Aug 13.
s.30