digitális matek

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 10: these are 10^0=1, 10^1=10, 10^2=100, 10^3=1000, etc.
Imagine that we have coins labeled by the powers of 10, like 1-coins, 10-coins, 100-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 9 times, and we always have to pay the exact price. For instance, paying 17 means that we must use one 10-coin and seven 1-coins: we are not allowed to use seventeen 1-coins. Also, we are not allowed to pay two 10 coins and waiting for the change back. Similarly, we pay 215 using exactly two 100-coins, one 10-coin and five 1-coins — there is no other way as, according to the rule, we cannot use twenty-one 10 coins and five 1-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, 7: these are 7^0=1, 7^1=7, 7^2=49, 7^3=343, etc. In addition, in that Sevenland they have another rule: they can use no more than 6 pieces of each type of coins when paying. Suppose that our budget is 10000 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 10000 in terms of powers of 7 according to the rule: no more than 6 coins can be used from each type. Of course, we have to find out which one is the highest power of 7 which is not greater than 10000: after some trial and error we get that it is 7^4=2401, as 7^5 is greater than 10000.

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

    \[10000=4\cdot 2401+396.\]

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

    \[396=1\cdot 343+53.\]

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

    \[53=1\cdot 49+6,\]

hence we use one 49-coin. The remainder is 6, which is smaller than the next power of 7, hence it should be payed by six pieces of 1-coins. We write down in decreasing order the number of coins we have used from the different types: 41106. What is this number? This is the expression of 10000 in the base-7 number system: the exact meaning of the number 41106 is: 4\cdot 7^4+1\cdot 7^3+1\cdot 7^2+0\cdot 7^1+6\cdot 7^0=10000. To indicate that 41106 is expressed in the base-7 number system we write 41106_7: the subscript _7 refers to the base of the number system. So, we can write the sophisticated equation: 10000_{10}=41106_7.

Now we know how to convert a number N from decimal system into another, say, of base-b, where b is a positive integer: we divide N by the highest power of b which is not greater than N 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 b. Nevertheless, if this power is smaller than b, then the following digit will be 0, no powers of b can be skipped.

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

Let us try to do this with 1401_3, that is, 1401 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 1401 is not written in the base-3 number system, as in that number system there is no digit 4. There are only the following digits: 0,1,2 – according to the first rule, which says that in base-b number system the digits are 0,1,2,\dots,b-1. So, 1401 can be a number in any base-b\geq 5 number system.

One may ask: what about the base-1 number system: does it make any sense? In that system we have just one digit, the 0, 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: 0 and 1. 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 0 and „on” means 1. The disadvantage is that the numbers are very long in this system. For instance, our 100-coin can be sold in Twoland for one 64-coin, one 32-coin and one 2-coin, as we have 100_{10}=110010_2.
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 0+0=0, 1+0=0+1=1, and 1+1=10. The multiplication rules are even simpler: 0\cdot 0=0\cdot 1=1\cdot 0=0, and 1\cdot 1=1. 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-5 and base-6 number systems? To answer this question first we try to describe all four digit numbers in the base-5 number system. It is clear that they are the numbers between 1000_5 and 4444_5, the endpoints included. As 1000_5=5^3=125 and 4444_5=5^4-1=624, hence the positive integer x is a four-digit number in the  base-5 number system exactly if 125\leq x\leq 624.

We apply the same argument in the base-6 number system, where we have 1000_6=216 and 5555_6=6^4-1=2335. Hence, we have that the positive integer x is a four-digit number in the  base-6 number system exactly if 216\leq x\leq 2335. The intersection of these two sets is the set of those positive integers x with 216\leq x\leq 624, and the number of these positive integers is 624-215=409.