Math and Logic Puzzles Flashcards
Prime Number Law
All positive integers can be decomposed into a product of primes
Divisibility
In order for a number x to divide a number y (x\y), all primes in x’s prime factorization must be in y’all prime factorization.
Greatest Common Divisor of x and y
The greatest positive integer d such that d is a divisor or both x and y.
It is the product of x and y’s primes, but to the power of the lowest power between the two numbers.
Example: 6 = 21 * 31 and 8=23 becomes 21 * 3**0 = 2.
Least Common Multiplier of x and y
The smallest positive integer that is divisible by both x and y.
It is the product of the primes of x and y but with the largest power used.
Example 6 = 21 * 31 and 8=23 is 23 * 3**1 = 24
gcd * lcd of x and y
This becomes x * y. The key concept to understand is that gcd deals with the min prime power while the lcd deals with the max prime power. Together, they will touch both of x’s and y’s primes.
Check for Primality: Naive
Check for divisibility from 2 through n-1 of the number.
Check for Primality: Naive w/small improvement
Only check numbers from 2 to sqrt(n). For every number a that divides n evenly, there is a complement b. If a > sqrt(n) then b < sqrt(n). Therefore, we’ve already checked if b divides n evenly.
Sieve of Eratosthenes
Produces a list of primes from 2 to max. It works by recognizing that all non-prime numbers are divisible by a prime number. Start with a list of numbers up through value max. First, cross off all numbers divisible by 2. The next prime will be the next number in the list not crossed off. Cross off all numbers divisible by this prime. Continue until you reach the max number or last remaining non-crossed off number.
There are a number of optimizations that can be added. For example, using a list of odd numbers will reduce space usage by half.
Probably of A and B
The probability of landing at the intersection of A and B (A upside down U B)
P(A and B) = P(B given A) P(A) = P(A given B) P(B)
Bayes’ Theorem
P(A given B) = P(B given A) P(A) / P(B).
This is b/c P(A and B) can be expressed in terms of P(A) or P(B).
Probability of A or B
Probability of landing in A or B. It’s the probability of landing in one plus the the probability of landing in the other, minus the probability of landing in both.
P(A or B) = P(A) + P(B) - P(A and B)
Independence
If A and B are independent (that is, one happening tells you nothing about the other happening), then P(A and B) = P(A) P(B) b/c P(B given A) = P(B).
Mutually Exclusivity
If A and B are mutually exclusive (that is, if one happens, then the other cannot happen), then P(A or B) = P(A) + P(B) b/c P(A and B) = 0
If an events are independent, can they be mutually exclusive and vice versa?
No unless one or both events have zero probability. If events are mutually exclusive, one happening means the other cannot. If they are independent, one happening has no effect on the other happening.
Worst Case Shifting
Balance the worst case. If an early decision results in a skewing of the worst case, we can sometimes change the decision to balance out the worst case. Think of the 9 ball problem, where one is heavier then the rest. Do it in 2 steps instead of 3.
