### Number systems

In our everyday practice we use the base-10 number system which is called *decimal system*: what does exactly this expression mean? The meaning is that we try to express the natural numbers in a unique way using the nonnegative powers of : these are , etc.

Imagine that we have coins labeled by the powers of , like -coins, -coins, -coins, etc., and we want to pay any price expressed in terms of natural numbers using these coins but there are two rules: when paying we may use each type of these coins maximum times, and we always have to pay the exact price. For instance, paying means that we must use one -coin and seven -coins: we are not allowed to use seventeen -coins. Also, we are not allowed to pay two coins and waiting for the change back. Similarly, we pay using exactly two -coins, one -coin and five -coins — there is no other way as, according to the rule, we cannot use twenty-one coins and five -coins. The point is that we can pay any price under this rule, and even there is only one way how to do this – assuming that we have arbitrary number of coins of each type.

The first reasonable question concerning this procedure is if we can do the same when visiting another country where they have coins labeled by the powers of, say, : these are , etc. In addition, in that Sevenland they have another rule: they can use no more than pieces of each type of coins when paying. Suppose that our budget is and we wonder how much it is worth in Sevenland, how many different coins we’ll receive according to their rule when we change our money to their currency when crossing the border?

The question is how to express in terms of powers of according to the rule: no more than coins can be used from each type. Of course, we have to find out which one is the highest power of which is not greater than : after some trial and error we get that it is , as is greater than .

The next step is to find out how many -coins we have to use: dividing by we have

Now the next largest coin which must be used is the -coin: we have

So far we have used four -coins and one -coin, the rest is , which is

hence we use one -coin. The remainder is , which is smaller than the next power of , hence it should be payed by six pieces of -coins. We write down in decreasing order the number of coins we have used from the different types: . What is this number? This is the expression of in the base-7 number system: the exact meaning of the number is: . To indicate that is expressed in the base-7 number system we write : the subscript refers to the base of the number system. So, we can write the sophisticated equation: .

Now we know how to convert a number from decimal system into another, say, of base-, where is a positive integer: we divide by the highest power of which is not greater than with remainder: the quotient will be the first digit of the converted number, and we repeat this process with the remainder and the next power of . Nevertheless, if this power is smaller than , then the following digit will be , no powers of can be skipped.

The converse process is expressing a number in base number system in the decimal system. This is the easier way: as we have seen above, the digits of the number should be multiplied with the corresponding powers of so that the last digit corresponds to the power , and then we sum up these products.

Let us try to do this with , that is, is considered as a number in base-3 number system, and we should convert it into the decimal system. What??? Something is wrong here: the number is not written in the base-3 number system, as in that number system there is no digit . There are only the following digits: – according to the first rule, which says that in base- number system the digits are . So, can be a number in any base- number system.

One may ask: what about the base- number system: does it make any sense? In that system we have just one digit, the , hence it does not make too much sense to express numbers in this system. The first reasonable choice is the base-2 number system, called *binary system*, which is very important in informatics. In that system we have two digits: and . The great advantage of this binary system is that these digits can easily be represented by the two possible states of an electric circuit: “off” means and “on” means . The disadvantage is that the numbers are very long in this system. For instance, our -coin can be sold in Twoland for one -coin, one -coin and one -coin, as we have .

But for powerful computers it is not a problem to work with long numbers. And the basic rules of arithmetic, like addition and multiplication are extremely simple in the binary system. When adding two binary numbers we apply the rules , , and . The multiplication rules are even simpler: , and . It is very easy to “teach” these rules to a robot, much easier than to teach the decimal multiplication table to schoolboys – can you remember?

We finish with the following simple problem: how many positive integers are four-digit numbers in both base- and base- number systems? To answer this question first we try to describe all four digit numbers in the base- number system. It is clear that they are the numbers between and , the endpoints included. As and , hence the positive integer is a four-digit number in the base- number system exactly if .

We apply the same argument in the base- number system, where we have and . Hence, we have that the positive integer is a four-digit number in the base- number system exactly if . The intersection of these two sets is the set of those positive integers with , and the number of these positive integers is .