How Many Threes Are Needed for N?
Here’s a neat fact: Take any number, like say 10. This can be represented as a sum of powers of 2. For instance, \(10 = 2^3+2^1\).
Of course if you already know about binary numbers, this is less interesting. Because effectively all we’re saying is that if you change your number system from 10 (our usual, decimal number system) to base 2, then you can still represent every number!
Notice how this works the same way as decimal numbers: We can start with numbers 0 and 1. If we’re using base 2, there is no numeral for the number 2, so instead we have to positionally go up one. Therefore 2 is written 10.
Immediately it’s clear that we need a way to show that a given numeral is meant as a decimal or binary, since 10 can be read as “ten” or “two” depending on which base (“radix” if you like to be fancy) we’re using. Therefore let’s agree that any numeral written with 0b in front is meant as binary. Therefore 0b10 is the binary numeral for the number 2. Anything un-decorated is assumed to be in decimal, so still 10 is ten, written in a decimal numeral.
We can continue hitting all numbers by going from 0b10 to 0b11, and from there we need to increase the right-most bit by 1 but again don’t have the numeral 2. (Note: I can write 1 or 0b1 to mean the same thing, so why not just write 1? That is to say, don’t @ me about having just written 1 while talking about binary numbers!) So to increment, we increase the right-most 1 to a 0, and carry an extra 1 left of it. But there’s already a 1 there! So we increment it by 1 and carry a 1 left of there. This takes us from 0b11 to 0b100.
From here we can use the same pattern to get the remaining binary numbers
0b101
0b110
0b111
0b1000
and so on.
Well notice that every binary number then is basically just an encoding of a sum of powers of two! For instance, 0b11 which we know is the same as 3, is also just \(2^1+2^0\). Take for instance 0b101 which we know is five. This is an encoding of \(2^2+2^0\) where you can see that if a digit is 0 we skip it because it contributes nothing to the sum of powers of two.
Well the pattern generating the binary numerals just increments by adding one. We therefore get all the numbers this way — and each numeral is a sum of powers of two. So every number can be represented as a sum of powers of two!
That’s pretty cool, and it shows one of my favorite things about math: Seeing a familiar thing in a new light, and this shift in vision can really cause you to solve various problems in better ways! I won’t go into the uses of binary numbers and sums of powers of two, although there’s a lot to say about them.
Instead I want to next ask the question: For a given number N, how many digits do you need to represent N? Well, if N is less than ten, you can immediately see that the answer depends on the base of your numeral system. If you use binary numbers, you need two digits to represent two, but you need only one digit in decimal.
Let’s answer the question for decimal representations. Take for instance the number 789 which clearly takes three decimal digits. How do we relate the number 789 to the fact that it takes three digits in decimal? Perhaps we use the idea that each next digit requires an extra multiple of 10. After all
$$ 789 = 7\cdot 10^2 + 8\cdot 10^1 + 9\cdot 10^0 $$
We could then say that because 2 is the highest power in this “decomposition” into a combination of powers of 10, then the number of digits needed is 3!
Often we like to phrase this in terms of a logarithm, simply because computers are often equipped with a logarithm function. If we compute \(\log_{10}(789)\) we find from a calculator that it’s about 2.9. This makes sense because \(\log_{10}(1000) = 3\) because this equation is equivalent (by definition) to the equation
$$ 1000 = 10^3 $$
And the logarithm is an increasing function, so if you give it the argument 789 you’ll get something slightly smaller. To capture the exact value that we want, we therefore introduce the “round up” or “ceiling” function. This is written as, for instance \(\lceil 2.1 \rceil = 3\). That is to say, if you put any number between the \(\lceil\) and \(\rceil\) brackets, then we send it to the nearest integer which is not smaller.
Notice, however, that \(\lceil 2 \rceil = 2\) because here the nearest integer to 2 is 2 — and also, 2 is not smaller than 2. So by our technical definition, the ceiling function leaves numbers alone if they are already integers. It only rounds up a number if it has any decimal part.
Then a formula built from these components, for the number of digits needed to represents N, is
$$ \lceil \log_{10}(N) \rceil $$
But nothing about that analysis made much use of the number 10! That is to say, we would get a similar result of our base were 2. In that case the formula is, predictably,
$$ \lceil \log_2(N)\rceil $$
And so we come to the subject of this post’s title — what if our base were three? That is to say, suppose we wanted to take any number N and represent it as a sum of powers of 3 (perhaps with coefficients taken from 0, 1, and 2, just as decimal representation takes coefficients from 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 when expressing it as a sum of powers of ten). Then the number of digits needed in base-3 (also called “ternary numbers”) is
$$\lceil \log_3(N)\rceil $$