MAD 2502, Computational mathematics

Assignments

• For 16 January:
  • Figure out exactly what the operator a%b does in Python by using the interactive shell. Write down a description.
  • Write a Python program to print out, and count, the primes that are less than 2500.
  • Rename your program in the form RichF1.py, where you use your name rather than mine (so John Smith's first program would be SmitJ1.py). Mail your program, before 11:00 AM on Wednesday, January 16, to mad2502@gmail.com.
• Answers to Test 1
• For 23 January:
  • Write a program to count the number of ways an even number 2n can be written as the sum of two odd primes. Print out the results for n = 3,4,5,...,20.
  • Find the smallest even number that can be written in 11 ways as the sum of two primes.
  • Find the smallest even number that can be written in exactly 11 ways as the sum of two primes.
  • Rename your program in the form RichF2.py, where you use your name rather than mine (so Will Smith's second program would be SmitW2.py). Mail your program, before 11:00 AM on Wednesday, January 23, to mad2502@gmail.com.
• Answers to Test 2
• For 30 January:
  • Read the section in the text on Sophie Germain primes
  • Write a program to count the number Sophie Germain primes that are less than n. Print out the results for n = 100,200,300,...,1000.
  • Write a program to print out those complete Cunningham chains that have length greater than two and whose first prime is less than n. Print out these chains for n = 1500.
  • Rename your program in the form RichF3.py, where you use your name rather than mine (so Barack Obama's third program would be ObamB3.py). Mail your program, before 11:00 AM on Wednesday, January 30, to mad2502@gmail.com.
• Answers to Test 3
• For 6 February:
  • Read the sections in the text about the largest prime factor and complete factorization.
  • Using the functions spf and Lpf, write a program that prints out those numbers from 2 to 100 whose smallest prime factor is equal to its largest prime factor. (Don't print them out on separate lines.) Does your list look correct?
  • Write a program that prints out lists of the prime factors of 3486784401, 7744352003, 7744879829, and 84502410186833.
  • Write a program that prints out a list (without square brackets) of the prime factors of each number less than 30. A typical line of output would be "12. 2 2 3".
  • Modify this program so that it checks the list of prime factors by multiplying them all together. If that product is equal to the original number, write "check" at the end of the list. Run this modified program on the numbers from 100 to 130.
  • Rename your program in the form RichF4.py, and mail it to mad2502@gmail.com before 11:00 AM on Wednesday, February 6.
• Answers to Test 4
• My fourth program. You can click on RichF4.py to view it, or right click on it and save it (Save link as...).
• For 13 February:
  • Read Section 5, Euclidean algorithm and Euler phi function, up to, but not including, the "final check", which provides another way of computing the phi function, φ(n).
  • Define a Python function f(a,n) that returns a^φ(n) modulo n. For n = 27 and n = 36, print out a and a^φ(n) modulo n, for a = 1,2,...,n, marking those number a that are relatively prime to n.
  • Define a Python function that, given a number n, tests to see if a^φ(n) is equal to 1 modulo n for all number a that are less than n and relatively prime to n. Run it on n = 1000, 1001, ..., 1020.
  • Rename your program in the form RichF5.py, and mail it to mad2502@gmail.com before 11:00 AM on Wednesday, February 13.
• Answers to Test 5
• My fifth program. You can click on RichF5.py to view it, or right click on it and save it (Save link as...).
• Python functions from class on Monday, 18 February
• For 20 February:
  • Read Section 7, Orders of units modulo n.
  • Define a function that returns the order of a modulo n.
  • Define a function that returns the number of elements of order d in the group of units modulo n.
  • Define a function that returns a list of the elements of order d in the group of units modulo n.
  • Print out a list of the elements of order 2 in the group of units modulo n, for each of the numbers n = 3,4,...,50 for which that list has at least two elements.
  • Find the smallest two numbers that have more than 30 units of order 2.
  • Find the smallest two numbers that have more than 20 units of order 3.
  • Rename your program in the form RichF6.py, and mail it to mad2502@gmail.com before 11:00 AM on Wednesday, February 20.
• Answers to Test 6
• My sixth program. You can click on RichF6.py to view it, or right click on it and save it (Save link as...).
• For 27 February:
  • Read Section 2.2, The extended Euclidean algorithm, starting on page 24 in the rearranged text.
  • Implement the function bez(a,b) in Python.
  • Write a program testbez(a,b) that tests your function bez on the numbers a and b, prints out a, b, and bez(a,b), and checks to see whether sa + tb divides both a and b.
  • Run testbez(a,b) on the numbers a from 5 to 12 and the numbers b from a+1 to 13.
  • Use your function bez to find positive inverses for the numbers 472, 473, and 474, modulo 88001, and also modulo 32,452,867.
  • Rename your program in the form RichF7.py, and mail it to mad2502@gmail.com before 11:00 AM on Wednesday, February 27.
• Answers to Test 7
• For 13 March:
  • Read Section 3, Sieving for primes, starting on page 27 in the rearranged text.
  • Use the sieve method to create a list A of boolean values such that A[i] is True exactly when i is a prime. Make the list have length n+1 so that you can set n equal to various values. The list will tell you which of the numbers from 2 to n are primes.
  • Use the list to count the number of primes that are less than n. Print out those counts for n = 100, 1000, 10,000, 100,000, and 1,000,000. Try 10,000,000 also
  • Use the list to count the number of pairs of twin primes that are less than n. Print out those counts for n = 100, 1000, 10,000, 100,000, and 1,000,000. Try 10,000,000 also.
  • Rename your program in the form RichF8.py, and mail it to mad2502@gmail.com before 11:00 AM on Wednesday, March 13.
• Answers to Test 8
• My eighth program. You can click on RichF8.py to view it, or right click on it and save it (Save link as...).
• For 20 March:
  • Read about Fermat's theorem (not including Carmichael numbers or the Miller-Rabin test), Mersenne primes (not including the programs or the Lucas-Lehmer test), and repunits in the text.
  • Write a probabilistic test for primality using Fermat's theorem.
  • Use your test to determine for which numbers p less than 1000 the Mersenne number M_p is prime.
  • Check your results against the table here.
  • Use your test to determine for which numbers p less than 500 the repunit R_p is prime.
  • Check your results against the table here.
  • Rename your program in the form RichF9.py, and mail it to mad2502@gmail.com before 11:00 AM on Wednesday, March 20.
• Answers to Test 9
• My ninth program. You can click on RichF9.py to view it, or right click on it and save it (Save link as...).
• For 27 March:
  • Read about the Miller-Rabin test in the text.
  • Define a Python function G(t,n) that returns '1' if t is equivalent to 1 modulo n, returns '-1' if t is equivalent to -1 modulo n, and returns '*' otherwise.
  • Define a Python function seeG(L,n) that takes a list L of numbers and prints out, on one line, the characters G(t,n) for t in L. Test this function on L = range(2*n) for several small values of n.
  • Define a Python function sd(n) that returns the list [s,d], or the pair (s,d), where d is odd and n-1 = 2^sd. Test this function on n = 6, 41, 49, and 129. If it doesn't do the right thing, fix it.
  • Define a Python function MR(n) that creates a random number a between 2 and n-2, sets x equal to pow(a,d,n), and returns the list [x,pow(x,2,n),pow(x,4,n),...,pow(x,2**s,n)]. Here d and s are the numbers returned by sd(n).
  • Define a Python function seeMR(n) that prints out the list returned by MR(n) using seeG(L,n).
  • Apply seeMR(n) ten times to various large Carmichael numbers n, such as 56052361. What do the results mean? You can find large Carmichael numbers here. The ones with no small factors are the most stubborn ones.
  • Bonus: Include in your program a function that looks at the list returned by MR(n) and decides whether or not n has passed the Miller-Rabin test. Use this function to write "pass" or "fail" next to the print-out of the list that seeMR(n) produces.
  • Rename your program in the form RichF10.py, and mail it to mad2502@gmail.com before 11:00 AM on Wednesday, March 27.
• Answers to Test 10
• For 3 April:
  • Read about the sum of the squares of the digits of a number in the text (Section 6, page 38).
  • Define a Python function h(n) that returns True if n is a happy number and False otherwise.
  • Print out and count all the happy numbers that are less than 1000. Don't print them out on separate lines!
  • Define a Python function inc(n) that returns True if the digits of n appear in increasing order, like 1779, and False otherwise.
  • Print out and count all the happy numbers less than 1000 whose digits appear in increasing order.
  • Print out and count all the happy number triplets (three consecutive happy numbers) that are less than 10000.
  • Print out all the happy number quadruplets (four consecutive happy numbers) that are less than 10000.
  • Print out all the happy number quintuplets that are less than 100000.
  • Rename your program in the form RichF11.py, and mail it to mad2502@gmail.com before 11:00 AM on Wednesday, April 3.
• Answers to Test 11
• For 10 April:
  • Define a function g(n) that returns the sums of the squares of the digits of n written in base 3. Check your function by hand on a few small numbers, like 24 and 123.
  • Find all fixed points of g that are less than 1000.
  • Find all points of period 2 of g that are less than 1000.
  • Find all points of period 3 of g that are less than 1000.
  • Define a function f(n) that returns the sums of the cubes of the digits of n (in base 10). Check your function by hand on a few small numbers, like 24 and 123.
  • Find all the fixed points of f that are less than 1000.
  • Find all the points of period 2 of f that are less than 1000.
  • Find all the points of period 3 of f that are less than 1000.
  • Now that you know the points of period 2 and of period 3, group those points into cycles of size 2 and 3.
  • Are there any other periodic points of f? Write a program that shows there are no others that are less than 1000.
  • What happens if you change 1000 to 10000?
  • Rename your program in the form RichF12.py, and mail it to mad2502@gmail.com before 11:00 AM on Wednesday, April 10.
• Answers to Test 12
• My twelfth program. You can click on RichF12.py to view it, or right click on it and save it (Save link as...).
• For 17 April:
  • Implement the function f(n) that returns the sum of the fourth powers of the digits of n (base 10).
  • Find as many cycles (orbits) of f as you can.
  • Do the same for the function f(n) that returns the sum of the fifth powers of the digits of n.
• Answers to Test 13
• For 24 April:
  • Read about aliquot sequences and the Collatz function in the text.
  • Implement the function s(n) that returns the sum of the proper divisors of n. (The proper divisors of 12 are 1, 2, 3, 4, and 6.)
  • Find all the fixed points and orbits of size 2 that are less than 10000.
  • Find the periods of the numbers 12496, 14316, and 805984760.
  • For each of the numbers n from 1 to 275 for which s(n) > n, find the largest number that can be reached from n by successive applications of s, and the number of applications of s required to reach 1 or a periodic point.
  • Implement the Collatz function and complete the project described in the text (on page 47).
• Answers to Test 14