Numeral Systems But 2D

Introduction to 3-smooth integer representations

Intro

You’ve probably seen binary (e.g. 10100), trinary (e.g. 2101), or even hexadecimal (e.g. A1F7264). I call these 1D integer representations because they represent integers and can all be written neatly in a row. In this article we represent integers using two dimensions.

\(\begin{array}{|c|c|c|} \hline 0 & 0 & 1 & 0\\ \hline 0 & 1 & 0 & 0\\ \hline 0 & 0 & 1 & 0\\ \hline 1 & 0 & 0 & 0\\ \hline \end{array}\)

We’ll see that the extra degree of freedom makes some things more easy, but other things (like knowing if two numbers are the same) much harder.

Recommended Background

Recommend some familiarity with base-n representations.

Motivation and Definition

(Throughout, we’ll only talk about whole numbers, though an extension to decimals is natural.)

So you know numbers, right? Base-10 numbers (arabic numerals¹) improve over earlier numeral systems², by introducing place value - each digit is 10X the previous digit:

\(\begin{array}{|c|c|c|c|c|c|} \hline \cdots & 10^4 & 10^3 & 100 & 10 & 1 \\ \hline \end{array}\)

This lets us easily represent arbitrarily large numbers, and makes arithmetic easy. But naturally this leads us to ask if 10^n are the best place values. Though some exotic choices exist,³ the best options for space efficiency and arithmetic ease seem to be place values that grow exponentially, where the n-th digit represents b^n.⁴ For example, base-3 uses digits 0, 1 and 2 uses powers of 3 for place value.

\(\begin{array}{|c|c|c|c|c|c|} \hline \cdots & 3^4 & 3^3 & 9 & 3 & 1 \\ \hline \end{array}\)

So that “210” is understood to mean 2*9 + 1*3 + 0*1 = 12. We can use our traditional arithmetic algorithms for these.

\(\begin{array}{r} 2102_3 \\ \times 122_3 \\ \hline 11211_3 \\ 112110_3 \\ + 210200_3 \\ \hline 1111221_3 \\ \end{array}\)

If this is your first time encountering this idea, then it may take some time to digest.⁵

Choosing a different base makes some things easier. For example, multiplying by three or nine in base-3 is much easier (2212_3 X 100_3 = 221200_3). But other things become harder. For example, ten in base-3 is 101_3; so multiplying by ten now requires work.

Given that there’s all these trade-offs, one hopes that you can get a best-of-both-worlds scenario. In particular, I found “3-smooth⁶ representations” when I was looking for numbers that were easy either to multiply by 2 (easy in base-2) or to multiple by 3 (easy in base-3). This is somewhat easy in base-6, but we can do better, if we just let numbers be two-dimensional. Here I define place value by:

\(\begin{array}{|c|c|c|c|c|c|} \hline 1 & 2 & 4 & 2^3 & 2^4 & \cdots \\ \hline 3 & 6 & 12 & 2^3\cdot3 & 2^4\cdot3 & \cdots \\ \hline 9 & 18 & 36 & 2^3\cdot9 & 2^4\cdot9 & \cdots \\ \hline 3^3 & 2\cdot3^3 & 4\cdot3^3 & 2^3\cdot3^3 & 2^4\cdot3^3 & \cdots \\ \hline 3^4 & 2\cdot3^4 & 4\cdot3^4 & 2^3\cdot3^4 & 2^4\cdot3^4 & \cdots \\ \hline \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \hline \end{array}\)

Now the number in the intro,

\(\begin{array}{|c|c|c|} \hline 0 & 0 & 1 & 0\\ \hline 0 & 1 & 0 & 0\\ \hline 0 & 0 & 1 & 0\\ \hline 1 & 0 & 0 & 0\\ \hline \end{array}\)

Can be understood to mean 4 + 6 + 36 + 27 = 73.

A few things to note about this notation:
- This grows by powers of 2 in one dimension and and powers of 3 in the other. I’ll focus on this notation for this article, but you may choose different bases, or even add more dimensions!
- I flipped this, so that going left-to-right increases place value; this makes this more familiar to matrix notation.
- I only allow digits of 0 and 1. This is a choice, which has the advantage of making each row a binary number. (Though I’ll occasionally write a “2” as an intermediate step before I carry.)
-We write any whole number as a 3-smooth representation, by just writing it in the first row as binary.

As desired, multiplication by 2 is easy (shift the whole matrix right by one), and multiplication by 3 is easy (shift the whole matrix down by one).

Note about “easy”: I use the term “easy” a few times in this article, but this isn’t precisely defined. Roughly it means that doing calculations by hand don’t require much brain power. We might hope that this translates to computational ease. It sorta does in a vacuum, but in practice, the techniques here are unlikely to optimize any algorithms. Largely this is because binary-based CPUs benefit from decades of optimization. Multiplication by 3 is probably not what’s making your program go slow. Though 3-smooth representation do make certain problems easier, they’re probably not worth decades of optimization.

Basic Arithmetic

Because each row is binary, we can do usual binary carries rightward. This makes addition feel familiar. (In fact, it’s literally binary addition of each row.)

\(\begin{array}{|c|c|c|} \hline 0 & 0 & 1 & 0\\ \hline 0 & 1 & 0 & 0\\ \hline 0 & 0 & 1 & 0\\ \hline 1 & 0 & 0 & 0\\ \hline \end{array} + \begin{array}{|c|c|c|} \hline 0 & 1 & 1 & 0\\ \hline 0 & 1 & 1 & 0\\ \hline 0 & 1 & 0 & 0\\ \hline 0 & 1 & 1 & 0\\ \hline \end{array} = \begin{array}{|c|c|c|} \hline 0 & 1 & 0 & 1\\ \hline 0 & 0 & 0 & 1\\ \hline 0 & 1 & 1 & 0\\ \hline 1 & 1 & 1 & 0\\ \hline \end{array}\)

Multiplying is also familiar. When you multiple 1-dimensional representations, say 123*456, you break up one of the numbers into its digits, 123*400 + 123*50 + 123*6. The same idea works here.

Look at this representation of 22, for example:

\(\begin{array}{|c|c|} \hline 0&0&1\\ \hline 0&0&0\\ \hline 0&1&0\\ \hline\end{array} = \begin{array}{|c|c|} \hline 0&0&1\\ \hline 0&0&0\\ \hline 0&0&0\\ \hline\end{array} + \begin{array}{|c|c|} \hline 0&0&0\\ \hline 0&0&0\\ \hline 0&1&0\\ \hline\end{array}\)

Multiplication by each of the terms on the right-hand side is easy. For the first term, this is multiplication by 4, which is just two shifts right. The second term is multiplication by 18, which can be done with two shifts down and one shift right. So multiplication by 22 is just making copies of your matrix at each of the bits.

\(\begin{array}{|c|c|} \hline 1&1&0\\ \hline 1&0&0\\ \hline 1&0&0\\ \hline\end{array}\times\begin{array}{|c|c|} \hline 0&0&1\\ \hline 0&0&0\\ \hline 0&1&0\\ \hline\end{array} = \begin{array}{|c|c|} \hline 0&0&1&1\\ \hline 0&0&1&0\\ \hline 0&0&1&0\\ \hline\end{array} + \begin{array}{|c|c|} \hline 0&0&0\\ \hline 0&0&0\\ \hline 0&1&1\\ \hline 0&1&0\\ \hline 0&1&0\\ \hline\end{array}= \begin{array}{|c|c|} \hline 0&0&1&1\\ \hline 0&0&1&0\\ \hline 0&1&0&1\\ \hline 0&1&0&0\\ \hline 0&1&0&0\\ \hline\end{array}\)

To show this same calculation more clearly, I’ll make the two summands the same shape.

\( \begin{array}{|c|c|} \hline 0&0&1&1\\ \hline 0&0&1&0\\ \hline 0&0&1&0\\ \hline 0 & 0 & 0 & 0\\ \hline 0 & 0 & 0 & 0\\ \hline\end{array} + \begin{array}{|c|c|} \hline 0&0&0&0\\ \hline 0&0&0&0\\ \hline 0&1&1&0\\ \hline 0&1&0&0\\ \hline 0&1&0&0\\ \hline\end{array}= \begin{array}{|c|c|} \hline 0&0&1&1\\ \hline 0&0&1&0\\ \hline 0&1&0&1\\ \hline 0&1&0&0\\ \hline 0&1&0&0\\ \hline\end{array}\)

For multiplication, it helps me to keep track of one of the original numbers in the result. Here I wrote an * to mark the first multiplicand, and I make sure that I have two stacked 1s two to the right of each starred number on the product.

\(\begin{array}{|c|c|} \hline 1 & 0 & 0 \\ \hline 0 & 0 & 1 \\ \hline 0 & 1 & 0 \\ \hline\end{array}\times\begin{array}{|c|c|} \hline 0 & 0 & 1 \\ \hline 0 & 0 & 1 \\ \hline\end{array}=\begin{array}{|c|c|} \hline 0^{*} & 0 & 1 & 0 & 0\\ \hline 0 & 0 & 1^{*} & 0 & 1 \\ \hline 0 & 0^{*} & 0 & 1 & 1 \\ \hline 0 & 0 & 0 & 1 \\ \hline\end{array} \)

Non-uniqueness

I mentioned above that all whole numbers can be written using only the first row, so what are all these other numbers? Of course, they’re the same numbers. Above we saw 22 written as the sum of 4 and 18, but this can also we written as

\(\begin{array}{|c|c|} \hline 0 & 1 & 1 & 0 & 1 & 0 \\ \hline 0 & 0 & 0 & 0 & 0 & 0\\ \hline \end{array}\)

This poses a non-uniqueness problem that we don’t have for 1D representations.⁷ One of the challenges of 2D representations is that it’s hard to tell when two numbers are the same.

We introduce here “transformations,” which will let you change one representation of a number to another representation. For example,

\(\begin{array}{|c|c|} \hline \it1 & \it1 \\ \hline \bf1 & 0 \\ \hline\end{array}\)

This is a way of expressing that whenever you have a 1, you can rewrite it as two 1s in the row above it. In the corner this makes sense (3 = 1 + 2), but you can move this anywhere because the moving right m and down n corresponds to the relationship

\(3\cdot 2^m3^n = 2\cdot 2^m3^n + 1\cdot 2^m3^n\)

So for example:

\(\begin{array}{|c|c|c|} \hline 0 & 0 & 1 & 0\\ \hline 0 & 1 & 0 & 0\\ \hline 0 & 0 & 1 & 0\\ \hline 1 & 0 & 0 & 0\\ \hline\end{array}= \begin{array}{|c|c|c|} \hline 0 & \it0 & \it1 & 0\\ \hline 0 & \bf1 & 0 & 0\\ \hline 0 & 0 & 1 & 0\\ \hline 1 & 0 & 0 & 0\\ \hline\end{array}= \begin{array}{|c|c|c|} \hline 0 & 1 & 0 & 1\\ \hline 0 & 0 & 0 & 0\\ \hline 0 & 0 & 1 & 0\\ \hline 1 & 0 & 0 & 0\\ \hline\end{array}\)

Notice that I had to handle the carry as part of this transformation. Except for carries these relationships are symmetric. We’ll always use bold to indicate the bits that we’re moving and italics to indicate the bits that we’re moving it to. In many of the calculations below, we use this notation to anticipate the next step.

You can come up with infinitely many such transformations, like:

\(\begin{array}{|c|c|} \hline \bf1 & 0 & \it 1 \\ \hline \bf1 & 0 & 0\\ \hline\end{array} \quad\text{or}\quad \begin{array}{|c|c|} \hline \bf1 & 0 & \it 1 \\ \hline \it1 & \bf1 & 0\\ \hline\end{array} \quad\text{or}\quad \begin{array}{|c|c|} \hline \bf1 & \it1 & \bf1 \\ \hline 0 & \it1 & 0\\ \hline\end{array}\)

Or even whole families of transformations:

\(\begin{array}{|c|c|} \hline \bf 1 & 0 & \it 1 \\ \hline \bf 0 & \it 1 & 0\\ \hline \bf 0 & \it 1 & 0\\ \hline \vdots &\vdots&\\ \hline \bf 0 & \it 1 & 0\\ \hline \bf 1 & 0 & 0\\ \hline\end{array}\)

Watch how we can use these rules to change the shape of numbers:

\(\begin{array}{|c|c|} \hline 1 & 1 & 1 \\ \hline 1 & 1 & 0 \\ \hline 1 & 0 & 0 \\ \hline\end{array}= \begin{array}{|c|c|} \hline 1 & 1 & 1 \\ \hline \bf1 & \bf1 & 0 \\ \hline \it1 & 0 & 0 \\ \hline\end{array}= \begin{array}{|c|c|} \hline 1 & \bf1 & \bf1 \\ \hline 0 & \it0 & 0 \\ \hline 0 & 1 & 0 \\ \hline\end{array}= \begin{array}{|c|c|} \hline 1 & 0 & 0 & 0 \\ \hline 0 & \bf1 & 0 & \it0\\ \hline 0 & \bf1 & 0 & 0\\ \hline\end{array}=\begin{array}{|c|c|} \hline 1 & 0 & 0 & 0 \\ \hline 0 & 0 & 0 & 1\\ \hline 0 & 0 & 0 & 0\\ \hline\end{array}\)

This may be fun to a Sudoku aficionado, but these rules would surely be taught in elementary schools if our ancestors had chosen a more pathological counting system.

Notably, this rule above (through repeated application) allows us to algorithmically transform any number into binary.⁸

\(\begin{array}{|c|c|} \hline \it1 & \it1 \\ \hline \bf1 & 0 \\ \hline\end{array}\)

Collatz Conjecture

Collatz Conjecture⁹ (or the 3x+1 problem) centers around an operation on natural numbers, x, where you divide by two if the number is even, and calculate 3x+1 if it’s odd.

\(f(x) = \left\{\begin{array}{rcl}x/2&;&x\text{ is even}\\ 3x+1&;&x\text{ is odd}\end{array} \right.\)

Collatz conjecture (unproven) states that if you repeatedly apply this function, you’ll eventually reach 1. Generally this may take a lot of work to reach 1. For example, for 7, this looks like 7 → 11 → 34 → 17 → 52 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1.

This is a calculation that 3-smooth representations are well-design for. 3x+1 is as easy as shifting down and adding a 1 in the top-left corner. A whole number is 1 if and only if there’s a single 1 in the top-left corner. A whole number is even if and only if there are an even number of 1s in the left column. (Why?) And dividing by two in that case can be done by applying this transformation on all pairs of the left column to zero that column out:

\(\begin{array}{|c|c|} \hline \bf 1 & 0 & \it 1 \\ \hline \bf 0 & \it 1 & 0\\ \hline \bf 0 & \it 1 & 0\\ \hline \vdots &\vdots&\\ \hline \bf 0 & \it 1 & 0\\ \hline \bf 1 & 0 & 0\\ \hline\end{array}\)

Let’s see how that same calculation goes now:

\(\begin{array}{|c|c|} \hline 1 & 1 & 1 \\ \hline\end{array} \rightarrow \begin{array}{|c|c|} \hline \bf1 & 0 & \it0 \\ \hline \bf1 & 1 & 1 \\ \hline\end{array} \rightarrow \begin{array}{|c|c|} \hline 0 & 1 \\ \hline 1 & 1 \\ \hline\end{array} \rightarrow \begin{array}{|c|c|} \hline \bf1 & 0 & \it0\\ \hline \bf0 & \it1 \\ \hline \bf1 & 1 \\ \hline\end{array} \rightarrow \begin{array}{|c|c|} \hline 0 & 1 \\ \hline 0 & 1 \\ \hline 1 & 0 \\ \hline\end{array}\rightarrow\)

\( \\ \begin{array}{|c|c|} \hline \bf1 & 0 & \it0 \\ \hline \bf0 & \it1 \\ \hline \bf0 & \it1 & \\ \hline \bf1 & 0 \\ \hline\end{array}\rightarrow\begin{array}{|c|c|} \hline 0 & 1 \\ \hline 0 & 1 \\ \hline 0 & 1 \\ \hline\end{array}\rightarrow\begin{array}{|c|c|} \hline 1 \\ \hline 1 \\ \hline 1 \\ \hline\end{array}\rightarrow\begin{array}{|c|c|} \hline \bf1 & 0 & \it0\\ \hline \bf1 & 0 & 0 \\ \hline \bf1 & 0 & \it0 \\ \hline \bf1 & 0 & 0 \\ \hline\end{array}\rightarrow\begin{array}{|c|c|} \hline 0 & 1 \\ \hline 0 & 0 \\ \hline 0 & 1 \\ \hline\end{array}\rightarrow\)

\(\begin{array}{|c|c|} \hline \bf1 & 0 &\it0\\ \hline \bf0 &\it0 \\ \hline \bf1 \\ \hline\end{array}\rightarrow\begin{array}{|c|c|} \hline 0&1\\ \hline 1&0\\ \hline\end{array}\rightarrow\begin{array}{|c|c|} \hline \bf1&0&\it0\\ \hline \bf0&\it1\\ \hline \bf1&0\\ \hline\end{array}\rightarrow\begin{array}{|c|c|} \hline 0&1\\ \hline 0&1\\ \hline\end{array}\rightarrow\begin{array}{|c|c|} \hline \bf1&0&\it0\\ \hline \bf1\\ \hline\end{array}\rightarrow\)

\(\begin{array}{|c|c|} \hline 0&0&1\\ \hline\end{array}\rightarrow\begin{array}{|c|c|} \hline 0&1\\ \hline\end{array}\rightarrow\begin{array}{|c|c|} \hline 1\\ \hline\end{array}\)

This was fun. Aside from four carries (compared to 17 if we had done this in binary!), there was no arithmetic todo, it was mostly repetitively applying the same two transformations. But I may be overstating the value a bit - certainly it was a lot more digits to write down.

It does at least reframe a familiar problem in a new light. Why is it that these two transformations and some carries always terminate? Is there a maximum number of rows that this algorithm will produce? Can you prove this terminates when a number can be written as a column; or a column with only two bits? How does the algorithm change when you add a bit somewhere?¹⁰

Bit Efficiency

3-Smooth representations are clearly not space efficient. With an n-by-n grid, the largest number you could record is (3^{n+1}-1)(2^{n+1}-1). And there are numbers less than that which cannot be written on the n-by-n grid. Compare this to binary on that many bits could represent any number up to 2^{n^2} (much larger).

However 3-smooth representations can be bit efficient, meaning that a number can be written with few 1s. Not every representation of a given number is bit efficient. However we have freedom to write numbers many different ways, and we can use this freedom to find a bit-efficient representation.

Revisiting the example above of 25, we see that we can write this efficiently as 1 + 24:

\(\begin{array}{|c|c|} \hline 1 & 1 & 1 \\ \hline 1 & 1 & 0 \\ \hline 1 & 0 & 0 \\ \hline\end{array}= \begin{array}{|c|c|} \hline 1 & 1 & 1 \\ \hline \bf1 & \bf1 & 0 \\ \hline \it1 & 0 & 0 \\ \hline\end{array}= \begin{array}{|c|c|} \hline 1 & \bf1 & \bf1 \\ \hline 0 & \it0 & 0 \\ \hline 0 & 1 & 0 \\ \hline\end{array}= \begin{array}{|c|c|} \hline 1 & 0 & 0 & 0 \\ \hline 0 & \bf1 & 0 & \bf0\\ \hline 0 & \bf1 & 0 & 0\\ \hline\end{array}=\begin{array}{|c|c|} \hline 1 & 0 & 0 & 0 \\ \hline 0 & 0 & 0 & 1\\ \hline 0 & 0 & 0 & 0\\ \hline\end{array}\)

We care about bit efficiency, because addition and (especially) multiplication are easier with fewer bits.

In fact most numbers can be written in 3-smooth representation using only two bits. We call a 3-smooth representation “minimal” if the number cannot be written with fewer bits. Here’s an list of the first hundred minimal representations:

Which numbers can’t be written with only two bits is something of a mathematical curiosity.¹¹ Minimal representation are also not unique, and in general they’re hard to find.

Let’s also introduce a family of representations called “principal” representations.¹² These are 3-smooth representations that have no row or column with more than one bit set, and no one bit is down and two the right of another. Another way to say this is: “No bit divides any other bit.” Example:

\(\begin{array}{|c|c|} \hline 0&0&0&1\\ \hline 0&1&0&0\\ \hline 1&0&0&0\\ \hline\end{array}\)

These matrices are nearly-anti-diagonal. Specifically, as the bits decrease on one dimension, they increase on the other. In the worst case an n-by-n principal representation only uses n bits filling out the full diagonal.

Like with minimal representations, principal representations are usually not unique.¹³ But they are often bit efficient. For the first 128 numbers, I found one principal representation. On average, these representations used 2.44 bits, compared to 3.5 bits for binary, and 1.97 for minimal representations (found using an NP algorithm).

Multiplication

Using minimal and principal representations, multiplication becomes easier than with a general 3-smooth representation. I randomly generated four numbers to test this: 83, 58, 15, 49. Let’s hope I don’t regret this.

Assume that I have the minimal and principal representations saved some where. I’ll write 2^m*3^n as (m,n). Multiplying (a,b) with (c,d) then would give (a+c,b+d).

83 = (0,4) + (1,0)
58 = (1,3) + (2,0)
15 = (0,2) + (1,1)
49 = (0,0) + (4,1) = (0,3) + (1,2) + (2,0)

We’ll do transformations non-graphically here, because it’s easier in this case.

83 * 58 = (1,7) + (2,3) + (2,4) + (3,0) = (1,7) + (3,0) + (4,3)

Next we’ll multiply 15*49, this time visually. Surprisingly I’ll prefer the longer principal representation of 49. 49 is represented by highlighted by yellow to show the multiplication step.

\(\begin{array}{|c|c|} \hline 0&0&0^*\\ \hline 0&0&0&1\\ \hline 0&0^*&1\\ \hline 0^*&0&1\\ \hline 0&2\\ \hline 1\\ \hline\end{array}=\begin{array}{|c|c|} \hline 0&0&0\\ \hline 0&0&0&1\\ \hline 0&0&0&0&1\\ \hline0&0&0\\ \hline 0&0&1\\ \hline 1\\ \hline\end{array}=\begin{array}{|c|c|} \hline 0&0&0\\ \hline 0&0&0&0&0&1\\ \hline 0&0&0&1\\ \hline0&0&0\\ \hline 0&0&1\\ \hline 1\\ \hline\end{array}\)

Our result is:

15 * 49 = (0,5) + (2,4) + (3,2) + (5,1)

We ended up with 4 bits that we would have gotten if we had used the minimal form and we had to do some simplification, so why use the principal representation? Because the product of principal representations are likely to nearly principal, as we saw here. This allows us to do fairly simple transformations to get back to principality, which we know if somewhat bit efficient. Intermediate simplifications are worth it if it means that we can preserve principality for the next product.

Our last product then:

15 * 49 * 83 * 58 =

  (1,12) + (3,11) + (4,9) + (6,8)
+ (3,5)  + (5,4)  + (6,2) + (8,1)
+ (4,8)  + (6,7)  + (7,5) + (9,4) =

 (1, 8) + (4, 7) + (7, 5) + (11, 4) + (14, 2) + (20, 1)

For the last equality, I used a computer algorithm to convert to a principal representation.¹⁴

The number of terms you have to keep track of with the product of two terms is equal to the product of the number of bits in each term. The same is true for binary representations. We trade carries for transformations in order to preserve principality. Though we demonstrated that there are typically fewer bits in a principal representation, asymptotically the algorithms have the same amount of work for large numbers.

What’s interesting about multiplication on 3-smooth representations is the additional degrees of freedom. You can choose when you apply transformations and how much you transform. You can search for minimal solutions at any intermediate step. You can reduce bits with small approximations.

Conclusion and Other Things to Think About

2D numeral representations give us a wealth of new counting systems. These make some things harder, but other things easier. The new representation has a new and interesting arithmetic. It frames some problems (like Collatz Conjecture) in a new light. The multiple representations of each number gives us degrees of freedom for how we tackle arithmetic problems, which could potentially be exploited.

Here are some questions that came to mind as I worked through this. If you have an answer to these or other ideas, let me know.

• Is there some formula for when a number has a two-bit 3-smooth representation? Note that if you do an infinite-dimensional representation with a dimension for each prime, Goldbach’s conjecture¹⁵ implies that every even number can be written with just two bits.

• Is there some (efficient) algorithm to find a minimal representation for a given 3-smooth representation?

• Though there are infinitely many transformations, can you write down a set of families that capture all of these?

• Is there a more efficient algorithm to find a principal representation of a product of two two-bit principal representations?

• Most numbers are close to two-bit principal representations. Can you bound the error of a product if you replace both numbers with their closest two-bit principal representation?

• Is there some family of numbers whose 3-smooth representation makes it clear that the Collatz Conjecture holds for that family?

1. https://www.britannica.com/topic/Hindu-Arabic-numerals

2. Roman numerals are classic example.

3. “Mixed radix” is the name for place values that don’t grow exponentially. To generalize fully, you can specify a bespoke place value for each digit.

4. Generally b doesn’t even have to be a whole number, but since we’re talking whole numbers in this article (and for our sanity), we’ll assume it is.

5. There are lots of resources on this idea. I recommend this reference from OpenStax.

6. “3-Smooth” has some broad meaning, but that’s not helpful for understanding this article.

7. Ah, the keen-eyed reader may notice that in fact every whole number has exactly two representations in decimal.

8. A better algorithm for converting to algorithm is to use the left most column to get parity, then use the given family of rules to divide by two (rounding down) and repeat.

9. https://en.wikipedia.org/wiki/Collatz_conjecture

10. I’m not the first person to think to use 3-smooth representations to tackle Collatz Conjecture. See for example: http://hdl.handle.net/11375/27543

11. Here’s a lits of them: https://oeis.org/A081329

12. Some sources use “3-smooth representation” to mean “principal 3-smooth representations,” leaving the more general form we’ve been using unnamed.

13. This paper gives a condition for uniqueness of principal representations. https://doi.org/10.2307/2589404

14. Specifically the algorithm outlined here. https://doi.org/10.2307/2589404

15. https://en.wikipedia.org/wiki/Goldbach%27s_conjecture