%config InteractiveShell.ast_node_interactivity="none"
def f(globals, locals):
import base64
code="ZGVmIG1ha2VfcHJpbnRfbG9jYWxzKCk6IAogICAgIyBJbiBhIGZ1bmN0aW9uIHRvIHByZXZlbnQgbG9jYWxzIGFuZCBpbXBvcnRzIGZyb20gbGVha2luZy4KICAgIGdsb2JhbCBtYWtlX3ByaW50X2xvY2FscwogICAgZGVsIG1ha2VfcHJpbnRfbG9jYWxzICAjIE9ubHkgcnVuIHRoaXMgZnVuY3Rpb24gb25jZS4KCiAgICBpbXBvcnQgSVB5dGhvbgogICAgaW1wb3J0IGFzdAogICAgaW1wb3J0IGluc3BlY3QKCiAgICBjbGFzcyBWaXNpdG9yKGFzdC5Ob2RlVmlzaXRvcik6CiAgICAgICAgZGVmIF9faW5pdF9fKHNlbGYpOgogICAgICAgICAgICBzZWxmLnZhcmlhYmxlcyA9IHNldCgpCiAgICAgICAgZGVmIHZpc2l0X05hbWUoc2VsZiwgbmFtZSk6CiAgICAgICAgICAgIHNlbGYudmFyaWFibGVzLmFkZChuYW1lLmlkKQogICAgICAgICMgVE9ETzogUG9zc2libHkgZGV0ZWN0IHdoZXRoZXIgdmFyaWFibGVzIGFyZSBhc3NpZ25lZCB0by4KCiAgICBBTExPV19UWVBFUyA9IFtpbnQsIGZsb2F0LCBzdHIsIGJvb2wsIGxpc3QsIGRpY3QsIHR1cGxlLCByYW5nZV0KICAgIGRlZiBmaWx0ZXJfdmFyaWFibGVzKHZhcmlhYmxlcywgbG9jYWxzKToKICAgICAgICBmb3IgdiBpbiB2YXJpYWJsZXM6CiAgICAgICAgICAgIGlmIHYgaW4gbG9jYWxzIGFuZCB0eXBlKGxvY2Fsc1t2XSkgaW4gQUxMT1dfVFlQRVM6CiAgICAgICAgICAgICAgICB5aWVsZCB2CiAgCiAgICAjIFVuZm9ydHVuYXRlbHksIHRoZXJlIGRvZXNuJ3Qgc2VlbSB0byBiZSBhIHN1cHBvcnRlZCB3YXkgb2YgZ2V0dGluZwogICAgIyB0aGUgY3VycmVudCBjZWxsJ3MgY29kZSB2aWEgdGhlIHB1YmxpYyBJUHl0aG9uIEFQSXMuIEhvd2V2ZXIsIGJlY2F1c2UKICAgICMgd2UgYXJlIGdldHRpbmcgY2FsbGVkIGZyb20gSVB5dGhvbiBpdHNlbGYgYW5kIHdlIGFyZSBhbHJlYWR5IGluc3BlY3RpbmcKICAgICMgdGhlIHN0YWNrdHJhY2UsIHdlIG1pZ2h0IGFzIHdlbGwganVzdCBwZWVrIGludG8gaXRzIGZyYW1lLi4uCiAgICBpZiBJUHl0aG9uLl9fdmVyc2lvbl9fID09ICI1LjUuMCI6CiAgICAgICAgIyBjb2xhYgogICAgICAgIGRlZiBnZXRfYXN0KGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGFzdC5Nb2R1bGUoZnJhbWUuZl9iYWNrLmZfYmFjay5mX2xvY2Fsc1sibm9kZWxpc3QiXSkKICAgICAgICBkZWYgZmluZF9sb2NhbHMoZnJhbWUpOgogICAgICAgICAgICByZXR1cm4gZnJhbWUuZl9sb2NhbHMKICAgICAgICBkZWYgYXRfdG9wX2xldmVsKGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGZyYW1lLmZfYmFjay5mX2NvZGUuY29fZmlsZW5hbWUuZW5kc3dpdGgoIklQeXRob24vY29yZS9pbnRlcmFjdGl2ZXNoZWxsLnB5IikKCiAgICBlbGlmIElQeXRob24uX192ZXJzaW9uX18gPT0gIjguNC4wIjoKICAgICAgICAjIGxhYiBjb21wdXRlcnMKICAgICAgICBkZWYgZ2V0X2FzdChmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBhc3QuTW9kdWxlKGZyYW1lLmZfYmFjay5mX2JhY2suZl9sb2NhbHNbIm5vZGVsaXN0Il0pCiAgICAgICAgZGVmIGZpbmRfbG9jYWxzKGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGZyYW1lLmZfbG9jYWxzCiAgICAgICAgZGVmIGF0X3RvcF9sZXZlbChmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBmcmFtZS5mX2JhY2suZl9jb2RlLmNvX2ZpbGVuYW1lLmVuZHN3aXRoKCJJUHl0aG9uL2NvcmUvaW50ZXJhY3RpdmVzaGVsbC5weSIpCiAgICBlbHNlOgogICAgICAgIHByaW50KGYicHJpbnRfbG9jYWxzKCkgbm90IHN1cHBvcnRlZCBvbiBJUHl0aG9uIHZlcnNpb24ge0lQeXRob24uX192ZXJzaW9uX199IikKCiAgICBkZWYgZ2V0X2NlbGxfbmFtZXMoZnJhbWUpOgogICAgICAgIHRyZWUgPSBnZXRfYXN0KGZyYW1lKQogICAgICAgIHZpc2l0b3IgPSBWaXNpdG9yKCkKICAgICAgICB2aXNpdG9yLnZpc2l0KHRyZWUpCiAgICAgICAgcmV0dXJuIGZpbHRlcl92YXJpYWJsZXModmlzaXRvci52YXJpYWJsZXMsIGZyYW1lLmZfbG9jYWxzKQoKICAgIGRlZiBmaW5kX3doaWNoKGZyYW1lKToKICAgICAgICAjIEZyYW1lIGlzIHRoZSBmcmFtZSB3aG9zZSBsb2NhbHMgd2UgYXJlIGludGVyZXN0ZWQgaW4gcHJpbnRpbmcuCiAgICAgICAgaWYgYXRfdG9wX2xldmVsKGZyYW1lKToKICAgICAgICAgICAgIyBUaGUgcGFyZW50IGZyYW1lIG9mIHRoZSBpbnRlcmVzdGVkIGZyYW1lIGlzIGEgbW9kdWxlLCBtb3N0IGxpa2VseQogICAgICAgICAgICAjICJpbnRlcmFjdGl2ZXNoZWxsIi4gVGhpcyBtZWFucyB3ZSBhcmUgaW4gdGhlIGdsb2JhbCBzY29wZSwgc2luY2UKICAgICAgICAgICAgIyBvbmx5IHRoZSBnbG9iYWwgc2NvcGUgc2hvdWxkIGJlIGRpcmVjdGx5IHJ1biBieSB0aGUgaW50ZXJhY3RpdmUgc2hlbGwuCiAgICAgICAgICAgIHJldHVybiBzZXQoZ2V0X2NlbGxfbmFtZXMoZnJhbWUpKQogICAgICAgICMgVGhlIHBhcmVudCBmcmFtZSBpcyBub3QgYSBtb2R1bGUsIHNvIHdlIGFyZSBpbiBhIGxvY2FsIHNjb3BlLgogICAgICAgIHJldHVybiBzZXQoZnJhbWUuZl9sb2NhbHMpCgogICAgZGVmIHByaW50X2xvY2Fscygqd2hpY2gsIHR5cGVzPUZhbHNlKToKICAgICAgICAiIiJQcmludCB0aGUgbG9jYWwgdmFyaWFibGVzIGluIHRoZSBjYWxsZXIncyBmcmFtZS4iIiIKICAgICAgICBpbXBvcnQgaW5zcGVjdAogICAgICAgICMgY3VycmVudGZyYW1lKCkgZnJhbWUgaXMgcHJpbnRfbG9jYWxzLiBXZSB3YW50IHRoZSBjYWxsZXIncyBmcmFtZQogICAgICAgIGZyYW1lID0gaW5zcGVjdC5jdXJyZW50ZnJhbWUoKS5mX2JhY2sKICAgICAgICBsb2NhbHMgPSBmaW5kX2xvY2FscyhmcmFtZSkKICAgICAgICB3aGljaCA9IHNldCh3aGljaCkgaWYgd2hpY2ggZWxzZSBmaW5kX3doaWNoKGZyYW1lKQogICAgICAgIGxsID0ge2s6IHYgZm9yIGssIHYgaW4gbG9jYWxzLml0ZW1zKCkgaWYgayBpbiB3aGljaH0KICAgICAgICBpZiBub3QgbGw6CiAgICAgICAgICAgIHByaW50KCJwcmludF9sb2NhbHM6IG5vIGxvY2FscyIpCiAgICAgICAgICAgIHJldHVybgogICAgICAgIGlmIHR5cGVzOgogICAgICAgICAgICBwcmludCgiXG4iLmpvaW4oZiJ7a306IHt0eXBlKHYpLl9fbmFtZV9ffSDihpAge3Z9IiBmb3IgaywgdiBpbiBsbC5pdGVtcygpKSkKICAgICAgICBlbHNlOgogICAgICAgICAgICBwcmludCgiOyAiLmpvaW4oZiJ7a30g4oaQIHtyZXByKHYpfSIgZm9yIGssIHYgaW4gbGwuaXRlbXMoKSkpCgogICAgcmV0dXJuIHByaW50X2xvY2FscwoKcHJpbnRfbG9jYWxzID0gbWFrZV9wcmludF9sb2NhbHMoKQ=="
exec(base64.b64decode(code), globals, locals)
f(globals(), locals())
del f
def assertEqual(want, got):
if want == got:
print("Test case passed.")
return
print()
print("--------- Test case failed. ---------")
print(f"Want: {repr(want)} (type: {type(want).__name__})")
print(f"Got: {repr(got)} (type: {type(got).__name__})")
print("-------------------------------------")
print()
Lecture 10, C Exercises (Optional Challenge Problems)¶
1. Primes¶
1.1 Find primes.¶
A prime is a positive integer divisible by exactly two numbers: itself, and 1. (1 is only divisible by 1, so it is not a prime.)
Implement find_primes_up_to, which returns a list of all primes up to n. Recall that you can check whether a divides b by checking b % a == 0.
def find_primes_up_to(n):
"""Finds all prime numbers less than or equal to `n`.
Argument:
n (int): The number to search up to.
Returns: (list) A list of primes up to and including `n`.
Effects: None.
"""
assertEqual([], find_primes_up_to(1))
assertEqual([2], find_primes_up_to(2))
assertEqual([2, 3, 5, 7, 11, 13, 17, 19, 23, 29], find_primes_up_to(30))
1.2 Factorize¶
Given a natural number n, determine its prime factorization. Use find_primes_up_to as defined above to determine primes.
Recall that the fundamental theorem of arithmetic says that every natural number has a unique prime factorization. The prime factorization of a number decomposes it into the product of primes. For example, the prime factorization of $60$ is $2^2 \times 3^1 \times 5^1$.
In our program, we represent this prime factorization as a list: [2, 1, 1], where the first item (0th index) corresponds to the exponent (2) of the first prime (2); the second item (1st index) corresponds to the exponent (1) of the second prime (3), and so on.
Given a number, determine its prime factorization, and return it as the above list representation.
def factorize(n):
"""Given a number, determine its prime factorizaton.
Arguments:
n (int): The number to factorize.
Returns: (list) A list of exponents representing n's prime factorization.
Effects: None.
"""
assertEqual([2, 1, 1], factorize(60))
assertEqual([], factorize(1))
assertEqual([1], factorize(2))
assertEqual([1, 2, 2], factorize(450))
1.3 Goldbach's Conjecture¶
Goldbach's conjecture claims that every even number $n > 2$ can be written as the sum of two primes. In other words, for all $n > 2$, there exist prime numbers $p$ and $q$ such that $p + q = n$.
| p | q | n |
|---|---|---|
| 2 | 2 | 4 |
| 3 | 3 | 6 |
| 3 | 5 | 8 |
| 3 | 7 | 10 |
| 5 | 7 | 12 |
Write a function find_goldbach(n) that returns a pair of primes that sum up to n.
def find_goldbach(n):
"""Find a pair of primes that sum to `n`.
Arguments:
n (int): The number.
Returns: (list) A pair of prime numbers that sum to n.
Effects: None.
"""
def test_is_prime(n):
for i in range(2, n):
if n % i == 0:
return False
return True
assertEqual([3, 3], find_goldbach(6))
for n in range(4, 100):
p, q = find_goldbach(n)
assertEqual(True, test_is_prime(p))
assertEqual(True, test_is_prime(q))
assertEqual(n, p + q)
2. Polynomials¶
2.1 Print a polynomial¶
In our program, we represent (integer) polynomials as a list of integers.
For example, we represent the polynomial $ax^0 + bx^1 + cx^2 + dx^3$ as the list [a, b, c, d]. The first element (0th index) corresponds to the coefficient ($a$) of $x^0$; the second element (1st index) corresponds to the coefficient ($b$) of $x^1$, and so on.
Write a function poly_to_str(l) which takes a polynomial in list form and returns it in string form. The string form of the polynomial [2, 1, 0, 5] would be "2x^0 + 1x^1 + 5x^3".
def poly_to_str(l):
"""Converts a list representation of a polynomial to a string.
Arguments:
l (list): A list representing the coefficients of the polynomial.
Returns: (str) The string form of the polynomial.
Effects: None.
"""
assertEqual("2x^0 + 1x^1 + 5x^3", poly_to_str([2, 1, 0, 5]).strip())
assertEqual("1x^0", poly_to_str([5, 0, 0, 0]).strip())
assertEqual("1x^1 + 2x^2 + 3x^3 + 4x^4 + 5x^5", poly_to_str(list(range(6))))
2.2 Multiply two polynomials¶
Given two list representations of a polynomial, compute the product polynomial. The product polynomial is computed by multiplying every pair of terms from each polynomial, and adding them all up into a new polynomial.
For example, to compute the product:
$$(2x^0 + 1x^1 + 5x^3)(1x^0 + 3x^1 + 1x^2)$$
Take every pair of terms, one from the first polynomial, one from the second:
- $2x^0 \times 1x^0 = 2x^0$
- $2x^0 \times 3x^1 = 6x^1$
- $2x^0 \times 1x^2 = 2x^2$
- $1x^1 \times 1x^0 = 1x^1$
- $1x^1 \times 3x^1 = 3x^2$
- $1x^1 \times 1x^2 = 1x^3$
- $5x^3 \times 1x^0 = 5x^3$
- $5x^3 \times 3x^1 = 15x^4$
- $5x^3 \times 1x^2 = 5x^5$
Then add all the terms:
$$2x^0 + 6x^1 + 2x^2 + 1x^1 + 3x^2 + 1x^3 + 5x^3 + 15x^4 + 5x^5$$
Group terms:
$$2x^0 + (6x^1 + 1x^1) + (2x^2 + 3x^2) + (1x^3 + 5x^3) + 15x^4 + 5x^5$$
Simplify:
$$2x^0 + 7x^1 + 5x^2 + 6x^3 + 15x^4 + 5x^5$$
def multiply_poly(first, second):
"""Multiplies two polynomials in list representation.
Arguments:
first (List[int]): A list representation of the first polynomial.
second (List[int]): A list representation of the second polynomial.
Returns: (List[int]) A list representation of the the product polynomial.
Effects: None.
"""
def drop_trailing_zeroes(poly):
"""Removes trailing zero coefficients from the list-polynomial.
Useful for checking whether two list-polynomials are equal.
"""
result = poly[:]
while result and result[-1] == 0:
result.pop()
return result
f = [2, 1, 0, 5] # 2x^0 + 1x^1 + 5x^3
s = [1, 3, 1] # 1x^0 + 3x^1 + 1x^2
assertEqual([2, 7, 5, 6, 15, 5], drop_trailing_zeroes(multiply_poly(f, s)))
f = [5, 3, 2, 7] # 5x^0 + 3x^1 + 2x^2 + 7x^3
s = [1] # 1x^0
assertEqual([5, 3, 2, 7], drop_trailing_zeroes(multiply_poly(f, s)))
f = [5, 3, 2, 7] # 5x^0 + 3x^1 + 2x^2 + 7x^3
s = [] # 0
assertEqual([], drop_trailing_zeroes(multiply_poly(f, s)))
What is the runtime of your algorithm, if $n$ is the length of your polynomials? Is it surprising that there exists an algorithm to multiply two polynomials in $O(n\log{n})$ time?