Transcript big numbers - New Mexico State University

The number of rational numbers is equal to the
number of whole numbers
Countable sets
• A set is countable if its elements can be
enumerated using the whole numbers.
• A set is countable if it can be put in a one-toone correspondence with the whole numbers
1,2,3,….
• Paradox: the Hilbert hotel
Any number between 0 and 1 can be
represented by a sequence d1,d2,d3,… of zeros
and ones
•
•
•
•
•
•
•
•
x1=x
d1=0 if 0<=x1<1/2; d1=1 if ½<=x1<1
x2=2x1-d1
d2=0 if 0<=x2<1/2; d2=1 if ½<=x2<1
x3=2x2-d2, etc….
Ex: x=0, d1=d2=…=0
x=1/2, d1=1, d2=d3=….=0
x=3/8: d1=0, d2=d2=1, d3=d4=…=0
The numbers between 0 and 1 are
uncountable.
In search of…Georg Cantor
• Ordinal number: 0,1,2,
etc
• Cardinal number:
• 2^N: number of
subsets of a set of N
elements
• Number of subsets of
the natural numbers
• The “Continuum
hypothesis”
Aleph naught
Back down to Earth:
• Numbers are represented by symbols:
• 257,885,161-1 has 17,425,170 digits
• Very large numbers are represented by
descriptions. For example, Shannon’s number
is the number of chess game sequences.
• Very very large numbers are represented by
increasingly abstract descriptions.
• We use symbols to represent mathematical
concepts such as numbers
• The symbols 0,1,2,3,4,5,6,7,8,9 are known as
the Hindu arabic numerals
Some ancient number systems
Cuneiform (Babylonians): base 60
Mayans: Base 20 (with zero)
Egyptians: base 10
Greeks (base 10)
Romans (base 10)
• Only the Mayan’s had a “zero”
• Babylonians: base 60 inherited today in angle
measures. Used for divisibility.
• No placeholder: the idea of a “power” of 10 is
present, but a new symbol had to be
introduced for each new power of 10.
• Decimal notation was discovered several times
historically, notably by Archimedes, but not
popularized until the mid 14th cent.
• Numbers have names
Base 10
•
•
•
•
•
•
•
•
•
2
3
4
5
6
7
8
9
10
Powers of 10
• Alt 1
• More videos and other sources on powers of
10
Orders of Magnitude
• Shannon number
• the number of atoms in the
observable Universe is
estimated to be between
4x10^79 and 10^81.
Some orders on human scales
• Human scale I: things that humans can sense
directly (e.g., a bug, the moon, etc)
• Human scales II: things that humans can sense
with light, sound etc amplification (e.g.,
bacteria, a man on the moon, etc)
• Large and small scales: things that require
specialized instruments to detect or sense
indirectly
• Indirect scales: things that cannot possibly be
sensed directly: subatomic particles, black
holes
These are a few of my least favorite things
• Viruses vary in shape from simple helical and
icosahedral shapes, to more complex structures.
They are about 100 times smaller than bacteria
• Bacterial cells are about one tenth the size of
eukaryotic cells and are typically 0.5–5.0
micrometres in length
• There are approximately five nonillion
(.5×10^30) bacteria on Earth, forming much of
the world's biomass.
Clicker question
• If the average weight of a bacterium is a picogram (10^12 or 1
trillion per gram).
• The average human is estimated to have about 50 trillion
human cells, and it is estimated that the number of bacteria in
a human is ten times the number of human cells.
• How much do the bacteria in a typical human weigh?
• A) < 10 grams
• B) between 10 and 100 grams
• C) between 100 grams and 1 kg
• D) between 1 Kg and 10 Kg
• E) > 10 Kg
How big is a googol?
Some small numbers
•
•
•
•
•
•
10 trillion: national debt
1 trillion: a partial bailout
300 million: number of americans
1 billion: 3 x (number of americans) (approx)
1 trillion: 1000 x 1 billion
$ 30,000: your share of the national debt
Visualizing quantities
• How many pennies would it take to fill the
empire state building?
• Your share of the national debt
Clicker question
• If one cubic foot of pennies is worth $491.52, your
share of the national debt, in pennies, would fill a
cube closest to the following dimensions:
• A) 1x1x1 foot (one cubic foot)
• B) 3x3x3 (27 cubic feet)
• C) 5x5x5 feet (125 cubic feet)
• D) 100x100x100 (1 million cubic feet)
• E) 1000x1000x1000 (1 billion cubic feet)
big numbers
Small Numbers have names
How to make bigger numbers faster
•
•
•
•
•
•
•
There is no biggest number
N+1 > N
2*N>N
N^2>N if N>1
Googol: 10^100
Googolplex: 10^googol
“10^big = very big”
Power towers
Power towers and large numbers
Number and Prime Numbers
• Natural numbers: 0,1,2,3,… allow us to count
things.
• Divisible: p is divisible by q if some whole
number multiple of q is equal to p.
• Remainder: if p>q but p is not divisible by q
then there is a largest m such that mq<p and
we write p=mq+r where 0<=r<q
• p is prime if its only divisors are p and itself.
Some facts about prime numbers
Every whole number is either prime or is
divisible by a smaller prime number.
• Proof: If Q is not prime then we can write
Q=ab for whole numbers a, b where a>1 (and
hence b<Q)
• Suppose that a is the smallest whole number,
larger than one, that divides into Q. Then a is
prime since, otherwise, we could write a=cd
where c>1 (and hence d<a). But then d is a
smaller number than a that divides into Q,
which contradicts our choice of a.
There are infinitely many prime numbers
• Proof by contradiction.
• If there were only finitely many then we could list them all:
p1,p2,…,pN
• Set Q=p1*p2*…*pN+1
• Claim: Q is not divisible by any of the numbers in the list.
Otherwise, Q=Pm for some integer m and P in the list, say
P=p1 (the same argument applies or the other pi’s) Then
• p1*(p2*…*pN)+1 =p1*m or p1*(m-p2*…*pN)=1
• But this is impossible because if the product of two whole
numbers a and b is 1, i.e., a*b=1, then a=1 and b=1. But p1 is
not equal to one.
• This contradiction proves that Q is not divisible by any prime
number on the list so either Q itself is a prime number not on
the list or it is divisible by a prime number not on the list.
Fundamental theorem of arithmetic: Every
whole number can be written uniquely as a
product of prime powers.
• We use the principal of mathematical
induction: if the statement is true for n=1 and
if its being true for all numbers smaller than n
implies that it is true for n, then it is true for
all whole numbers.
• If n is itself prime then we are done (why?)
• Otherwise n is composite, ie, n=ab where a,b are whole
numbers smaller than 1. The induction hypothesis is that a
and b can be written uniquely as products of prime powers,
that is,
• a=p1n1p2n2….pknk and b=p1m1p2m2…pkmk
• Here p1, p2,….,pk are all primes smaller than n and the
exponents could equal zero.
• Then n=ab=p1n1+m1p2n2+m2….pknk+mk
• The exponents are unique since changing any of them would
change the product.
Clicker Question
• Which of the following correctly expresses
expresses 123456789 as a product of prime
factors:
• A) 123456789=2*3*3*3*3*769*991
• B) 123456789=29*4257131
• C) 123456789=3*3*3607*3803
• D) 123456789=2*2*7*13*17*71*281
What this means:
• There is a code (the prime numbers) for
generating any whole number via the code
• Given the code, it is simple to check the code
(by multiplying)
• Given the answer, it is not easy, necessarily, to
find the code.
Large prime numbers
• Euclid: there are infinitely many prime
numbers
• Proof: given a list of prime numbers, multiply
all of them together and add one.
• Either the new number is prime or there is a
smaller prime not in the list.
How big is the largest known prime number?
• 257,885,161-1 has 17,425,170 digits.
• A typical 8x10 page of text contains a
maximum of about 3500 characters (digits)
• Printing out all of the digits would take about
5000 pages. That’s a full carton of standard
copier paper. That’s about 0.6 trees.
Security codes
• Later we might discuss RSA encryption, which
is based on prime number pairs, M=E*D
where E,D are prime numbers. Standard 2048
bit encryption uses numbers M that have
about 617 digits. In principle we have to check
divisibility by prime numbers up to about 300
digits.
Euclid’s algorithms: GCD
• The greatest common divisor of M and N is
the largest whole number that divides evenly
into both M and N
• GCD (6 , 15 ) = 3
• If GCD (M, N) = 1 then M and N are called
relatively prime.
• Euclid’s algorithm is a method to find GCD
(M,N)
Euclid’s algorithm
• M and N whole numbers.
• Suppose M<N. If N is divisible by M then
GCD(M,N) = M
• Otherwise, subtract from N the biggest
multiple of M that is smaller than N. Call the
remainder R.
• Claim: GCD(M,N) = GCD (M,R).
• Repeat until R divides into previous.
Example: GCD (105, 77)
• 49 does not divide 105.
• Subtract 1*77 from 105. Get R=28
• 28 does not divide into 77. Subtract 2*28 from
77. Get R=77-56=21
• Subtract 21 from 28. Get 7.
• 7 divides into 21. Done.
• GCD (105, 77) = 7.
Clicker question: find GCD
(1234,121)
•
•
•
•
A) 1
B) 11
C) 21
D) 121