# 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 = 2**1 * 3**1 and 8=2**3 becomes 2**1 * 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 = 2**1 * 3**1 and 8=2**3 is 2**3 * 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.