MTHS 3600 Project 2

Three Puzzles

More Computational and Experimental Mathematics

February 28, 2014

Team Members: _____________________________

                                 _________________________________

                         _____________________________

Triangle Puzzle

Consider an isoceles triangle with 4 slots on each side and 5 slots on the base.  We can place the integers 0 through 9 on the slots of the triangle as follows.

           0

        1     9 

     2           8

   3   4   5   6   7

In this case the left side adds up to 6, the right side adds up to 24, and the base adds up to 25. The goal of the triangle puzzle is to find arrangements of the integers 0 through 9 so that all three sides add up to the same number.

The goal of the programming exercise is to write a program which will generate ALL the distinct solutions to the triangle puzzle in the most efficient way possible --- faster programs get higher scores.  My personal program is the bar to shoot for and it is almost three orders of magnitude faster than Triangle_Puzzle01.

The following block of code builds on the triple for loop solution to the sampling without replacement exercise in HW09.  In this case it enumerates all $10!$ permutions of the integers 0 through 9 and then checks the sums for the three sides.  If the sums are equal, then the count of the number of solutions is incremented.  The first 5 solutions are printed out and the total number of solutions is returned.

There are two major strategies for improving the speed of a program like this.

The first strategy is called Pruning.  Think of a tree with a single root node that represents the empty solution.  From this node we have 10 possible children.  For each of these children, there are 9 possible grandchildren.  And so forth.  At the tenth level, the bottom of this tree, there are $10!$ leaves.  Pruning is the strategy of cutting off branches of the tree as soon as we know that that branch can not lead to a solution.  This strategy includes several implementation tactics:

1. Do the equality tests earlier
2. Rearrange the order in which you choose entries for each slot so that tests can be done earlier
3. Exploit any mathematical properties of the puzzle that might constrain the values that can be placed in certain slots.

The second strategy exploits Symmetries.  This puzzle is symmetric about the vertical axis.  Consequently we could insist that the lower left corner always be smaller (or larger) than the lower right corner.  Once we have enumerated all the solutions that satisfy this constraint, then we only have to multiply by two to find the total number of solutions.  In this puzzle there are other symmetries that can also be exploited.

In the following blocks enter a copy of a working code that implements one of these ideas.  Run it and verify that the timing has improved.  Use a separate block for each improved implementation, and be sure to include comments or preliminary text descriptions of your rationale for each improvement.

Exploring Mersenne Primes

Many early writers felt that the numbers of the form $2^p-1$ were prime for all primes $p$, but in 1536 Hudalricus Regius showed that 2¹¹-1 = 2047 was not prime (it is 23^.89).  By 1603 Pietro Cataldi had correctly verified that 2¹⁷-1 and 2¹⁹-1 were both prime, but then incorrectly stated $2^p-1$ was also prime for 23, 29, 31 and 37.  In 1640 Fermat showed Cataldi was wrong about 23 and 37; then Euler in 1738 showed Cataldi was also wrong about 29.  Sometime later Euler showed Cataldi's assertion about 31 was correct.  The French monk Marin Mersenne (1588-1648) stated in the preface to his Cogitata Physica-Mathematica (1644) that the numbers $2^p-1$ were prime for

p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257 

and were composite for all other positive integers $p<257$.  Mersenne's (incorrect) conjecture fared only slightly better than earlier conjectures, but it still got his name attached to these numbers.

Definition: When $2^p-1$ is prime it is said to be a Mersenne prime.

To underscore the enormous advantage that we have over these earlier mathematicians because of computers, the next two blocks use the Sage built-in function, is_prime(), to determine all the Mersenne Primes less than 1,000.  Specifically, for all primes $p$<N, Mersenne1(N) determines whether $2^p-1$ is a prime and if it is, then it prints $p$, $2^p-1$, and the words Mersenne Prime.

Complete the definition of the function Mersenne2, which should use the Sage built-in functions, is_prime() and factor(), to determine for all primes $p<260$ whether $2^p-1$ is a Mersenne prime and if not what is its factorization.  This function should print the results in a table that displays $p$, $2^p-1$ and either the words Mersenne Prime or the factorization.

List the primes $p<= 257$ which contradict Mersenne's conjecture.  

You may also wish to comment on the apparent difference in the computational complexity of the functions, is_prime() and factor(). 

The function, Lehmer, is defined recursively as

1. Lehmer(1) = 4
2. Lehmer(n) = (Lehmer(n-1))^2 - 2

If we start the calculation with $n = p-1$, where $p$ is an odd prime, then $2^p-1$ is a Mersenne prime if and only if Lehmer(n) mod $(2^p-1)$ is zero, that is, if and only if Lehmer($p-1)$ is divisible by $2^p-1$.

Start by completing the function, Lehmer1, using the recursive definition.  Then define and run the function Mersenne3 with an argument of $N = 18$.

The results from Mersenne3(18) clearly indicate that the value of $s$ is growing very rapidly and increasing $p$ will cause some problems.  (Feel free to verify this for yourself.) Since we only want to determine that $s$ mod $(2^p-1)$ is 0 we can move the mod function inside the definition of Lehmer.  To do this, we will need to have two arguments n and Mp.   On the initial call n will have the value $p-1$ and Mp will have the value $2^p-1$.  The argument n will be decremented on each recursive call but the argument Mp will stay the same.  The values of s will never grow larger than the value of Mp and we can easily calculate Mersenne4(150).

This seems like an adequate solution, but try Mersenne4(1000).  You will encounter a different memory problem, one which is actually due to the memory limitation on recursive functions.  A recursive function has to have enough memory to maintain copies of the state for every instantiation of the function.  In this case 1,000 copies is too much. However, each instance of the Lehmer2 function just invokes itself and does a simple calculation with the result. This is known as tail recursion.  Since we know that the base step returns 4, we can easily convert the recursion into a simple loop.  Complete the definition of Lehmer3 using this simple loop structure, and see how well it runs on all the primes less than 1,000.

What is the largest known Mersenne Prime?  

When was it discovered and by whom?

The Graph Class

The Prime Maze

The following blocks define and display the Prime Maze.

Write a program that finds all the cycles through the Prime Maze that satisfy the following property.

The distance from the root node to every intermediate node is a prime number.