Ch 6: Math and Logic Puzzles Flashcards
Common Math Puzzle Topics
- Prime Numbers
- Probability Calculation
Prime Numbers:
Essential Concepts
- Prime Factorization (Prime Number Law)
- Divisibility
- Greatest Common Denominator
- Least Common Multiple
- Multiplying GCD and LCM
- Checking for Primality
- Sieve of Eratosthenes
Prime Numbers:
Prime Factorization Law
Every positive integer can be decomposed into a product of primes
Examples:
3 = 2^0 * 3^1
10 = 2^1 * 3^0 * 5^1
84 = 2^2 * 3^1 * 5^0 * 7^1 * 11^0 * 13^0 * …..
Prime numbers in the factorization that are NOT factors have an exponent of 0
Prime Numbers:
Divisibility of Integers:
Is a number Y divisible by X?
Because all integers are products of prime factors,
for a number X to divide a number Y,
All primes in X’s factorization must be present in Y’s factorization.
Y must include all of the prime factors of X.
Formally:
X = 2^j0 * 3^j1 * 5^j2 * 7^j3 * ….
Y = 2^k0 * 3^k1 * 5^k2 * 7^k3 * ….
If X divides Y, then for all i, ji <= ki
Prime Numbers:
Greatest Common Divisor of two Integers
For each prime factor, use the smaller of the exponent between the two numbers:
Formally:
X = 2^j0 * 3^j1 * 5^j2 * 7^j3 * ….
Y = 2^k0 * 3^k1 * 5^k2 * 7^k3 * ….
GCD(X,Y) = 2^min(j0,k0) * 3^min(j1,k1) * 5^min(j2,k2) * …. * p^min(ji, ki)
Prime Numbers:
Least Common Multiple of Two Integers
For each prime factor, use the larger of the exponents between the two numbers:
Formally:
X = 2^j0 * 3^j1 * 5^j2 * 7^j3 * ….
Y = 2^k0 * 3^k1 * 5^k2 * 7^k3 * ….
LCM(X,Y) = 2^max(j0,k0) * 3^max(j1,k1) * 5^max(j2,k2) * …. * p^max(ji, ki)
Prime Numbers:
Three Common Ways to
Check if a Number is Prime
- Naive: Brute Force
Iterate from 2 to n-1,
Checking if n is divisible by the number
O(n) - Improved Naive:
Same, but only check through sqrt(n)
Everything larger is redundant
O(sqrt(n) ) - Sieve of Eratosthenes
Efficiently generates list of numbers 2 to n
If number is in the list, it is prime
Prime Numbers:
Sieve of Eratosthenes
*A highly efficient way to generate a list of prime numbers
* Core concept: all non-prime numbers are divisible by a prime number
Steps:
* Start with a list of numbers up through some value MAX
* Remove all numbers divisible by 2 (except 2)
Note: Can start here for increased efficiency
* Move to the next remaining number, this is the next prime
* Remove all numbers divisible by this prime
* Repeat until reaching sqrt(max)
Note: all non-primes larger than sqrt(max) will have already been
removed at this point
* The list now includes all primes from 2 to MAX
Probability:
Important Concepts
- Venn Diagram
- Bayes Theorem
- Probability of Events A AND B
- Probability of Event A OR B
- Independence
- Mutually Exclusive
Probability:
Bayes’ Theorem
The probability of event A given event B,
is equal to the probability of event B given event A
multiplied by the ratio of the independent probabilities.
P(A given B) = P(B given A) * P(A) / P(B)
Probability of A AND B
P(A and B) = P(B given A) * P(A)
alternatively,
P(A and B) = P(A given B) * P(B)
Together,
P(A given B)P(B) = P(B given A)P(A)
Probability of A OR B
Add the probability of P(A) and P(B).
This includes the intersection probability (A and B) twice,
so subtract it once
P(A or B) = P(A) + P(B) - P(A and B)
Probability:
Independence
Two events are independent if the probability of one happening doesn’t tell you anything about the probability of the other happening.
Probability:
Probability of A AND B when
A and B are independent
P(A and B) = P(A) * P(B)
Probability:
Mutual Exclusivity
If A and B are mutually exclusive, it means that if one happens, the other cannot happen.
