ISE 390 -- Programming Challenges -- Week 6 Notes This Weeks Goals: To review some of the mathematics behind the solution of the problems on the Warm-up World Competition held last week. To introduce this weeks problems on modular arithmetic and primality Topic for Discussion: Should we do the problems in groups instead of individually? Solving the 8-puzzle This can be done by a breadth-first search from the initial puzzle state, with a data structure (perhaps an array of boards) to keep track of which states we have already visited. Number of lattice points in a polygon: This can be computed (in a slow way) with a plane sweep (try every possible x-value and count the number of inside points), as will be discussed when we get to computational geometry section. Another approach would be to use "Pick's theorem": Let P be a lattice polygon. Assume there are I(P) lattice points in the enterior of P, and B(P) lattice points on its boundary. Let A(P) denote the area of A. Then A(P) = I(P) + B(P)/2 - 1 We can compute the area by first triangulating the polygon and adding up the numbers. Repackaging Gaussian elimination can be used to find three rows which will generate solutions to any set of values (are the rows independent). Marbles This problem is a good example of the power of modular arithmetic. You seek to solve the following equation (in variables c1 and c2) c1 * x1 + c2 * x2 = n where all quantities must be integers. Solving for c1 gives c1 = (n - c2 *x2) / x1 which can only be an integer iff n = c2*x2 (mod x1) Solving such a congruence requires a little number theory. If the modulus x1 is relatively prime to x2, this has exactly one solutionl. If x2 divides x1 but not n, there is no solution. Otherwise, we can divide the whole things by the greatest common divisor of the three constants. Greatest Common Divisor The greatest common divisor can be computed by Euclid's algorithm: The algorithm is based on the following two observations: 1.If b|a then gcd(a, b) = b. 2.If a = bt + r, for integers t and r, then gcd(a, b) = gcd(b, r). Example Let a = 2322, b = 654. 2322 = 654*3 + 360 gcd(2322, 654) = gcd(654, 360) 654 = 360*1 + 294 gcd(654, 360) = gcd(360, 294) 360 = 294*1 + 66 gcd(360, 294) = gcd(294, 66) 294 = 66*4 + 30 gcd(294, 66) = gcd(66, 30) 66 = 30*2 + 6 gcd(66, 30) = gcd(30, 6) 30 = 6*5 gcd(30, 6) = 6 Therefore, gcd(2322,654) = 6. Assigned Problems: 180 -- A variation of the Josephus problem. Is modular arithmetic appropriate? (not clear) 202 -- Compute the repeating decimal component of a rational number. Think long division.. 294 -- Count the number of divisors which an integer has, in a clever rather than brute force manner. 324 -- What is the digit distribution of n!, for large n? Can we do better than brute force multiplication? 374 -- Use the power of modular arithmetic for efficiency? 382 -- What is the sum of the divisors of a given integer? What fraction goes with given repeating decimal number? Suppose that a simple fraction a/b has a repeat R of length of l. Then 10^l * (a/b) - (a/b) will be equal to R, and a/b = R / (10^l - 1) The Fundamental theorem of Arithmetic Despite the impressive title, all it states is that each integer can be expressed only one way as the product of primes. This simple fact can be very useful. Puzzle: how many divisors does an integer have (2^n, n!, 10000). Which has the largest number? Which has the smallest number? What about sums of divisors? Modular arithmetic Is (s * t) mod m == (s mod m) * (t mod m) (mod m)? YES -- because suppose s = a*m + b and t = c*m + d. then s*t = (a*m + b)(c*m + d) = acm^2 + (ad+bc)m + bd so the remainder must be bd (mod m)