how discrete mathematics is used in computer science. lecture notes on algebraic structures in discrete mathematics and its applications pdf free download
OliverFinch,France,Teacher
Published Date:15-07-2017
Your Website URL(Optional)
Comment
Lecture Notes for College Discrete
Mathematics
GÆbor HorvÆth and Szabolcs T engely
2013Chapter 1
Introduction
These lecture notes are based on the class material College Discrete Mathe-
matics for students in the F oundation Semester year at University of Debre-
cen, Hungary . The lecture notes are intended to help the students understand
and learn the course material, but they do not substitute participation and
active work on the class.
Discrete mathematics deals with the non-continuous mathematics. This
usually means ni te mathematics, but prop erties of natural numb ers are
discussed, as well. The course sets the basis for future mathematical classes,
and is essential to understand those later.
In Chapter 1 we intro duce basic mathematical concepts, such as sets,
subsets, sums and pro ducts, the Euclidean algorithm and numeral systems.
In Chapter 2 we show di erent counting arguments. W e count the numb er
of sequences, subsets, p ermutations, and anagrams. Then we consider the
numb er of ordered subsets, the numb er of subsets of a given size. Finally , we
count the numb er of p ossibilities to distribute money , and to take out some
balls from an urn.
In Chapter 3 we explain di erent basic mathematical pro of metho ds, such
as mathematical induction and pro of by contradiction. W e show how one can
prove theorems in a constructive way , or by using the pigeonhole principle.
At the end of the chapter we use these pro of techniques to bring the reader
b ehind the curtains of a mathematical card trick.
In Chapter 4 we consider Pascal’s famous triangle built up from the bi-1.1 Sets 5
nomial co e cients. W e prove several identities related to the triangle, and
use it to show the Binomial theorem. In Chapter 5 recurrence sequences are
discussed. W e start by the famous T owers of Hanoi, then work our way up to
more general recurrence sequences and to the explicit formulas determining
them. Finally , in Chapter 6 we give all solutions to the exercises o ccurring
in the lecture notes.
1.1 Sets
In mathematics a set is a collection of ob jects that are called elements. Usu-
ally we denote sets by capital letters and elements by small letters. If A is
a set and a is an element of A, then we write a2 A. If a is not an element
of A, then we write a2= A. Now we deal with the problem how to provide a
set.
Sets given by enumeration. If we have a set containing certain
elements, then we enclose these elements in braces. F or example, if A
is a set containing 1, 2 and 3 we write A =f1;2;3g. This notation is
di cult to use if the given set has large amount of elements. In this
case we list only some (usually consecutive) elements such that it is
easy to see which are the remaining elements of the set. As an example
let us assume that B is a set containg the integers b etween 1 and 1000.
Here we write B =f1;2;3;:::;1000g. If C is the set containing the
o dd integers b etween 1 and 99, then we have C =f1;3;5;:::;99g. It
is also p ossible to provide some families of sets, for example
D =f1g; D =f1;3;:::;2k 1g:
1 k
In this case D denotes the set containing the rst k p ositive o dd inte-
k
gers.6 INTRODUCTION
k D
k
1 f1g
2 f1;3g
3 f1;3;5g
4 f1;3;5;7g
Standard sets. There are certain frequently used sets which have
their own symb ols. These are the set of natural numb ers, the set of
integers, the set of rational numb ers, the set of real numb ers and the
set of complex numb ers.
N =f1;2;3;:::g, the set of natural numb ers.
Z =f:::; 2; 1;0;1;2;:::g, the set of integers.
Q, the set of rational numb ers.
R, the set of real numb ers.
C, the set of complex numb ers.
Set-builder notation. It is also p ossible to de ne sets using the
so-called set-builder notation. As an example consider the set D =
3
f1;3;5g, we can de ne this set in many di erent ways, e.g.
f1;3;5g =faj (a 1)(a 3)(a 5) = 0g;
f1;3;5g =faja = 2k 1;k2f1;2;3gg;
f1;3;5g =faj 1a 5; and a is o ddg:
W e can use semicolon instead of the vertical line, as well:
f1;3;5g =fa : (a 1)(a 3)(a 5) = 0g;
f1;3;5g =fa :a = 2k 1;k2f1;2;3gg;
f1;3;5g =fa : 1a 5; and a is o ddg:
Let us de ne the set of even natural numb ers:
f2njn2Ng:1.1 Sets 7
The set of rational numb ers can b e given as follows
fa=bja;b2Z;b =6 0g:
T o study some basic prop erties of sets we give some de nitions. First we
intro duce the concept of cardinality .
De nition 1.1. A set is called nite if it has nite numb er of elements. If
a set is not nite it is called in nite.
Now we consider cardinality of nite sets. The cardinality of in nite sets
is more complicated and we will not discuss it.
De nition 1.2. Let A b e a nite set. The c ar dinality of A is the numb er of
di erent elements of A. Notation:jAj.
F or example, the cardinality of D is 3 and the cardinality of the set
3
f1;2;3;6;7;8g is 6.
De nition 1.3. Let A and B b e sets. The set B is a subset of A if and only
if every element of B is an element of A. Notation: BA.
There is a sp ecial set which is a subset of all sets, the so-called empty
set. As the name suggests it is the set which has no element, that is, its
cardinality is 0. The empty set is denoted by;.
De nition 1.4. If B A and B6=;;B =6 A, then B is a pr op er subset of
A.
De nition 1.5. Let A and B b e sets. The two sets are e qual if AB and
BA.
Now we de ne some basic op erations of sets.
De nition 1.6. Let A and B b e sets. The interse ction of A and B is the
setfxjx2A and x2Bg. Notation: A\B .
The so-called V enn diagrams are often useful in case of sets to understand
the situation b etter. By shading the appropriate region we illustrate the
intersection of A and B .8 INTRODUCTION
A B
Let A =f1;2;3;4;5g and B =f3;4;5;6;7g. The intersection of these two
sets is the set A\B =f3;4;5g.
De nition 1.7. Let A and B b e sets. The union of A and B is the set
fxjx2A or x2Bg. Notation: AB .
The corresp onding V enn diagram is as follows.
A B
Let A =f1;2;3;4;5g and B =f3;4;5;6;7g. The union of these two sets
is the set AB =f1;2;3;4;5;6;7g. It is easy to see that the following
prop erties hold A\B = B\A and AB = BA. It is not true for the
di erence of two sets.
De nition 1.8. Let A and B b e sets. The di er enc e of A and B is the set
fxjjx2A and x2= Bg. Notation: AnB .
The V enn diagram of AnB :
A B1.1 Sets 9
T o see the di erence b etween AnB and BnA we draw the V enn diagram of
BnA as well:
A B
Again, let A =f1;2;3;4;5g and B =f3;4;5;6;7g. Now we have that
AnB =f1;2g;
BnA =f6;7g:
Now we intro duce the symmetric di erence of sets.
De nition 1.9. Let A and B b e sets. The symmetric di er enc e of A and
B is the set (AB)n(A\B). Notation: A4B .
The V enn diagram of the symmetric die rence of A and B :
A B
W e give an example using sets A =f1;2;3;4;5g andB =f3;4;5;6;7g. W e
obtain that
A4B =f1;2;6;7g:
Finally , we de ne the complement of a set.
De nition 1.10. Let U b e a set (called the universe) and A is a subset of
U: The complement of A consists of elements of U which do not b elong to A:
Notation: A:10 INTRODUCTION
The corresp onding V enn diagram is as follows.
U
A
A
As an example consider the sets U =f1;2;3;4;5;6g and A =f1;3;5g: The
complement of A is the setf2;4;6g:
Exercise 1.1. LetA =f3;4;6;7;8g;B =f2;4;5;6;8g andC =f1;2;4;5;8g.
What are the elements of the set (AnB)(C\B)?
Exercise 1.2. LetA =f1;3;4;6;7g;B =f2;4;5;6;8g andC =f1;3;4;5;8g.
What are the elements of the set (A\B)n(C\B)?
Exercise 1.3. Let A =f1;3;4;6;7g;B =f2;4;6;8g and C =f1;3;4;8g.
What are the elements of the set (AnB)(CnB)?
Exercise 1.4. List all elements of the following sets:
(a)f3k+1jk2f2;3;4gg,
2
(b)fk jk2f 1;0;1;2gg,
(c)fu vju2f3;4;5g;v2f1;2gg.
Exercise 1.5. Describ e the following sets using set-builder notation.
(a)f2;4;6;8;10g,
(b)f1;4;9;16;25g,
1 1 1
(c) 1; ; ;:::; ;::: ,
k
2 4 2
(d) the set of rational numb ers b etween 1 and 2.
Exercise 1.6. Draw a V enn diagram for the following sets:
(a) (A\B)C ,
(b) (AnB)(AnC),1.2 Sums and pro ducts 11
(c) (AB)\C ,
(d) (A\B)(B\C)(A\C),
(e) ((A\B)nC)((A\C)nB)((B\C)nA),
(f ) (AnB)(BnC)(CnA).
Exercise 1.7. Provide three sets A;B and C which satisfy the following
cardinality conditions
jA\B\Cj = 2;
jA\Bj =jA\Cj =jB\Cj = 2;
jAj =jBj =jCj = 4:
Exercise 1.8. Provide three sets A;B and C which satisfy the following
cardinality conditions
jA\B\Cj = 2;
jA\Bj = 2; jA\Cj = 2; jB\Cj = 3;
jAj = 4; jBj = 5; jCj = 6:
1.2 Sums and products
In this section we intro duce summation notation and pro duct notation which
P
we will use later on. The sp ecial symb ol is used to denote sums. Let us
consider an example
5
X
k = 1+2+3+4+5:
k=1
In a more general form
n
X
k =m+(m+1)+:::+(n 1)+n:
k=m
Here m is the lower b ound of summation and n is the upp er b ound of sum-
mation. There are some other p ossibilities to express the ab ove sum, e.g.
X
k;
mkn
X
k; where S =fm;m+1;:::;ng:
k2S12 INTRODUCTION
It is imp ortant to note that the v ariable used in the summation is arbitrary .
That is, the v alues of the following summations are equal:
3
X
2 2 2 2
k = 1 +2 +3 = 14
k=1
and
3
X
2 2 2 2
m = 1 +2 +3 = 14:
m=1
Now we write out explicitly some other summations:
(a)
6
X
(2 i) = (2 2)+(3 2)+(4 2)+(5 2)+(6 2) = 10;
i=2
(b)
5
X
j 2 3 2 4 2 5 2
2 = 2 +2 +2 = 14;
j=3
(c)
X
ij = (11)+(12)+(21)+(22) = 9:
1i;j2
Now we deal with pro ducts of mathematical expressions. The symb ol used
Q
in this case is . Pro duct notation is very similar to summation notation so
it is straightforward to learn to use. The rst example in case of summation
notation was
5
X
k = 1+2+3+4+5:
k=1
P Q
If we change the symb ol to , then we obtain
5
Y
k = 12345:
k=1
Let us consider the pro duct of integers b etween m and n, where mn. W e1.2 Sums and pro ducts 13
can write it in pro duct notation in di erent forms:
n
Y
k;
k=m
Y
k;
mkn
Y
k; where S =fm;m+1;:::;ng:
k2S
It may happ en that the sum or pro duct should b e ev aluated on the empty
set. By de nition, in such situations the sum is always 0 and the pro duct is
always 1, e.g.
X
k = 0;
k2;
Y
k = 1:
k2;
If S and T b e two disjoint sets, then
X X X
k+ k = k;
k2S k2T k2ST
Y Y Y
k k = k:
k2S k2T k2ST
Note, that this is true even if S or T is the empty set. (This is the main
reason we de ne the empty sum to b e 0 and the empty pro duct to b e 1.)
There is a sp ecial notation for the pro duct of p ositive integers up to n,
that is, when we multiply the elements of
S =fkjk is a p ositive integer;kng =f1;2;:::;ng:
n
The pro duct of the elements of S is called n factorial and denoted by n,
n
that is,
n
Y Y
n = k = k = 12(n 1)n:
k2S k=1
n
W e even de ne 0, that is, the pro ducts of elements of S :
0
Y Y
0 = k = k = 1:
k2S k2;
014 INTRODUCTION
F actorials are always computed b efore any other op eration. F or example
2+3 = 2+123 = 2+6 = 8;
(2+3) = 5 = 12345 = 120:
Exercise 1.9. Expand the following sums.
P
7
(a) i,
i=4
P
5
2
(b) (i i),
i=1
P
4
i
(c) 10 ,
i=1
P
1
(d) ,
i
2i5 2
P
i
(e) ( 1) , where S =f2;3;5;8g.
i2S
Exercise 1.10. W rite the following expressions in summation notation.
(a) 2+4+6+8+10,
(b) 1+4+7+10,
1 1
(c) + +1+2+4,
4 2
1 1
(d) +1 2+4.
4 2
Exercise 1.11. Expand the following pro ducts.
Q
1
(a) i,
i= 4
Q
4
2
(b) (i ),
i=1
Q
3
i
(c) 2 ,
i=1
Q
1
(d) ,
i
2i3 2
Q
i
(e) ( 1) , where S =f2;4;6;7g.
i2S
Exercise 1.12. W rite the following expressions in pro duct notation.
(a) 1357,
(b) ( 1)258,
1 1
(c) 139.
9 3
Exercise 1.13. Compute the v alues of n for everyn2f0;1;2;3;4;5;6;7;8g.1.3 The Euclidean algorithm 15
Exercise 1.14. Compute the v alues of
5+3
(5+3)
4 23
(4 2)3
4 (23)
32
(32)
43
45:
Exercise 1.15. Prove that n = n (n 1) for every p ositive integer n.
Note, that it is even true for n = 1, which is one of the reasons we de ne 0
to b e equal to 1.
1.3 The Euclidean algorithm
In this section we intro duce the so-called Division algorithm, we de ne the
greatest common divisor of given integers and we consider the Euclidean
algorithm, which is one of the oldest mathematical algorithms.
Division algorithm. Given two integers a and b such that b 0. There
exist unique integers q and r for which
a =qb+r; 0r b:
Here q is called quotient and r is called r emainder. There is a sp ecial case,
when the Division algorithm yields r = 0. In such a situation a = qb for
some q .
De nition 1.11. W e say that b divides a (b is a divisor ofa ora is a multiple
of b) if there exists q such that a =qb. Notation: bja.
How to nd an appropriate q and r ? Let us assume that we have two
p ositive integers a andb. W e start with q = 0 andr =a. Clearlya = 0b+a.16 INTRODUCTION
Ifab, then we are done, otherwise a b 0. So we write a = 1b+(a b).
W e check ifa bb. If this is the case then we have found q andr , otherwise
we have a 2b 0 and a = 2b+(a 2b). W e stop when we have a kbb
for some k . F or example, let a = 76 and b = 7 :
k a kb
0 76
1 69
2 62
3 55
4 48
5 41
6 34
7 27
8 20
9 13
10 6
that is, we obtain that 76 = 107+6 and 0 6 7.
De nition 1.12. Let a;b2 Z. A p ositive integer d is called a c ommon
divisor of a and b, if d divides a and d divides b. The largest p ossible such
integer is called the gr e atest c ommon divisor of a and b. Notation: gcd(a;b).
The Euclidean algorithm. Now we study a metho d to determine
gcd(a;b) of given p ositive integers a and b. The metho d also provides so-
lution of the linear Diophantine equation
ax+by = gcd(a;b):
If we apply the Division algorithm to a;b;ab, then we have
a =qb+r; 0r b:
If d is a common divisor of a and b, then d divides r =a qb as well. That
is the basic idea of the algorithm. The Euclidean algorithm works as follows.
First we apply the Division algorithm for a and b to obtain a quotient q and
11.3 The Euclidean algorithm 17
a remainder r . Then we apply the Division algorithm for b and r to get a
1 1
new quotient q and a new remainder r . W e continue, we divide r by r to
2 2 1 2
obtain q andr . W e stop if we obtain a zero remainder. Since the pro cedure
3 3
pro duces a decreasing sequence of non-negative integers so must eventually
terminate by descent. The last non-zero remainder is the greatest common
divisor of a and b.
As an example we compute gcd(553;161). W e write the computations in
the following way:
553 = 3161+70 q = 3;r = 70
1 1
161 = 270+21 q = 2;r = 21
2 2
70 = 321+7 q = 3;r = 7
3 3
21 = 37+0 q = 3;r = 0:
4 4
That is, the last non-zero remainder is 7, so gcd(553;161) = 7. If we would
like to express 7 as 553x+161y for some x;y2Z, we can do it by working
backwards
7 = 70 321
= 70 3(161 270) = 3161+770
= 3161+7(553 3161) = 7553 24161:
It follows that x = 7 and y = 24.
Exercise 1.16. Use the Euclidean algorithm to nd gcd(a;b) and compute
integers x and y for which
ax+by = gcd(a;b) :
(a) a = 678;b = 567,
(b) a = 803;b = 319,
(c) a = 2701;b = 2257,
(d) a = 3397;b = 1849.18 INTRODUCTION
1.4 Numeral systems
In this Section we learn ab out the die rent numeral systems. In everyday
life we use base 10. That is, when we talk ab out numb ers, we use the base
10 notation.
Let us consider counting. Imagine Robinson Cruso e sp ending his days on
an uninhabited island, and he counts all the days by carving a vertical line
every day into a ro ck. He was raised using the base 10 numb ers, thus after
reaching 9 lines, he crosses them on the tenth day (thus marking them as
ten). That way he groups together every ten days. Then, when he reaches
ten of such groups, then he carves a big b ox around them. That is how
he indicates hundreds. Then he circles around every ten b oxes, indicating
thousands, etc. Then, reaching ten circles on one ro ck he would lo ok for a
new ro ck to carve days into.
Assume Robinson had arrived at the island 1st May 1817, and was rescued
on 30th April 1850. How would his stones lo ok like, after so much time? He
sp ent 33 years on the island, that is, 33365 = 12045 days, not counting leap
years. The leap years are 1820, 1824, 1828, 1832, 1836, 1840, 1844, 1848,
that is, he sp ent 12053 days altogether on the island. That means one of the
ten thousands, two of the thousands, zero of hundreds, ve of tens and three
of ones. That is, he would have one ro ck completely full with ten circles, ten
b oxes in each circle, and ten of the ten lines crossed in each b ox. Then on
his second ro ck he would have two full circles, and next to them he would
have ve of the ten crossed lines and three separate lines.
Robinson is basically writing the numb ers in base 10 by grouping every
ten together. This is what we do, as well, except mayb e in a bit more
abstract and automatic way . When we think ab out the numb er 12053, we
automatically give the meaning to the p ositions with the appropriate p owers
of 10:
12053 = 110 000+21 000+0100+510+31 =
4 3 2 1 0
= 110 +210 +010 +510 +310 :
By writing the digits next to each other we indicate their v alue by their1.4 Numeral systems 19
0
p ositioning. The v alue of the rightmost digit is 1 = 10 , then going from right
to left the v alue increases by a factor of 10. That is, the v alue of the second
1 2
rightmost digit is 10 , the digit left from it is 10 , etc. W e have ten digits
altogether (0, 1, 2, 3, 4, 5, 6, 7, 8, 9), b ecause every tens will b e group ed
together by this p ositioning.
All other numeral systems are based on the same idea. Considering for
example base 2 (the binary system ), we will only need two digits: 0 and 1,
b ecause every twos will b e group ed together. The v alues of the digits from
right to left will b e the two p owers in increasing order, that is, 1, 2, 4, 8,
16, 32, 64, etc. W e indicate by the numb er 2 in the lower right corner of the
numb er that the base is 2. F or example
5 4 3 2 1 0
101011 = 12 +02 +12 +02 +12 +12 = 32+8+2+1 = 43 :
2 10
Numb ers are almost exclusively represented in their binary form in Computer
Science.
Another typical example from Computer Science could b e the o ctal sys-
tem, i.e. base 8 (1 byte equals to 8 bits). Then there are eight digits (0, 1, 2,
3, 4, 5, 6, 7), and the v alues of the digits from right to left are the increasing
p owers of 8. Similarly , in Computer Science, base 16 (hexade cimal numb er
system) is used. Here, the v alues of the digits from right to left are the in-
creasing p owers of 16, and we need 16 digits. That is, we need separate digits
for the digits corresp onding to 10, 11, 12, 13, 14 and 15. By convention, we
denote these digits by the rst six letters of the alphab et:
A = 10 ; B = 11 C = 12 ;
16 10 16 10 16 10
D = 13 ; E = 14 F = 15 :
16 10 14 10 16 10
At rst, it might lo ok strange to use digits for the numb er ten, eleven or
twelve. This is actually not so surprising if we think ab out some historical
numb er systems. Counting months, or lo oking at the clo ck we use base 12
numeral system. Until 1971 British p eople used base 12 for money exchange
(12 p ennies were worth 1 shilling). Moreover, in the English language eleven
and twelve have di erent names, they are not generated as all the others20 INTRODUCTION
b etween 10 and 20, indicating that they may have b een distinguished as
extra digits.
Generally , in base n we need n digits, running from 0 to (n 1). W e
will write numb ers in p ositional system, as ab ove. The v alues of the digits
are the p owers of n going from right to left. That is, the rightmost digit
0 1
has v alue n = 1, the second rightmost digit has v alue n =n, the digit left
2
to it has v alue n , etc. Thus, the numb er a a :::a a a in base n (where
t t 1 2 1 0
0a n 1 for every 0kt) represents the numb er
k
t
X
k t t 1 2 1 0
(a a :::a a a ) = an =an +a n ++an +an +an :
t t 1 2 1 0 n k t t 1 2 1 0
k=0
Now, the question is how to write numb ers into di erent numeral systems.
First of all, to write numb ers from a numeral system into base 10 we basically
calculate the v alues of the digits using the p ositional systems, and sum the
results:
4 3 2 1 0
10101 = 12 +02 +12 +02 +12 = 16+4+1 = 21
2 10
3 2 1 0
1212 = 13 +23 +13 +23 = 27+18+3+2 = 50
3 10
2 1 0
372 = 38 +78 +28 = 192+56+2 = 250
8 10
2 1 0
AFE = 1016 +1516 +1416 = 2560+240+14 = 2814 :
16 10
Another metho d is to rep eatedly multiply by the base and add the next digit.
F or example:
10101 = (((12+0)2+1)2+0)2+1
2
((22+1)2+0)2+1 = (52+0)2+1 = 21
10
1212 = ((13+2)3+1)3+2
3
= (53+1)3+2 = 163+2 = 50
10
372 = (38+7)8+2 = 318+2 = 250
8 10
AFE = (1016+15)16+14 = 17516+14 = 2814 :
16 10
The other direction is to nd a base n representation of a decimal numb er.
Again, it can b e done in two di erent ways. The rst is that we check1.4 Numeral systems 21
the highest n-p ower which is not greater than our numb er, execute division
algorithm with this n-p ower, and rep eat the pro cess for the remainder, until
the remainder is 0. F or example, write 250 in base 8. The 8-p owers are (in
10
increasing order) 1, 8, 64, 512, the last one is already greater than 250. Thus
we execute the division algorithm with 64: 250 = 364+58. Now, 8 is not
greater than 58, thus we execute the division algorithm by 8: 58 = 78+2.
Finally , 1 is the highest 8-p ower not greater than 2, and after the division
algorithm we obtain 2 = 21+0. Thus
2 1 0
250 = 364+78+21 = 38 +78 +28 = 372 :
10 8
Exercise 1.17. W rite 21 in base 2, 50 in base 3, 2814 in base 16 using
10 10 10
the metho d explained ab ove.
The other metho d is to execute the division algorithm rep eatedly on the
quotients until the quotient is not 0, and then the numb er will consist of the
remainders b ackwar ds . F or example, if we want to rewrite 2814 into base
10
16, then
2814 = 17516+14;
175 = 1016+15;
10 = 016+10:
The remainders backwards are 10 =A, 15 =F , 14 =E , thus
2814 =AFE :
10 16
Exercise 1.18. W rite 21 in base 2, 50 in base 3, 250 in base 8 using
10 10 10
the division algorithm.
How would we write a numb er of an arbitrary base into another (arbi-
trary) base? One metho d could b e that we simply rewrite it rst into base
10, then write it into the other system. F or example, if we need to write 372
8
into base 3, we can do the following. Rewrite 372 rst into base 10:
8
2 1 0
372 = 38 +78 +28 = 192+56+2 = 250 :
8 1022 INTRODUCTION
Now, rewrite 250 into base 3:
10
250 = 833+1;
83 = 273+2;
27 = 93+0;
9 = 33+0;
3 = 13+0;
1 = 03+1:
The remainders backwards are 1, 0, 0, 0, 2, 1, thus
372 = 250 = 100021 :
8 10 3
Finally , we mention that some rewriting can b e done much quicker if one
3
base is a full p ower of another. F or example, 8 = 2 , and then every base 8
digit can b e rewritten easily to three base 2 digits:
0 = 000 ; 1 = 001 ;
8 2 8 2
2 = 010 ; 3 = 011 ;
8 2 8 2
4 = 100 ; 5 = 101 ;
8 2 8 2
6 = 110 ; 7 = 111 :
8 2 8 2
Going from right to left, every three base 2 digits can b e easily rewritten into
base 8, as well. Thus, it is easy to rewrite 372 into base 2 or 10101 into
8 2
base 8:
372 = 011 111 010 = 11111010 ;
8 2 2
10101 = 010 101 = 25 :
2 2 8
4
Similarly , as 16 = 2 , every base 16 digit can b e rewritten easily to four
Advise:Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.
