I had this idea of non-overflowing digits when I first saw pascal's triangle in primary school and last day it came to my mind again for no apparent reason. I tried to search this a little bit but couldn't find anything related partly because of the fact that 'baseless numbers' is usually used with the meaning 'fake numbers' or 'misleading numbers' and partly because it is probably a quite useless thing to have but anyhow here it goes.

Baseless Number System

Just to get you started here is a pascal triangle in its conventional form:

\begin{array}{ccccccccccc} & & & & & & 1 & & & & & & \\ & & & & & 1 & & 1 & & & & & \\ & & & & 1 & & 2 & & 1 & & & & \\ & & & 1 & & 3 & & 3 & & 1 & & & \\ & & 1 & & 4 & & 6 & & 4 & & 1 & & \\ & 1 & & 5 & & 10 & & 10 & & 5 & & 1 & \\ & & & & & & \dots & & & & & & \\ \end{array}

When I looked at these numbers first thing I saw was that $11^2 = 121$ which are numbers in (zero indexed) first and second row of the triangle as if they were just single numbers instead. Trying to find a pattern I tried to take the square of $121$ hoping to get $1331$ but it gave me $14641$ instead which is still adaptable for a pattern. What was also interesting is that I was able to get $1331$ by multiplying $121$ and $11$ and then I realized what I had was:

\begin{align} n = 0:& 11^n = 1 \\ n = 1:& 11^n = 11 \\ n = 2:& 11^n = 121 \\ n = 3:& 11^n = 1331 \\ n = 4:& 11^n = 14641 \\ \end{align}

Is pascal's triangle just numbers $11^n$?

\begin{align} n = 5:& 11^n = 161051 \\ \end{align}

So the answer is no, well at least in simple terms. The obvious problem with the $5^{th}$ row is that there are numbers with multiple digits and it's ambiguous how to concatenate them, hence the obvious answer is that what if we had no multiple digits that is to say digits themselves do not overflow and form the next ones.

Luckily I was doing the calculations on paper like this:

\begin{array}{cccccc} 1 & 4 & 6 & 4 & 1 \\ \times & & & 1 & 1 \\ \hline & & & & \dots \\ \end{array}

and the part that grabbed my attention was:

\begin{array}{cccccc} & & 1 & 4 & 6 & 4 & 1 \\ + & 1 & 4 & 6 & 4 & 1 & \\ \hline & 1 & 6 & 1 & 0 & 5 & 1 \\ \end{array}

So instead of carrying over in overflowing digits I put some space between digits and wrote them as they are which gave me the answer I was looking for. Just to make things clear I will put columns between digits:

\begin{array}{cccccc} & & : & 1 & : & 4 & : & 6 & : & 4 & : & 1 \\ + & 1 & : & 4 & : & 6 & : & 4 & : & 1 & \\ \hline & 1 & : & 5 & : & 10 & : & 10 & : & 5 & : & 1 & \\ \end{array}

Elaborating on what we have in here, regular base $10$ numbers use $10$ distinct symbols:

\begin{equation} \Sigma = \{0,1,2,..,9\} \end{equation}

Hexadecimal (base $16$) numbers use $16$ symbols:

\begin{equation} \Sigma = \{0,1,2,..,9,A,B,C,D,E,F\} \end{equation}

Since $10$ can be represented with only one digit $A$ in hexadecimal system we could use hexadecimal system to calculate the $5^{th}$ row correctly by calculating $11^5$ but then we would have the same problem in $6^{th}$ row and later on.

Since we don't want to overflow a digit ever, we need to have a symbol set having an infinite number of elements. We know for sure that there is no such alphabet on earth hence the best candidate for the job is the integer set itself to use as the symbol set:

\begin{equation} \Sigma = \mathbb{N} = \{0,1,2,..,9,10,11,12,..\} \end{equation}

In the end, a loosely formal description of the language of baseless numbers would be:

\begin{equation} (\Sigma :)^*\Sigma \end{equation}

Implementation in Scala

Now that I grew up and learned programming I decided to implement this idea mostly because it's quite fun to do it in Scala. An easy way to do this is to represent digits as a List[Int]. This would mean something like a number system in base Integer.MAX_VALUE (2147483647) and not even that because overflowing digits won't increase the next one. I agree it would be better to use List[BigInt] and maybe even better to parametrize the underlying type to allow users to select whatever type they require depending on the application including things like Baseless[Float] if that proves to be useful. I will keep things simple for now.

Let's first make a class and its companion object.

class BaselessInt private (val digits: List[Int]) { .. }
object BaselessInt {
  def apply(digits: List[Int]): BaselessInt = new BaselessInt(digits)
  def apply(digits: Int*): BaselessInt = new BaselessInt(digits.toList)
}

Now we can instantiate our class using:

val b = BaselessInt(List(1, 2, 3))

or just:

val b = BaselessInt(1, 2, 3)

In order to add two numbers we can just zip digits together and add pairs to get the result. zipAll is a convenient method to zip together two collections which have different number of elements by filling the shorter one with the provided element. In order to match digits with the same significance when numbers have different lengths, we first reverse the digits and then reverse them back after zipping.

def +(that: BaselessInt): BaselessInt = {
  val ds1 = this.digits.reverse
  val ds2 = that.digits.reverse
  BaselessInt((ds1.zipAll(ds2, 0, 0).reverse) map { case (d1, d2) => d1 + d2 })
}

Multiplication uses addition operation. Starting from the most significant digit, the trick is to multiply the accumulator by 10 at each step by adding a 0 to the end since that's universal among all number systems including baseless numbers. The rest is just to multiply each digit with the current one with a simple map since there is no overflowing and carrying on.

def *(that: BaselessInt): BaselessInt = digits.foldLeft(BaselessInt(0)) {
  (z, x) => BaselessInt(z.digits :+ 0) + BaselessInt(that.digits.map(_ * x))
}

Power operation is best implemented using Exponentiation by squaring as such.

def ^(n: Int): BaselessInt = n match {
  case 0 => BaselessInt(1)
  case 1 => this
  case even if even % 2 == 0 => (this * this) ^ (n / 2)
  case odd => this * (this ^ (n - 1))
}

Before we test our class let's override the default toString method to get a convenient representation of baseless numbers.

override def toString = digits.mkString(":")

Now if we want to calculate a row in pascal's triangle we could use the formula $11^n$ in baseless number system.

println(BaselessInt(1, 1) ^ 5)  //> 1:5:10:10:5:1
println(BaselessInt(1, 1) ^ 8)  //> 1:8:28:56:70:56:28:8:1

Before I finish up I want to talk about values of baseless numbers a little bit. A somewhat interesting fact is that baseless numbers keep their values, that is if you do the carrying overs of overflowing digits afterwards they give you the correct value, hence we can convert baseless numbers to integers.

def toInt: Int = {
  val (num, acc) = digits.foldRight((List[Int](), 0)) {
    case (x, (xs, r)) => (((x + r) % 10 :: xs), (x + r) / 10)
  }
  (acc :: num).mkString.toInt
}

Now if you try to convert our example \(5^{th}\) row in baseless system to base 10 you will actually get the regular \(11^5\) which is equals to \(161051\).

println(BaselessInt(1, 5, 10, 10, 5, 1).toInt)  //> 161051

Since integers overflow easily in this case let's implement a BigInt conversion as well.

def toBigInt: BigInt = {
  val (num, acc) = digits.foldRight((List[Int](), 0)) {
    case (x, (xs, r)) => (((x + r) % 10 :: xs), (x + r) / 10)
  }
  BigInt((acc :: num).mkString)
}

Lastly note that this conversion keeps the value but also loses some information. The reason is that a number in baseless system corresponds to a unique value but the opposite is not true, that is there could be multiple baseless numbers representing the same value. Therefore if we want to check the equality of two numbers we first need to reduce them to regular numbers.

override def equals(that: Any) = that match {
  case that: BaselessInt => this.toBigInt == that.toBigInt
  case _ => false
}

In order to test this we can pick two baseless numbers which we know corresponding to the same value. First one is the \(5^{th}\) row and the second one is the value of \(5^{th}\) row converted back to a baseless number just by using regular digits as baseless digits.

println(BaselessInt(1, 5, 10, 10, 5, 1) == BaselessInt(1, 6, 1, 0, 5, 1))  //> true

The whole code piece is in here with some example usages in the test suite as well as some possible future improvements like additional operations such as subtraction or division once I figure out how to it in the most useful way. As a closing note, I want to say that if this concept ever becomes useful in anything you do or if you saw this idea somewhere before I would be interested to know.


comments powered by Disqus