MATH 3600 Project 2

2825 days ago by kcbrenn

MTHS 3600 Project 2

Three Puzzles

More Computational and Experimental Mathematics

February 28, 2014

 

Team Members: Kyle Brennan, Justin Ulmer, Hannah Kimbrell 

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.

def Triangle_Puzzle01(): available = [True for k in range(10)] count = 0 for t0 in range(10): available[t0] = False for t1 in range(10): if available[t1]: available[t1] = False for t2 in range(10): if available[t2]: available[t2] = False for t3 in range(10): if available[t3]: available[t3] = False for t4 in range(10): if available[t4]: available[t4] = False for t5 in range(10): if available[t5]: available[t5] = False for t6 in range(10): if available[t6]: available[t6] = False for t7 in range(10): if available[t7]: available[t7] = False for t8 in range(10): if available[t8]: available[t8] = False for t9 in range(10): if available[t9]: left_sum = t0+t1+t2+t3 bottom_sum = t3+t4+t5+t6+t7 right_sum = t7+t8+t9+t0 if left_sum==right_sum and right_sum==bottom_sum: count += 1 if count < 6: print ' ',t0 print ' ',t1,t9 print ' ',t2,' ',t8 print t3,t4,t5,t6,t7 print available[t8] = True available[t7] = True available[t6] = True available[t5] = True available[t4] = True available[t3] = True available[t2] = True available[t1] = True available[t0] = True return count 
       
time Triangle_Puzzle01() 
       
    0
   3 8
  9    6
7 1 2 4 5

    0
   3 6
  9    8
7 1 2 4 5

    0
   3 8
  9    6
7 1 4 2 5

    0
   3 6
  9    8
7 1 4 2 5

    0
   3 8
  9    6
7 2 1 4 5

6672
Time: CPU 9.49 s, Wall: 9.50 s
    0
   3 8
  9    6
7 1 2 4 5

    0
   3 6
  9    8
7 1 2 4 5

    0
   3 8
  9    6
7 1 4 2 5

    0
   3 6
  9    8
7 1 4 2 5

    0
   3 8
  9    6
7 2 1 4 5

6672
Time: CPU 9.49 s, Wall: 9.50 s

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.

def Triangle_Puzzle02(): available = [True for k in range(10)] count = 0 for t0 in range(10): available[t0] = False for t1 in range(10): if available[t1]: available[t1] = False for t2 in range(10): if available[t2]: available[t2] = False for t3 in range(10): if available[t3]: available[t3] = False for t7 in range(10): if available[t7]: available[t7] = False for t8 in range(10): if available[t8]: available[t8] = False for t9 in range(10): if available[t9]: available[t9] = False left_sum = t0+t1+t2+t3 right_sum = t7+t8+t9+t0 if left_sum!=right_sum: count = count else: for t4 in range(10): if available[t4]: available[t4] = False for t5 in range(10): if available[t5]: available[t5] = False for t6 in range(10): if available[t6]: bottom_sum = t3+t4+t5+t6+t7 if right_sum==bottom_sum: count += 1 if count < 6: print ' ',t0 print ' ',t1,t9 print ' ',t2,' ',t8 print t3,t4,t5,t6,t7 print available[t5] = True available[t4] = True available[t9] = True available[t8] = True available[t7] = True available[t3] = True available[t2] = True available[t1] = True available[t0] = True return count 
       
time Triangle_Puzzle02() 
       
    0
   3 8
  9   6
7 1 2 4 5

    0
   3 8
  9   6
7 1 4 2 5

    0
   3 8
  9   6
7 2 1 4 5

    0
   3 8
  9   6
7 2 4 1 5

    0
   3 8
  9   6
7 4 1 2 5

6672
Time: CPU 0.93 s, Wall: 0.93 s
    0
   3 8
  9   6
7 1 2 4 5

    0
   3 8
  9   6
7 1 4 2 5

    0
   3 8
  9   6
7 2 1 4 5

    0
   3 8
  9   6
7 2 4 1 5

    0
   3 8
  9   6
7 4 1 2 5

6672
Time: CPU 0.93 s, Wall: 0.93 s
def Triangle_Puzzle03(): #might as well use a set. Remove will be like setting available to false available = set(range(10)) count = 0 for t0 in available: available.remove(t0) for t1 in available: available.remove(t1) for t2 in available: available.remove(t2) for t3 in available: #setting sums earlier so we can test for equality before we go through all the loops left = t0+t1+t2+t3 available.remove(t3) for t7 in available: available.remove(t7) for t8 in available: available.remove(t8) for t9 in available: #since right side has fewer numbers, we want to check it first #check to make sure right = left. If it doesn't, there is no need to go on right = t7+t8+t9+t0 if left == right: available.remove(t9) for t4 in available: available.remove(t4) for t5 in available: available.remove(t5) for t6 in available: bottom = t3+t4+t5+t6+t7 if left == bottom: count += 1 if count < 6: print ' ',t0 print ' ',t1,t9 print ' ',t2,' ',t8 print t3,t4,t5,t6,t7 print available.add(t5) available.add(t4) available.add(t9) available.add(t8) available.add(t7) available.add(t3) available.add(t2) available.add(t1) available.add(t0) print count 
       
time Triangle_Puzzle03() 
       
    0
   3 8
  9    6
7 1 2 4 5

    0
   3 8
  9    6
7 1 4 2 5

    0
   3 8
  9    6
7 2 1 4 5

    0
   3 8
  9    6
7 2 4 1 5

    0
   3 8
  9    6
7 4 1 2 5

6672
Time: CPU 0.36 s, Wall: 0.36 s
    0
   3 8
  9    6
7 1 2 4 5

    0
   3 8
  9    6
7 1 4 2 5

    0
   3 8
  9    6
7 2 1 4 5

    0
   3 8
  9    6
7 2 4 1 5

    0
   3 8
  9    6
7 4 1 2 5

6672
Time: CPU 0.36 s, Wall: 0.36 s
def Triangle_Puzzle04(): #might as well use a set. Remove will be like setting available to false available = set(range(10)) count = 0 for t0 in available: available.remove(t0) for t1 in available: available.remove(t1) for t2 in available: available.remove(t2) for t3 in available: #setting sums earlier so we can test for equality before we go through all the loops left = t0+t1+t2+t3 available.remove(t3) for t7 in available: available.remove(t7) for t8 in available: available.remove(t8) for t9 in available: #since right side has fewer numbers, we want to check it first #check to make sure right = left. If it doesn't, there is no need to go on right = t7+t8+t9+t0 #take care of the cases where interior entries are flipped and corner entries #are flipped if left == right and t1 < t2 and t8 < t9 and t3 < t7: available.remove(t9) for t4 in available: available.remove(t4) for t5 in available: available.remove(t5) for t6 in available: bottom = t3+t4+t5+t6+t7 #take care of the cases where bottom interior entries are #flipped if left == bottom and t4 < t5 and t5 < t6: count += 1 if count < 6: print ' ',t0 print ' ',t1,t9 print ' ',t2,' ',t8 print t3,t4,t5,t6,t7 print available.add(t5) available.add(t4) available.add(t9) available.add(t8) available.add(t7) available.add(t3) available.add(t2) available.add(t1) available.add(t0) #There are 48 possible equivalent triangles, so we only counted 1 of the 48. To see the total number of triangles, #we print the count * 48. print count * 48 
       
time Triangle_Puzzle04() 
       
    0
   6 9
  8    3
5 1 2 4 7

    0
   6 8
  9    5
2 1 3 7 4

    0
   7 9
  8    5
1 3 4 6 2

    0
   7 8
  9    4
1 2 3 6 5

    1
   5 7
  9    6
2 0 4 8 3

6672
Time: CPU 0.23 s, Wall: 0.23 s
    0
   6 9
  8    3
5 1 2 4 7

    0
   6 8
  9    5
2 1 3 7 4

    0
   7 9
  8    5
1 3 4 6 2

    0
   7 8
  9    4
1 2 3 6 5

    1
   5 7
  9    6
2 0 4 8 3

6672
Time: CPU 0.23 s, Wall: 0.23 s
def Triangle_Puzzle05(): #might as well use a set. Remove will be like setting available to false available = set(range(10)) count = 0 for t0 in available: available.remove(t0) for t1 in available: available.remove(t1) for t2 in available: available.remove(t2) for t3 in available: #setting sums earlier so we can test for equality before we go through all the loops left = t0+t1+t2+t3 if left > 15 and left < 24: available.remove(t3) for t7 in available: available.remove(t7) for t8 in available: available.remove(t8) for t9 in available: #since right side has fewer numbers, we want to check it first #check to make sure right = left. If it doesn't, there is no need to go on right = t7+t8+t9+t0 #take care of the cases where interior entries are flipped and corner entries #are flipped if left == right and t1 < t2 and t8 < t9 and t3 < t7: available.remove(t9) for t4 in available: available.remove(t4) for t5 in available: available.remove(t5) for t6 in available: bottom = t3+t4+t5+t6+t7 #take care of the cases where bottom interior entries are #flipped if left == bottom and t4 < t5 and t5 < t6: count += 1 if count < 6: print ' ',t0 print ' ',t1,t9 print ' ',t2,' ',t8 print t3,t4,t5,t6,t7 print available.add(t5) available.add(t4) available.add(t9) available.add(t8) available.add(t7) available.add(t3) available.add(t2) available.add(t1) available.add(t0) #There are 48 possible equivalent triangles, so we only counted 1 of the 48. To see the total number of triangles, #we print the count * 48. print count * 48 
       
time Triangle_Puzzle05() 
       
    0
   6 9
  8    3
5 1 2 4 7

    0
   6 8
  9    5
2 1 3 7 4

    0
   7 9
  8    5
1 3 4 6 2

    0
   7 8
  9    4
1 2 3 6 5

    1
   5 7
  9    6
2 0 4 8 3

6672
Time: CPU 0.13 s, Wall: 0.13 s
    0
   6 9
  8    3
5 1 2 4 7

    0
   6 8
  9    5
2 1 3 7 4

    0
   7 9
  8    5
1 3 4 6 2

    0
   7 8
  9    4
1 2 3 6 5

    1
   5 7
  9    6
2 0 4 8 3

6672
Time: CPU 0.13 s, Wall: 0.13 s

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 211-1 = 2047 was not prime (it is 23.89).  By 1603 Pietro Cataldi had correctly verified that 217-1 and 219-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.

def Mersenne1(N): small_primes = [p for p in range(N) if is_prime(p)] for p in small_primes: Mp = 2^p - 1 if is_prime(Mp): print p,'\t',Mp,'\tMersenne Prime' 
       
time Mersenne1(1000) 
       
2 	3 	Mersenne Prime
3 	7 	Mersenne Prime
5 	31 	Mersenne Prime
7 	127 	Mersenne Prime
13 	8191 	Mersenne Prime
17 	131071 	Mersenne Prime
19 	524287 	Mersenne Prime
31 	2147483647 	Mersenne Prime
61 	2305843009213693951 	Mersenne Prime
89 	618970019642690137449562111 	Mersenne Prime
107 	162259276829213363391578010288127 	Mersenne Prime
127 	170141183460469231731687303715884105727 	Mersenne Prime
521
	68647976601306097149819007990813932172694353001433054093944634591855431\
833976560521225596406614545549772963113914808580371219879997166438125740\
28291115057151 	Mersenne Prime
607
	53113799281676709868958820655246862732959311772703192319944413820040355\
986085224273916250226522928566888932948624650101534657933765270723940951\
9978766587351943831270835393219031728127 	Mersenne Prime
Time: CPU 1.26 s, Wall: 1.26 s
2 	3 	Mersenne Prime
3 	7 	Mersenne Prime
5 	31 	Mersenne Prime
7 	127 	Mersenne Prime
13 	8191 	Mersenne Prime
17 	131071 	Mersenne Prime
19 	524287 	Mersenne Prime
31 	2147483647 	Mersenne Prime
61 	2305843009213693951 	Mersenne Prime
89 	618970019642690137449562111 	Mersenne Prime
107 	162259276829213363391578010288127 	Mersenne Prime
127 	170141183460469231731687303715884105727 	Mersenne Prime
521 	6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151 	Mersenne Prime
607 	531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127 	Mersenne Prime
Time: CPU 1.26 s, Wall: 1.26 s

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.

def Mersenne2(N): small_primes = [p for p in range(N) if is_prime(p)] for p in small_primes: Mp = 2^p - 1 if is_prime(Mp): print p,'\t',Mp,'\tMersenne Prime' else: print p,'\t',Mp,'\t',factor(Mp) 
       
time Mersenne2(260) 
       
2 	3 	Mersenne Prime
3 	7 	Mersenne Prime
5 	31 	Mersenne Prime
7 	127 	Mersenne Prime
11 	2047 	23 * 89
13 	8191 	Mersenne Prime
17 	131071 	Mersenne Prime
19 	524287 	Mersenne Prime
23 	8388607 	47 * 178481
29 	536870911 	233 * 1103 * 2089
31 	2147483647 	Mersenne Prime
37 	137438953471 	223 * 616318177
41 	2199023255551 	13367 * 164511353
43 	8796093022207 	431 * 9719 * 2099863
47 	140737488355327 	2351 * 4513 * 13264529
53 	9007199254740991 	6361 * 69431 * 20394401
59 	576460752303423487 	179951 * 3203431780337
61 	2305843009213693951 	Mersenne Prime
67 	147573952589676412927 	193707721 * 761838257287
71 	2361183241434822606847 	228479 * 48544121 * 212885833
73 	9444732965739290427391 	439 * 2298041 * 9361973132609
79 	604462909807314587353087 	2687 * 202029703 * 1113491139767
83 	9671406556917033397649407 	167 * 57912614113275649087721
89 	618970019642690137449562111 	Mersenne Prime
97 	158456325028528675187087900671 	11447 * 13842607235828485645766393
101 	2535301200456458802993406410751 	7432339208719 * 341117531003194129
103 	10141204801825835211973625643007 	2550183799 *
3976656429941438590393
107 	162259276829213363391578010288127 	Mersenne Prime
109 	649037107316853453566312041152511 	745988807 *
870035986098720987332873
113 	10384593717069655257060992658440191 	3391 * 23279 * 65993 * 1868569
* 1066818132868207
127 	170141183460469231731687303715884105727 	Mersenne Prime
131 	2722258935367507707706996859454145691647 	263 *
10350794431055162386718619237468234569
137 	174224571863520493293247799005065324265471 	32032215596496435569 *
5439042183600204290159
139 	696898287454081973172991196020261297061887 	5625767248687 *
123876132205208335762278423601
149 	713623846352979940529142984724747568191373311 	86656268566282183151
* 8235109336690846723986161
151 	2854495385411919762116571938898990272765493247 	18121 * 55871 *
165799 * 2332951 * 7289088383388253664437433
157 	182687704666362864775460604089535377456991567871 	852133201 *
60726444167 * 1654058017289 * 2134387368610417
163 	11692013098647223345629478661730264157247460343807 	150287 * 704161
* 110211473 * 27669118297 * 36230454570129675721
167 	187072209578355573530071658587684226515959365500927 	2349023 *
79638304766856507377778616296087448490695649
173 	11972621413014756705924586149611790497021399392059391 	730753 *
1505447 * 70084436712553223 * 155285743288572277679887
179 	766247770432944429179173513575154591809369561091801087 	359 * 1433
* 1489459109360039866456940197095433721664951999121
181 	3064991081731777716716694054300618367237478244367204351 	43441 *
1164193 * 7648337 * 7923871097285295625344647665764672671
191 	3138550867693340381917894711603833208051177722232017256447 	383 *
7068569257 * 39940132241 * 332584516519201 * 87274497124602996457
193 	12554203470773361527671578846415332832204710888928069025791
	13821503 * 61654440233248340616559 * 14732265321145317331353282383
197 	200867255532373784442745261542645325315275374222849104412671 	7487
* 26828803997912886929710867041891989490486893845712448833
199 	803469022129495137770981046170581301261101496891396417650687
	164504919713 * 4884164093883941177660049098586324302977543600799
211 	3291009114642412084309938365114701009965471731267159726697218047
	15193 * 60272956433838849161 * 3593875704495823757388199894268773153439
223
	13479973333575319897333507543509815336818572211270286240551805124607
	18287 * 196687 * 1466449 * 2916841 * 1469495262398780123809 *
596242599987116128415063
227
	215679573337205118357336120696157045389097155380324579848828881993727
	26986333437777017 *
7992177738205979626491506950867720953545660121688631
229
	862718293348820473429344482784628181556388621521298319395315527974911
	1504073 * 20492753 * 59833457464970183 *
467795120187583723534280000348743236593
233
	13803492693581127574869511724554050904902217944340773110325048447598591
	1399 * 135607 * 622577 *
116868129879077600270344856324766260085066532853492178431
239
	88342353238919216479164875037145925791374194843780947906080310064630988\
7 	479 * 1913 * 5737 * 176383 * 134000609 *
7110008717824458123105014279253754096863768062879
241
	35336941295567686591665950014858370316549677937512379162432124025852395\
51 	22000409 *
160619474372352289412737508720216839225805656328990879953332340439
251
	36185027886661311069865932815214971204146870208012676262330495002472853\
01247 	503 * 54217 * 178230287214063289511 * 61676882198695257501367 *
12070396178249893039969681
257
	23158417847463239084714197001737581570653996933128112807891516801582625\
9279871 	535006138814359 * 1155685395246619182673033 *
374550598501810936581776630096313181393
Time: CPU 226.03 s, Wall: 230.48 s
2 	3 	Mersenne Prime
3 	7 	Mersenne Prime
5 	31 	Mersenne Prime
7 	127 	Mersenne Prime
11 	2047 	23 * 89
13 	8191 	Mersenne Prime
17 	131071 	Mersenne Prime
19 	524287 	Mersenne Prime
23 	8388607 	47 * 178481
29 	536870911 	233 * 1103 * 2089
31 	2147483647 	Mersenne Prime
37 	137438953471 	223 * 616318177
41 	2199023255551 	13367 * 164511353
43 	8796093022207 	431 * 9719 * 2099863
47 	140737488355327 	2351 * 4513 * 13264529
53 	9007199254740991 	6361 * 69431 * 20394401
59 	576460752303423487 	179951 * 3203431780337
61 	2305843009213693951 	Mersenne Prime
67 	147573952589676412927 	193707721 * 761838257287
71 	2361183241434822606847 	228479 * 48544121 * 212885833
73 	9444732965739290427391 	439 * 2298041 * 9361973132609
79 	604462909807314587353087 	2687 * 202029703 * 1113491139767
83 	9671406556917033397649407 	167 * 57912614113275649087721
89 	618970019642690137449562111 	Mersenne Prime
97 	158456325028528675187087900671 	11447 * 13842607235828485645766393
101 	2535301200456458802993406410751 	7432339208719 * 341117531003194129
103 	10141204801825835211973625643007 	2550183799 * 3976656429941438590393
107 	162259276829213363391578010288127 	Mersenne Prime
109 	649037107316853453566312041152511 	745988807 * 870035986098720987332873
113 	10384593717069655257060992658440191 	3391 * 23279 * 65993 * 1868569 * 1066818132868207
127 	170141183460469231731687303715884105727 	Mersenne Prime
131 	2722258935367507707706996859454145691647 	263 * 10350794431055162386718619237468234569
137 	174224571863520493293247799005065324265471 	32032215596496435569 * 5439042183600204290159
139 	696898287454081973172991196020261297061887 	5625767248687 * 123876132205208335762278423601
149 	713623846352979940529142984724747568191373311 	86656268566282183151 * 8235109336690846723986161
151 	2854495385411919762116571938898990272765493247 	18121 * 55871 * 165799 * 2332951 * 7289088383388253664437433
157 	182687704666362864775460604089535377456991567871 	852133201 * 60726444167 * 1654058017289 * 2134387368610417
163 	11692013098647223345629478661730264157247460343807 	150287 * 704161 * 110211473 * 27669118297 * 36230454570129675721
167 	187072209578355573530071658587684226515959365500927 	2349023 * 79638304766856507377778616296087448490695649
173 	11972621413014756705924586149611790497021399392059391 	730753 * 1505447 * 70084436712553223 * 155285743288572277679887
179 	766247770432944429179173513575154591809369561091801087 	359 * 1433 * 1489459109360039866456940197095433721664951999121
181 	3064991081731777716716694054300618367237478244367204351 	43441 * 1164193 * 7648337 * 7923871097285295625344647665764672671
191 	3138550867693340381917894711603833208051177722232017256447 	383 * 7068569257 * 39940132241 * 332584516519201 * 87274497124602996457
193 	12554203470773361527671578846415332832204710888928069025791 	13821503 * 61654440233248340616559 * 14732265321145317331353282383
197 	200867255532373784442745261542645325315275374222849104412671 	7487 * 26828803997912886929710867041891989490486893845712448833
199 	803469022129495137770981046170581301261101496891396417650687 	164504919713 * 4884164093883941177660049098586324302977543600799
211 	3291009114642412084309938365114701009965471731267159726697218047 	15193 * 60272956433838849161 * 3593875704495823757388199894268773153439
223 	13479973333575319897333507543509815336818572211270286240551805124607 	18287 * 196687 * 1466449 * 2916841 * 1469495262398780123809 * 596242599987116128415063
227 	215679573337205118357336120696157045389097155380324579848828881993727 	26986333437777017 * 7992177738205979626491506950867720953545660121688631
229 	862718293348820473429344482784628181556388621521298319395315527974911 	1504073 * 20492753 * 59833457464970183 * 467795120187583723534280000348743236593
233 	13803492693581127574869511724554050904902217944340773110325048447598591 	1399 * 135607 * 622577 * 116868129879077600270344856324766260085066532853492178431
239 	883423532389192164791648750371459257913741948437809479060803100646309887 	479 * 1913 * 5737 * 176383 * 134000609 * 7110008717824458123105014279253754096863768062879
241 	3533694129556768659166595001485837031654967793751237916243212402585239551 	22000409 * 160619474372352289412737508720216839225805656328990879953332340439
251 	3618502788666131106986593281521497120414687020801267626233049500247285301247 	503 * 54217 * 178230287214063289511 * 61676882198695257501367 * 12070396178249893039969681
257 	231584178474632390847141970017375815706539969331281128078915168015826259279871 	535006138814359 * 1155685395246619182673033 * 374550598501810936581776630096313181393
Time: CPU 226.03 s, Wall: 230.48 s

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(). 

for p in [1,..,259]: Mp = 2^p - 1 if is_prime(Mp) and p != 2 and p != 3 and p != 5 and p != 7 and p != 13 and p != 17 and p != 19 and p != 31 and p != 67 and p != 127 and p != 257: print p,'\t',Mp,'\tMersenne Prime' #is_prime() appears to be much faster than factor(). When we only had to print primes, the function was very fast, but when we had to produce #the factorization as well, it took almost 4 minutes 
       
61 	2305843009213693951 	Mersenne Prime
89 	618970019642690137449562111 	Mersenne Prime
107 	162259276829213363391578010288127 	Mersenne Prime
61 	2305843009213693951 	Mersenne Prime
89 	618970019642690137449562111 	Mersenne Prime
107 	162259276829213363391578010288127 	Mersenne Prime

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$.

def Lehmer1(n): if n == 1: return 4 pow = Lehmer1(n-1) s = pow^2 s -= 2 return s 
       
def Mersenne3(N): odd_primes = [p for p in range(3,N) if is_prime(p)] for p in odd_primes: Mp = 2^p-1 s = Lehmer1(p-1) if s%Mp == 0: print p,'\t',Mp,'\tMersenne Prime','\t',s else: print p,'\t',Mp,'\t',s 
       
Mersenne3(18) 
       
3 	7 	Mersenne Prime 	14
5 	31 	Mersenne Prime 	37634
7 	127 	Mersenne Prime 	2005956546822746114
11 	2047
	68729682406644277238837486231747530924247154108646671752192618583088487\
405790957964732883069102561043436779663935595172042357306594916344606074\
564712868078287608055203024658359439017580883910978666185875717415541084\
494926500475167381168505927378181899753839260609452265365274850901879881\
203714
13 	8191 	Mersenne Prime
	22313995867897900769603796342295788566208710409165129831038160968311491\
946220319893407703857721437957260314978754160034503401040789215400628158\
170099668522698066550221265307171574634992724727060201120758890920172789\
110609085990337846018634451646739004908975710893057017831784106285989578\
600398251364366079398506512806386775247318462388007386288293644987819640\
076171556974003404195908596970825853990347990259288695088334854125701652\
040860084239663064263605520384355127215307437936591866962296906419378104\
850899571605034504288737636564836267334726723727575106663971046844142763\
512854023937849655467693015631287929701909077381005060802853209341459156\
871829180256316747660704875518660035573112882904493746617877304844878674\
402542586943400547464667179926000026596616252849884072241228637895801783\
293732168802374542280341992348946606531635000814995246895089041641203184\
136132975956905572518723976402989858509003359081748048869560319466898146\
867908972088453016102089761833396052479183215782590173494080725569259056\
977955738902892341951393866495222420379013713784627095469233910359313068\
881745808900306832764925725008680492006161979334986865505218272485914888\
669136966553469714434
17 	131071 	Mersenne Prime
	37777879162279675452195076956113205718931688631103309188157377601609998\
765101734668293563902828537031359912551903101436374824756856238838188198\
606595525211502429399559951575843133710893926008493525445236292584474973\
281634423858427237777283042466004176892479614670428684385999255033933699\
202436874418688841003807765514547577394077635221275185821285815759996787\
407277035012707332662366358282164066182945746537805085654822543732130900\
796483424816934523457703817697713385637466915996489080015505137662792273\
633711234556696822204249217285606183789122752163154754222807772328255418\
070766394037156605663314853250098801227566159347611592319890613114716841\
836100632594159551320759746023210704416427131650005554333750284726698377\
556349340896029179582982612341543014107459740272321947367621588871753460\
124326421144175984290587860548835176733587806793277081924401148146335227\
708484083077150337524986977812535676393046297266877166021503464172978113\
666576368352544356456584006169315412653018435304217924747901024159935532\
721955991191413090162803433907947819216609479705013441859916466697679676\
971816064942676186358815307553218461779593358613654892433778560610927869\
182881918764928593802963116783674183563727193261155678995938995739647879\
090139422775776875148497584616354521386997084311333190034700753950395170\
301567867831450089686499208052102156047528689737309346127600719829770047\
311007488181912797767679835746212097669292161533031048966845258267120195\
006606046424760558646233402621819030137944379764196828015531043578597583\
664096302805068132573107233559330493280085114206273143758451366078320874\
200288972724131956685253317919235483476128447334734273631216350679046905\
827343318833428313246485733185730866951248326939455209967603746447329560\
406861410218686565850976273566544127834531634640797200441304333473503712\
681918817524876918953194517139270505714388740204873185893747174647652885\
501879575318246995946565218815223638512071600873584233633941081879077663\
745929224017814514842281580548905943278387627791491747280729483411645793\
688249740387666867795393840552089955168166872813725379622029659736595281\
260736537944776525418478571197085515286274331540354127588766636609231985\
922762924958945962874314604350653438757441042093428644104879646021699588\
091398760953845844931430583397054400551499435207335533944471958740422518\
902261143627542648694021277755637593939778713850353956353083307398985495\
490389458934945500181331370611626380730309233913587911360221379365267761\
870724651151799166235548869010698093876217237204519870365111389383600498\
268840594908190708610317966373017306011346898529255593789918684394201970\
972410434188474414957385255178309965264181431726631927410613063721141720\
047309145292979507963999734280705804445869076775357216365323308174283533\
422706414968021165658050299502547762157469537809212888867498040666991487\
823662903533160474302388354910224934399341546494859859401741157762608322\
999788317886524097928368788617870107724530590119044607691140787230952002\
676909654659809517265664364312656055649567796871202768835634963923478561\
620394008857144559592559631283830992060537148496332871619576507291030080\
884196251940076887748938611422339834866775406296579344479794804455706967\
786180754907131336679730099934610562872395029779701346962348372441486728\
046940454396986789460340084699493913395597897909032197842501416122482369\
176486530014397720039119474328566186991274374509033944996936229061224786\
405107143973873085438626552571116602278994453919725542009702398732315709\
196340455005543347116976097344609465038962301265378983429338852421421771\
621598662961482685518919761605181732715276577913061936276404113313924198\
260113052754539656907601437146295237984594117908566209606907821785450829\
779178952763391126499656829808203196352757990021840559785741135611665422\
721780053616274847010517127252168526932170208589787326075994302579425154\
745991985252254327562697426341532460386526262995033599964610526392041758\
327614023327770716734272824191763122689827261265265686543204058725530701\
477335436778706330636618424679437330105018876028356350798463681977139446\
628778392840578969713435282704025256192555666021542135068957128194675728\
327157488687888233256208674510798154142782939865461561907107157885751305\
516234708323852743737163796156960947616325335360202220291535778625626568\
689875515393693677437810890309590420946107399552506476212906362060852420\
024495550199214521380245614694788801468950719396454791230081022608201268\
195828293094355432023712470510928819489769161671540641175116174947416482\
825806857648819384328975684136557925905870939720608605319718068436214633\
181993710606254291474867558663323689136397098573758152690441937271692031\
155783728752655508362374895176496272780171187459534841098007470183070969\
836976104907943238412934552881138472101781557911778551493743075296480965\
840577151886892089438768729140432260176652125905847576435102667515977912\
783818047190581114101627320321754019724719508941214478794020898320175622\
468944124139927499268826327772172221719517374840946355772128261526580128\
437775089289745914204571385894636426823884917833292699405876897402743531\
139110173946596090782976760868939556027758998109665423856187003046744545\
727468110136720288819700777573920542301681019082944690255144993699926207\
650851345886688987392757233809211427900492368562067224016927066721746947\
358457438402719709106312218614791949195827929145519172974268805559236366\
763255995958777114281352647332978431950990015216610663132144023679710277\
730362062937319528335053401241448640362803899626329438471655723988982929\
035182669035178626193680738091050724565186247165457313931297436652306187\
066117700270578799639254046757051060503608474894916424854935646079882453\
598358007258014463397031150501353299672932547138910710140847324473599073\
739648238785513253650854765970685354079931478421575345359613755032236406\
556612374781378244529237409100899967268050782694049857659266932873184587\
227299907584987901819108773793382889719179873181457879405399416941631997\
635069877469910816254038263645063132701318768620608872181038734924829867\
696000117145028612927313689109987625444572664170755505450235939043427727\
941193055335823679059793820549229880403042546468545082816422297707941406\
253862862169225263898190159039012212618120773364173124344938545803519374\
078468511814323440400250430413076659205180384464866341438145352576118152\
992114970041008435257070965910401411201441486605158358142143562269540604\
715070550418864160697526545274677402680337995871980681407838539289428983\
428864378105081352653759515249331146197299083812647885103707711392841927\
610002979557733959699897999720865082739638701006112219674062486262766864\
088857626696154735337747941688358334989467530618895003664604919544930274\
667591400828918502294684026631295396668910321617202182994922541778937786\
033610758492933482323618574580290769288888558432663516418864149075235255\
631086752919319718448078876876008599804480972939542589930369794053310652\
031413819048814387260165286959065801376551268455625683855535737323619178\
292462152690633147330308341575097901714633372704885439811361768328053479\
840526015142445875035718724336214135456873871310575774085092873282361844\
685648539010371107974268890153051569355393130614948814340542964067423373\
691459045299493017389429658697022893990680232806932429586525369846312729\
907030242824262587574655085319649540660214960933260422636340891178752351\
652902743465862390624574900707245723690904865838665228749425395903157768\
229190487925622952947511126901269676086687857454365051202588447617077791\
035640671670290232864136354925643848511091668260159527865123178946267112\
733759315574360504527882196888068339017497328292005613249351261999498626\
648682045877416275121537692347728083944677481264908368100016100767250439\
360978881657720723123204187726573673610019271809615012177941360858384479\
958511414118475402580601728911066037849244754872904548943815379153444128\
135208233796247277925993816573345939609993432256919853666823803938512298\
340769579794810037627793412970920402556439864191488284723583414888730571\
132536408537055444407305247873807427514703203704504346817602071568531733\
438500647119206176606007234476891151974061779730219326261341236821898194\
051965568309954067734089264725437460036315981710821481403668829729425659\
708580209269273319602077236360764207513617353232290001173841451359876817\
340299234077050478927388528208765191124523211151339614309043659233474126\
178242349468342919835876958552972245532486616384569444537003562456332786\
923166712746540542912069142329833782630186703092164535027465432310967622\
325948862700310791044608442849148078562139350491249670510680720930251403\
436032088414977554044361564360596442588692486684534337812468326271353150\
305036998568395251178904282455934222923794202687442155060757608037544663\
595002911925071291481936846659821980892004197035094465137335989737236060\
887164715678393081238716764475895205278097933518094665131175834239675207\
836127402823181567307209865082016929970230092640996320154580971132957157\
530524665282956585632295316824600887643572316732897881767068394438469465\
636207735131585279483019744492279976144450559792386506026144690102045527\
299809850495848063265844042585090231419915548788173887251577878521385780\
674236804262066289482886765259378145287136068480217483221909258856702496\
919832773826000400790033349094145115446438768295713449810953852035626136\
302107851588263342520250518748078016063562133092893350699458202918774613\
046827878930277297086332246109576852892012162274295504232033729700365293\
951728904077231039906008507912780988714447578844273199522722255028787818\
054354593302408703667887974283778979561321532031324261327671052503223455\
049187891398452696019954039470990107142206893662372942127380553205131560\
334197850240381731427801731600185892296747738625841218889094975766347975\
837416916730781489925536042671064948984519374392815954771082434138166354\
960250633476823334092543946288500384896777011120482698687238208645571630\
687696154883048992113962482198120028499808127136302397802894845770958678\
641867004752959483785207918804420811574615198904629453284858075163376270\
725161906817078542516409198866352509990869373029024471902786641127969078\
033702672676878588898535847870833747654749984748659972060144428656540286\
436039126158075415983227578928692192258322919063104856464463831038559543\
002482120591607511500698861870753945102841058605830753088203159049948906\
939920339887148085526241590846270623863056890892985792057437974959779191\
350192990673008332807364390541577347221462850670269046467378261177678572\
040306244203867660713100285870513660149850199176446265463911528285170736\
882078466371899711853774657589776225974024995511772276588863778832788561\
162195956850340881671591088717439561029453967953300745961025583045086055\
607077554447217193162746794468632281348857964012140108701133437408101903\
480554370555627925950621501673130072919915728273030185331268903896032812\
162309327305793056538581068067591130692554359386021962646720274543136914\
367812768084174523919028896006800495546126307501519984340533934292748771\
327758545083340907976878844368926287728045402134676154814591527891499430\
487219746395045687206619798102782911507736089533352460122320745044852292\
793019874048817932556418455486072877165218271083223996779544454841859975\
164426249615428493091037781169314480373887394975585342147605835263962241\
278577028587632899762856068911067458863420781037018982728703255123974292\
850058088293201106949946832086066135992027648996081531143904201450494725\
793218567650471409586565808350659141328565857181379853737975018563257430\
472088555858288797571623724246239084342084787937663797856662974783516831\
805429095867336620680509311809344892738636528016350814043744466045919197\
841995138985317264860411426564258494292493266662481381043147446898946613\
605577520624241232274521847625326929339666391379130320750089660853193592\
373337883419765323832420201856511385915327747076674559532816447692989695\
182209742311310449614893282488767593843427187114108642215564843835843579\
448047679400014380249499892125182213876203668343618751682895676849580077\
573849861206132002592233584176960375475511685823713548807157942228957443\
959807074994789942454175009228796006425687297913430654882093779366849261\
864708308885165835067791258641315582447341861375721590288478976326961705\
430825432199477737581294179573508217677147011737643694286721167094891824\
686837602771349305552454231519915375805621391350878772572697280259309350\
816805024383538910956645632624283038582459751165265885575923560758569945\
137910620374706998699610396049301916273801767040029188725323641485255554\
431494448504983397846418380368158139035852341221020703142832508907693017\
036587444909616255808233427699731035389329293969614807089014137924587253\
093900999493933836932966324908778669517805376302086296184689501923430131\
202981419777258919172938057270988598360699557806500195638142225214299983\
173730834032299883588056330051213866835060494088436498950899274578818384\
148105773002307355106277791730237958859327561868548857713690167569827188\
800094863896968211893041281914484219750361490567152839689748073080046202\
387718115313205971731684905693212475796176779817924045565986653433718202\
001204855398029003735008613386891092507003725856824871693179081617744656\
440123881223542254212546987478538746395992698993356343425430974094753190\
970650230909309724784932031271486218899210375637181019122887083950143693\
070693575529804527265678661940474263814662946163852686627692322548125429\
482948718438029628682311992364568897658180539214245602139497383494351195\
379355766468052617040665577565475896839329250964790507524543140641289315\
589562168828344787289114152316393618774902982094218227552399654922829892\
715259835292515834929041711743568180495642767906231484851900824593497246\
019599224720243341513911764908763282064292265774096705829854045737426633\
213307584779106724323702476421400297129909007924936249466681264376722396\
313492402336666605584834347124975324296266873518726285033711129105296087\
208951178755411903833504836957036234258946712218688684079765512340311854\
802087283001085350387394427461398577631468911230446972014353246528919338\
392443615815645748774271532569236358425869609670597667528836706417459353\
979397521406202899489125139949198529759908824083255519032648182079553593\
964036797065077994188147851433505318336262832382531466400486279426341502\
663133592793075603323514904100247516906713139531321349778089140675966367\
101605254549507065399112143420581403266241747877789549204754867697333820\
826814464476687029314211199312283048876986524477895058222351722572974111\
972746635484768756240554467530771685637170329840021394917817597369287053\
773181801366796404825884734292886594735243393279727613872774859145653262\
384426564199804081129847782909371991879510672165783312863576018021014194\
617538128743074699421612208059690816202101924644781412204673158722395998\
580212985729140964765952049918427190183908259503700548594315663894402024\
767783736680594179341427568236022515330985555280364669202272146706143673\
017394856831463924265091231496882816603374586055828151300042567956960998\
472745950719878694160413672486448083139099841457190033239475776005217808\
036595761137210848416552259346670788962601695773782607784273379166272268\
327419379677522409836042146862800372983491876682896079050626628660671569\
428797070689656155166463103342927137266106448900052889755360968890038707\
620892731319759076738806431086977883162660645778226738737443328302103432\
407177400851754171746101836757543881647846504021310844532780904634660209\
872747439476922445875506183340917948662018755252495718053933894847512306\
153891441862573764279699186177609124667213922478950220114934845987501458\
948801169300412296578374514857116778061606643697455427363213973033476463\
710608793340149193221041240864653368041062244276552933001147286696080049\
148808465732817477007840977839870535723904508297971074331807970462137433\
212920931239043737385357053030071309503286215846801891070412236452289070\
543771913603027215926934370694007924265783101948422133883961990764113407\
013858399167628286717327828296290276361677241280967443589332835636282898\
142778384777187273017253959883151384784343052398868136921470460316379086\
664608651064117629802872540763972102606380773228698821494873059142827843\
611166691463358497625596647561385740741878267203016218554870361128246723\
542499074159071489246178855449274643447452125716979796772370248947963652\
062999854758916878605251085246210787478912099778068980458107281903381997\
028643762006740071673367427818018678777737286354608719512822171726113600\
943043915127194476603680926349582703592401966122299178887439221943648870\
223872912124134153001168034403566931767839024875082358141108487011731536\
311721101093414282558179008207244155597779726940462746566238427475788681\
618880072122076684356110152770859881582950670466989324566546593588238699\
255593600587009542746915060253271031430278347369142462298455068856581247\
410053864471983583397795528440330800372825196751918396353442488891712413\
511377961708602572192993505623598923618771798170601481235348358035667584\
453961868867051316824463756468785429166629668237718339239222632598066496\
978323318096118782406335713175027873726210220713360143698059723628810966\
128152700772912880082807601113595914707311771732516122074149297599614898\
620586371363887099795916694892918675493077627182197597044286521897836895\
697658367969050446849293570990290904480831351099589837331290869433922132\
414842996547480201303657826972120867619712272938900254995415708288506460\
261189732807669008806844476210848414264176605406201421113250158614645178\
481591429584629456408597789538792256604176665962863093798396278203135025\
523958851473068442018855201385633166040516046786184618925292112809749767\
179947699845349402854319179884912746892064374218534226712213103905433397\
155030856034736568958931802079139665422922028585847596858505141326197753\
424164122655006771043244667045800468202806513831062682703792858515559023\
991835558153036940974999534885986883516015332709642846903652067830565657\
602546768505340972212407727579791674741553815625765716175150956404552052\
053833368399553459521440808869141370197667492955411421283920349896216723\
130168776529566738411052970746672836904565067538110127405717531209991088\
223841870897526885598453360000920384917718568663608096773253689359397679\
595177473322267633075931534590575042471722043031037193502654786691032584\
244105197723664707689378085573818335019015049814167791024628799654934417\
598529033057287864059631941220289671492545589934250809969928214390198186\
343013145762807103817977798494783160346950125526565039025198359997530660\
184090704209497021798267077990200844938553156407287611861514077794745232\
230240076008092814705084937789806016064327429156762100098802659828794938\
762205791418364774436988925687170696578521334732514530269139813826217885\
941741945814819020171881277749678378745756549939334397972936764514483341\
074778787512677228534451718730954592445577605941227571004435601838622581\
872900331740483353194658863564156497865964884211180104903407200346404538\
47115950007960136056834
3 	7 	Mersenne Prime 	14
5 	31 	Mersenne Prime 	37634
7 	127 	Mersenne Prime 	2005956546822746114
11 	2047 	68729682406644277238837486231747530924247154108646671752192618583088487405790957964732883069102561043436779663935595172042357306594916344606074564712868078287608055203024658359439017580883910978666185875717415541084494926500475167381168505927378181899753839260609452265365274850901879881203714
13 	8191 	Mersenne Prime 	22313995867897900769603796342295788566208710409165129831038160968311491946220319893407703857721437957260314978754160034503401040789215400628158170099668522698066550221265307171574634992724727060201120758890920172789110609085990337846018634451646739004908975710893057017831784106285989578600398251364366079398506512806386775247318462388007386288293644987819640076171556974003404195908596970825853990347990259288695088334854125701652040860084239663064263605520384355127215307437936591866962296906419378104850899571605034504288737636564836267334726723727575106663971046844142763512854023937849655467693015631287929701909077381005060802853209341459156871829180256316747660704875518660035573112882904493746617877304844878674402542586943400547464667179926000026596616252849884072241228637895801783293732168802374542280341992348946606531635000814995246895089041641203184136132975956905572518723976402989858509003359081748048869560319466898146867908972088453016102089761833396052479183215782590173494080725569259056977955738902892341951393866495222420379013713784627095469233910359313068881745808900306832764925725008680492006161979334986865505218272485914888669136966553469714434
17 	131071 	Mersenne Prime 	3777787916227967545219507695611320571893168863110330918815737760160999876510173466829356390282853703135991255190310143637482475685623883818819860659552521150242939955995157584313371089392600849352544523629258447497328163442385842723777728304246600417689247961467042868438599925503393369920243687441868884100380776551454757739407763522127518582128581575999678740727703501270733266236635828216406618294574653780508565482254373213090079648342481693452345770381769771338563746691599648908001550513766279227363371123455669682220424921728560618378912275216315475422280777232825541807076639403715660566331485325009880122756615934761159231989061311471684183610063259415955132075974602321070441642713165000555433375028472669837755634934089602917958298261234154301410745974027232194736762158887175346012432642114417598429058786054883517673358780679327708192440114814633522770848408307715033752498697781253567639304629726687716602150346417297811366657636835254435645658400616931541265301843530421792474790102415993553272195599119141309016280343390794781921660947970501344185991646669767967697181606494267618635881530755321846177959335861365489243377856061092786918288191876492859380296311678367418356372719326115567899593899573964787909013942277577687514849758461635452138699708431133319003470075395039517030156786783145008968649920805210215604752868973730934612760071982977004731100748818191279776767983574621209766929216153303104896684525826712019500660604642476055864623340262181903013794437976419682801553104357859758366409630280506813257310723355933049328008511420627314375845136607832087420028897272413195668525331791923548347612844733473427363121635067904690582734331883342831324648573318573086695124832693945520996760374644732956040686141021868656585097627356654412783453163464079720044130433347350371268191881752487691895319451713927050571438874020487318589374717464765288550187957531824699594656521881522363851207160087358423363394108187907766374592922401781451484228158054890594327838762779149174728072948341164579368824974038766686779539384055208995516816687281372537962202965973659528126073653794477652541847857119708551528627433154035412758876663660923198592276292495894596287431460435065343875744104209342864410487964602169958809139876095384584493143058339705440055149943520733553394447195874042251890226114362754264869402127775563759393977871385035395635308330739898549549038945893494550018133137061162638073030923391358791136022137936526776187072465115179916623554886901069809387621723720451987036511138938360049826884059490819070861031796637301730601134689852925559378991868439420197097241043418847441495738525517830996526418143172663192741061306372114172004730914529297950796399973428070580444586907677535721636532330817428353342270641496802116565805029950254776215746953780921288886749804066699148782366290353316047430238835491022493439934154649485985940174115776260832299978831788652409792836878861787010772453059011904460769114078723095200267690965465980951726566436431265605564956779687120276883563496392347856162039400885714455959255963128383099206053714849633287161957650729103008088419625194007688774893861142233983486677540629657934447979480445570696778618075490713133667973009993461056287239502977970134696234837244148672804694045439698678946034008469949391339559789790903219784250141612248236917648653001439772003911947432856618699127437450903394499693622906122478640510714397387308543862655257111660227899445391972554200970239873231570919634045500554334711697609734460946503896230126537898342933885242142177162159866296148268551891976160518173271527657791306193627640411331392419826011305275453965690760143714629523798459411790856620960690782178545082977917895276339112649965682980820319635275799002184055978574113561166542272178005361627484701051712725216852693217020858978732607599430257942515474599198525225432756269742634153246038652626299503359996461052639204175832761402332777071673427282419176312268982726126526568654320405872553070147733543677870633063661842467943733010501887602835635079846368197713944662877839284057896971343528270402525619255566602154213506895712819467572832715748868788823325620867451079815414278293986546156190710715788575130551623470832385274373716379615696094761632533536020222029153577862562656868987551539369367743781089030959042094610739955250647621290636206085242002449555019921452138024561469478880146895071939645479123008102260820126819582829309435543202371247051092881948976916167154064117511617494741648282580685764881938432897568413655792590587093972060860531971806843621463318199371060625429147486755866332368913639709857375815269044193727169203115578372875265550836237489517649627278017118745953484109800747018307096983697610490794323841293455288113847210178155791177855149374307529648096584057715188689208943876872914043226017665212590584757643510266751597791278381804719058111410162732032175401972471950894121447879402089832017562246894412413992749926882632777217222171951737484094635577212826152658012843777508928974591420457138589463642682388491783329269940587689740274353113911017394659609078297676086893955602775899810966542385618700304674454572746811013672028881970077757392054230168101908294469025514499369992620765085134588668898739275723380921142790049236856206722401692706672174694735845743840271970910631221861479194919582792914551917297426880555923636676325599595877711428135264733297843195099001521661066313214402367971027773036206293731952833505340124144864036280389962632943847165572398898292903518266903517862619368073809105072456518624716545731393129743665230618706611770027057879963925404675705106050360847489491642485493564607988245359835800725801446339703115050135329967293254713891071014084732447359907373964823878551325365085476597068535407993147842157534535961375503223640655661237478137824452923740910089996726805078269404985765926693287318458722729990758498790181910877379338288971917987318145787940539941694163199763506987746991081625403826364506313270131876862060887218103873492482986769600011714502861292731368910998762544457266417075550545023593904342772794119305533582367905979382054922988040304254646854508281642229770794140625386286216922526389819015903901221261812077336417312434493854580351937407846851181432344040025043041307665920518038446486634143814535257611815299211497004100843525707096591040141120144148660515835814214356226954060471507055041886416069752654527467740268033799587198068140783853928942898342886437810508135265375951524933114619729908381264788510370771139284192761000297955773395969989799972086508273963870100611221967406248626276686408885762669615473533774794168835833498946753061889500366460491954493027466759140082891850229468402663129539666891032161720218299492254177893778603361075849293348232361857458029076928888855843266351641886414907523525563108675291931971844807887687600859980448097293954258993036979405331065203141381904881438726016528695906580137655126845562568385553573732361917829246215269063314733030834157509790171463337270488543981136176832805347984052601514244587503571872433621413545687387131057577408509287328236184468564853901037110797426889015305156935539313061494881434054296406742337369145904529949301738942965869702289399068023280693242958652536984631272990703024282426258757465508531964954066021496093326042263634089117875235165290274346586239062457490070724572369090486583866522874942539590315776822919048792562295294751112690126967608668785745436505120258844761707779103564067167029023286413635492564384851109166826015952786512317894626711273375931557436050452788219688806833901749732829200561324935126199949862664868204587741627512153769234772808394467748126490836810001610076725043936097888165772072312320418772657367361001927180961501217794136085838447995851141411847540258060172891106603784924475487290454894381537915344412813520823379624727792599381657334593960999343225691985366682380393851229834076957979481003762779341297092040255643986419148828472358341488873057113253640853705544440730524787380742751470320370450434681760207156853173343850064711920617660600723447689115197406177973021932626134123682189819405196556830995406773408926472543746003631598171082148140366882972942565970858020926927331960207723636076420751361735323229000117384145135987681734029923407705047892738852820876519112452321115133961430904365923347412617824234946834291983587695855297224553248661638456944453700356245633278692316671274654054291206914232983378263018670309216453502746543231096762232594886270031079104460844284914807856213935049124967051068072093025140343603208841497755404436156436059644258869248668453433781246832627135315030503699856839525117890428245593422292379420268744215506075760803754466359500291192507129148193684665982198089200419703509446513733598973723606088716471567839308123871676447589520527809793351809466513117583423967520783612740282318156730720986508201692997023009264099632015458097113295715753052466528295658563229531682460088764357231673289788176706839443846946563620773513158527948301974449227997614445055979238650602614469010204552729980985049584806326584404258509023141991554878817388725157787852138578067423680426206628948288676525937814528713606848021748322190925885670249691983277382600040079003334909414511544643876829571344981095385203562613630210785158826334252025051874807801606356213309289335069945820291877461304682787893027729708633224610957685289201216227429550423203372970036529395172890407723103990600850791278098871444757884427319952272225502878781805435459330240870366788797428377897956132153203132426132767105250322345504918789139845269601995403947099010714220689366237294212738055320513156033419785024038173142780173160018589229674773862584121888909497576634797583741691673078148992553604267106494898451937439281595477108243413816635496025063347682333409254394628850038489677701112048269868723820864557163068769615488304899211396248219812002849980812713630239780289484577095867864186700475295948378520791880442081157461519890462945328485807516337627072516190681707854251640919886635250999086937302902447190278664112796907803370267267687858889853584787083374765474998474865997206014442865654028643603912615807541598322757892869219225832291906310485646446383103855954300248212059160751150069886187075394510284105860583075308820315904994890693992033988714808552624159084627062386305689089298579205743797495977919135019299067300833280736439054157734722146285067026904646737826117767857204030624420386766071310028587051366014985019917644626546391152828517073688207846637189971185377465758977622597402499551177227658886377883278856116219595685034088167159108871743956102945396795330074596102558304508605560707755444721719316274679446863228134885796401214010870113343740810190348055437055562792595062150167313007291991572827303018533126890389603281216230932730579305653858106806759113069255435938602196264672027454313691436781276808417452391902889600680049554612630750151998434053393429274877132775854508334090797687884436892628772804540213467615481459152789149943048721974639504568720661979810278291150773608953335246012232074504485229279301987404881793255641845548607287716521827108322399677954445484185997516442624961542849309103778116931448037388739497558534214760583526396224127857702858763289976285606891106745886342078103701898272870325512397429285005808829320110694994683208606613599202764899608153114390420145049472579321856765047140958656580835065914132856585718137985373797501856325743047208855585828879757162372424623908434208478793766379785666297478351683180542909586733662068050931180934489273863652801635081404374446604591919784199513898531726486041142656425849429249326666248138104314744689894661360557752062424123227452184762532692933966639137913032075008966085319359237333788341976532383242020185651138591532774707667455953281644769298969518220974231131044961489328248876759384342718711410864221556484383584357944804767940001438024949989212518221387620366834361875168289567684958007757384986120613200259223358417696037547551168582371354880715794222895744395980707499478994245417500922879600642568729791343065488209377936684926186470830888516583506779125864131558244734186137572159028847897632696170543082543219947773758129417957350821767714701173764369428672116709489182468683760277134930555245423151991537580562139135087877257269728025930935081680502438353891095664563262428303858245975116526588557592356075856994513791062037470699869961039604930191627380176704002918872532364148525555443149444850498339784641838036815813903585234122102070314283250890769301703658744490961625580823342769973103538932929396961480708901413792458725309390099949393383693296632490877866951780537630208629618468950192343013120298141977725891917293805727098859836069955780650019563814222521429998317373083403229988358805633005121386683506049408843649895089927457881838414810577300230735510627779173023795885932756186854885771369016756982718880009486389696821189304128191448421975036149056715283968974807308004620238771811531320597173168490569321247579617677981792404556598665343371820200120485539802900373500861338689109250700372585682487169317908161774465644012388122354225421254698747853874639599269899335634342543097409475319097065023090930972478493203127148621889921037563718101912288708395014369307069357552980452726567866194047426381466294616385268662769232254812542948294871843802962868231199236456889765818053921424560213949738349435119537935576646805261704066557756547589683932925096479050752454314064128931558956216882834478728911415231639361877490298209421822755239965492282989271525983529251583492904171174356818049564276790623148485190082459349724601959922472024334151391176490876328206429226577409670582985404573742663321330758477910672432370247642140029712990900792493624946668126437672239631349240233666660558483434712497532429626687351872628503371112910529608720895117875541190383350483695703623425894671221868868407976551234031185480208728300108535038739442746139857763146891123044697201435324652891933839244361581564574877427153256923635842586960967059766752883670641745935397939752140620289948912513994919852975990882408325551903264818207955359396403679706507799418814785143350531833626283238253146640048627942634150266313359279307560332351490410024751690671313953132134977808914067596636710160525454950706539911214342058140326624174787778954920475486769733382082681446447668702931421119931228304887698652447789505822235172257297411197274663548476875624055446753077168563717032984002139491781759736928705377318180136679640482588473429288659473524339327972761387277485914565326238442656419980408112984778290937199187951067216578331286357601802101419461753812874307469942161220805969081620210192464478141220467315872239599858021298572914096476595204991842719018390825950370054859431566389440202476778373668059417934142756823602251533098555528036466920227214670614367301739485683146392426509123149688281660337458605582815130004256795696099847274595071987869416041367248644808313909984145719003323947577600521780803659576113721084841655225934667078896260169577378260778427337916627226832741937967752240983604214686280037298349187668289607905062662866067156942879707068965615516646310334292713726610644890005288975536096889003870762089273131975907673880643108697788316266064577822673873744332830210343240717740085175417174610183675754388164784650402131084453278090463466020987274743947692244587550618334091794866201875525249571805393389484751230615389144186257376427969918617760912466721392247895022011493484598750145894880116930041229657837451485711677806160664369745542736321397303347646371060879334014919322104124086465336804106224427655293300114728669608004914880846573281747700784097783987053572390450829797107433180797046213743321292093123904373738535705303007130950328621584680189107041223645228907054377191360302721592693437069400792426578310194842213388396199076411340701385839916762828671732782829629027636167724128096744358933283563628289814277838477718727301725395988315138478434305239886813692147046031637908666460865106411762980287254076397210260638077322869882149487305914282784361116669146335849762559664756138574074187826720301621855487036112824672354249907415907148924617885544927464344745212571697979677237024894796365206299985475891687860525108524621078747891209977806898045810728190338199702864376200674007167336742781801867877773728635460871951282217172611360094304391512719447660368092634958270359240196612229917888743922194364887022387291212413415300116803440356693176783902487508235814110848701173153631172110109341428255817900820724415559777972694046274656623842747578868161888007212207668435611015277085988158295067046698932456654659358823869925559360058700954274691506025327103143027834736914246229845506885658124741005386447198358339779552844033080037282519675191839635344248889171241351137796170860257219299350562359892361877179817060148123534835803566758445396186886705131682446375646878542916662966823771833923922263259806649697832331809611878240633571317502787372621022071336014369805972362881096612815270077291288008280760111359591470731177173251612207414929759961489862058637136388709979591669489291867549307762718219759704428652189783689569765836796905044684929357099029090448083135109958983733129086943392213241484299654748020130365782697212086761971227293890025499541570828850646026118973280766900880684447621084841426417660540620142111325015861464517848159142958462945640859778953879225660417666596286309379839627820313502552395885147306844201885520138563316604051604678618461892529211280974976717994769984534940285431917988491274689206437421853422671221310390543339715503085603473656895893180207913966542292202858584759685850514132619775342416412265500677104324466704580046820280651383106268270379285851555902399183555815303694097499953488598688351601533270964284690365206783056565760254676850534097221240772757979167474155381562576571617515095640455205205383336839955345952144080886914137019766749295541142128392034989621672313016877652956673841105297074667283690456506753811012740571753120999108822384187089752688559845336000092038491771856866360809677325368935939767959517747332226763307593153459057504247172204303103719350265478669103258424410519772366470768937808557381833501901504981416779102462879965493441759852903305728786405963194122028967149254558993425080996992821439019818634301314576280710381797779849478316034695012552656503902519835999753066018409070420949702179826707799020084493855315640728761186151407779474523223024007600809281470508493778980601606432742915676210009880265982879493876220579141836477443698892568717069657852133473251453026913981382621788594174194581481902017188127774967837874575654993933439797293676451448334107477878751267722853445171873095459244557760594122757100443560183862258187290033174048335319465886356415649786596488421118010490340720034640453847115950007960136056834

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).

def Lehmer2(n,Mp): if n == 1: return 4 pow = Lehmer2(n-1,Mp) s = pow^2 s -= 2 s = s % Mp return s 
       
def Mersenne4(N): odd_primes = [p for p in range(3,N,2) if is_prime(p)] for p in odd_primes: Mp = 2^p-1 s = Lehmer2(p-1,Mp) if s%Mp == 0: print p,'\t',Mp,'\tMersenne Prime','\t',s else: print p,'\t',Mp,'\t',s 
       
Mersenne4(150) 
       
3 	7 	Mersenne Prime 	0
5 	31 	Mersenne Prime 	0
7 	127 	Mersenne Prime 	0
11 	2047 	1736
13 	8191 	Mersenne Prime 	0
17 	131071 	Mersenne Prime 	0
19 	524287 	Mersenne Prime 	0
23 	8388607 	6107895
29 	536870911 	458738443
31 	2147483647 	Mersenne Prime 	0
37 	137438953471 	117093979072
41 	2199023255551 	856605019673
43 	8796093022207 	5774401272921
47 	140737488355327 	96699253829728
53 	9007199254740991 	5810550306096509
59 	576460752303423487 	450529175803834166
61 	2305843009213693951 	Mersenne Prime 	0
67 	147573952589676412927 	44350645312365507266
71 	2361183241434822606847 	271761692158955752596
73 	9444732965739290427391 	2941647823169311845731
79 	604462909807314587353087 	149246123283525944719226
83 	9671406556917033397649407 	7426393223211489353123218
89 	618970019642690137449562111 	Mersenne Prime 	0
97 	158456325028528675187087900671 	138799132171283648987055810555
101 	2535301200456458802993406410751 	2457457639868305855274916344886
103 	10141204801825835211973625643007 	4473275459952545161188509965118
107 	162259276829213363391578010288127 	Mersenne Prime 	0
109 	649037107316853453566312041152511 	80310482899578688674364643057506
113 	10384593717069655257060992658440191
	6600791243740670132758919227993337
127 	170141183460469231731687303715884105727 	Mersenne Prime 	0
131 	2722258935367507707706996859454145691647
	1720152102472260647526711808965574882231
137 	174224571863520493293247799005065324265471
	90145568356072673645446219346258028265320
139 	696898287454081973172991196020261297061887
	181318185791829225812656754645855481517572
149 	713623846352979940529142984724747568191373311
	267073170876646890164052223831706652997781887
3 	7 	Mersenne Prime 	0
5 	31 	Mersenne Prime 	0
7 	127 	Mersenne Prime 	0
11 	2047 	1736
13 	8191 	Mersenne Prime 	0
17 	131071 	Mersenne Prime 	0
19 	524287 	Mersenne Prime 	0
23 	8388607 	6107895
29 	536870911 	458738443
31 	2147483647 	Mersenne Prime 	0
37 	137438953471 	117093979072
41 	2199023255551 	856605019673
43 	8796093022207 	5774401272921
47 	140737488355327 	96699253829728
53 	9007199254740991 	5810550306096509
59 	576460752303423487 	450529175803834166
61 	2305843009213693951 	Mersenne Prime 	0
67 	147573952589676412927 	44350645312365507266
71 	2361183241434822606847 	271761692158955752596
73 	9444732965739290427391 	2941647823169311845731
79 	604462909807314587353087 	149246123283525944719226
83 	9671406556917033397649407 	7426393223211489353123218
89 	618970019642690137449562111 	Mersenne Prime 	0
97 	158456325028528675187087900671 	138799132171283648987055810555
101 	2535301200456458802993406410751 	2457457639868305855274916344886
103 	10141204801825835211973625643007 	4473275459952545161188509965118
107 	162259276829213363391578010288127 	Mersenne Prime 	0
109 	649037107316853453566312041152511 	80310482899578688674364643057506
113 	10384593717069655257060992658440191 	6600791243740670132758919227993337
127 	170141183460469231731687303715884105727 	Mersenne Prime 	0
131 	2722258935367507707706996859454145691647 	1720152102472260647526711808965574882231
137 	174224571863520493293247799005065324265471 	90145568356072673645446219346258028265320
139 	696898287454081973172991196020261297061887 	181318185791829225812656754645855481517572
149 	713623846352979940529142984724747568191373311 	267073170876646890164052223831706652997781887

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.

def Lehmer3(p,Mp): s = 4 for k in [2,..,p]: s = ((s^2)-2)%Mp #print s return s def Mersenne5(N): odd_primes = [p for p in range(3,N,2) if is_prime(p)] for p in odd_primes: Mp = 2^p-1 if Lehmer3(p-1,Mp)==0: print p,'\t',Mp,'\tMersenne Prime' 
       
time Mersenne5(1000) 
       
3 	7 	Mersenne Prime
5 	31 	Mersenne Prime
7 	127 	Mersenne Prime
13 	8191 	Mersenne Prime
17 	131071 	Mersenne Prime
19 	524287 	Mersenne Prime
31 	2147483647 	Mersenne Prime
61 	2305843009213693951 	Mersenne Prime
89 	618970019642690137449562111 	Mersenne Prime
107 	162259276829213363391578010288127 	Mersenne Prime
127 	170141183460469231731687303715884105727 	Mersenne Prime
521
	68647976601306097149819007990813932172694353001433054093944634591855431\
833976560521225596406614545549772963113914808580371219879997166438125740\
28291115057151 	Mersenne Prime
607
	53113799281676709868958820655246862732959311772703192319944413820040355\
986085224273916250226522928566888932948624650101534657933765270723940951\
9978766587351943831270835393219031728127 	Mersenne Prime
Time: CPU 0.16 s, Wall: 0.16 s
3 	7 	Mersenne Prime
5 	31 	Mersenne Prime
7 	127 	Mersenne Prime
13 	8191 	Mersenne Prime
17 	131071 	Mersenne Prime
19 	524287 	Mersenne Prime
31 	2147483647 	Mersenne Prime
61 	2305843009213693951 	Mersenne Prime
89 	618970019642690137449562111 	Mersenne Prime
107 	162259276829213363391578010288127 	Mersenne Prime
127 	170141183460469231731687303715884105727 	Mersenne Prime
521 	6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151 	Mersenne Prime
607 	531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127 	Mersenne Prime
Time: CPU 0.16 s, Wall: 0.16 s

What is the largest known Mersenne Prime?  

When was it discovered and by whom?

#2^57885161-1 is the largest, and it was discovered by the "Great Internet Mersenne Prime Search" 
       

The Graph Class

class Graph(object): '''Represents a graph''' def __init__(self, vertices, edges): '''A Graph is defined by its set of vertices and its set of edges.''' self.V = set(vertices) self.E = set([]) self.Adj = {} self.add_edges(edges) print '(Initializing a graph with %d vertices and %d edges)' % (len(self.V),len(self.E)) def add_vertices(self,vertex_list): ''' This method will add the vertices in the vertex_list to the set of vertices for this graph. Since V is a set, duplicate vertices will not be added to V. ''' for v in vertex_list: self.V.add(v) self.build_Adj() def add_edges(self,edge_list): ''' This method will add a list of edges to the graph It will insure that the vertices of each edge are included in the set of vertices (and not duplicated). It will also insure that edges are added to the list of edges and not duplicated. ''' for s,t in edge_list: if (s,t) not in self.E and (t,s) not in self.E: self.V.add(s) self.V.add(t) self.E.add((s,t)) self.build_Adj() def build_Adj(self): self.Adj = {} for v in self.V: self.Adj[v] = [] for e in self.E: s,t = e self.Adj[s].append(t) self.Adj[t].append(s) def Degree(self,v): return len(self.Adj[v]) def plot(self,Vc): # Vc is a dictionary with the coordinates for each vertex g = Graphics() # Create the list of coordinates Vcoords = [Vc[v] for v in self.V] # Include the vertices as red dots g += point2d(Vcoords,rgbcolor=(1,0,0),size=25) # Include the names of the vertices for v in self.V: g += text(v,(1.1*Vc[v][0], 1.1*Vc[v][1])) # Include the edges for edge in self.E: u,v = edge g += line([Vc[u],Vc[v]]) return g def build_Components(self): Visited = {} for v in self.V: Visited[v] = False components = [] Q = Queue() for v0 in self.V: if not Visited[v0]: comp = [] Visited[v0] = True Q.enqueue(v0) while 0 < len(Q): u = Q.dequeue() comp.append(v) for v in self.Adj[u]: if not Visited[v]: Visited[v] = True Q.enqueue(v) components.append(comp) return components def is_connected(self): Visited = {} for v in self.V: Visited[v] = False Q = Queue() for v0 in self.V: if not Visited[v0]: Visited[v0] = True Q.enqueue(v0) while 0 < len(Q): u = Q.dequeue() for v in self.Adj[u]: if not Visited[v]: Visited[v] = True Q.enqueue(v) break for v in self.V: if not Visited[v]: # The Graph is not connected return False # The Graph is connected return True 
       

The Prime Maze

The following blocks define and display the Prime Maze.

# The dictionary of edges and weights for the Prime Maze WPM = {('A', 'B'): 2, ('A', 'C'): 8, ('A', 'D'): 10, ('A', 'E'): 5,\ ('B', 'D'): 14, ('B', 'J'): 17, ('C', 'D'): 12, ('C', 'G'): 3,\ ('C', 'H'): 10, ('D', 'H'): 4, ('E', 'F'): 2, ('E', 'N'): 6,\ ('F', 'G'): 6, ('F', 'O'): 6, ('G', 'O'): 4, ('H', 'T'): 8,\ ('I', 'J'): 8, ('I', 'K'): 4, ('I', 'L'): 6, ('J', 'M'): 10,\ ('J', 'S'): 6, ('K', 'P'): 12, ('K', 'Q'): 12, ('L', 'M'): 12,\ ('L', 'Q'): 8, ('M', 'R'): 8, ('N', 'O'): 2, ('N', 'V'): 4,\ ('O', 'V'): 12, ('P', 'T'): 6, ('P', 'U'): 4, ('Q', 'R'): 10,\ ('R', 'S'): 12, ('S', 'W'): 13, ('T', 'U'): 14, ('U', 'W'): 10,\ ('V', 'W'): 2 } # print 'WPM',WPM WW = copy(WPM) for edge in WPM.keys(): u,v = edge WW[(v,u)] = WPM[edge] # print 'WW',WW 
       
# The coordinates for displaying the graph PMV = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','P','Q','R','S','T','U','V','W'] PMcoord = {'B':(-3,3),'A':(0,3),'E':(3,3)} PMcoord['J']=(-3,2); PMcoord['D']=(-1,2); PMcoord['C']=(1,2); PMcoord['F']=(2,2) PMcoord['I']=(-1,1); PMcoord['H']=(0,1); PMcoord['G']=(1,1) PMcoord['M']=(-2,0); PMcoord['L']=(-1,0); PMcoord['K']=(0,0); PMcoord['T']=(1,0); PMcoord['O']=(2,0); PMcoord['N']=(3,0) PMcoord['R']=(-2,-1); PMcoord['Q']=(-1,-1); PMcoord['P']=(0,-1); PMcoord['U']=(2,-1) PMcoord['S']=(-3,-2); PMcoord['W']=(0,-2); PMcoord['V']=(3,-2) # print 'PMcoord', PMcoord 
       
# Construct the Graph of the Prime Maze and display it PMG = Graph([],WPM.keys()) print 'Graph of the Prime Maze' Gpm = PMG.plot(PMcoord) for edge in PMG.E: s,t = edge xs,ys = PMcoord[s] xt,yt = PMcoord[t] w = WPM[edge] Gpm += text(w,((xs+xt)/2, 0.2+(ys+yt)/2)) show(Gpm,axes=False) 
       
(Initializing a graph with 23 vertices and 37 edges)
Graph of the Prime Maze
(Initializing a graph with 23 vertices and 37 edges)
Graph of 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.  

def prime_maze(new_vertex, distance, count): # Is the distance a prime number? # If not return count if not is_prime(distance): return count # If it is, append this new_vertex to the path path.append(new_vertex) # If new_vertex is the same as the first vertex in the path # then we have found a complete cycle # print the result, add 1 to the count and return count if new_vertex == path[0]: print distance print path count += 1 # Otherwise press on, check out - recursively - every edge connected to new_vertex # This will be very similar to the loop inside the Prime Maze Search Code. else: for v in PMG.Adj[new_vertex]: edge = (new_vertex,v) count = prime_maze(v,distance+WW[edge],count) path.pop() return count 
       
# Prime Maze Search Code for start_node in PMG.V: path = [start_node] count = 0 for v in PMG.Adj[start_node]: edge = (start_node,v) count = prime_maze(v, WW[edge], count) print start_node, ': ', count 
       
A :  0
C :  0
523
['B', 'J', 'S', 'J', 'I', 'K', 'Q', 'L', 'I', 'K', 'P', 'T', 'U', 'P',
'T', 'U', 'W', 'V', 'O', 'V', 'N', 'E', 'N', 'O', 'V', 'N', 'O', 'V',
'O', 'G', 'F', 'O', 'V', 'O', 'F', 'E', 'N', 'V', 'W', 'U', 'T', 'P',
'U', 'T', 'P', 'K', 'I', 'L', 'Q', 'K', 'I', 'L', 'M', 'R', 'Q', 'K',
'P', 'T', 'H', 'C', 'D', 'C', 'A', 'D', 'B']
B :  1
E :  0
D :  0
G :  0
F :  0
I :  0
H :  0
K :  0
J :  0
M :  0
L :  0
O :  0
N :  0
Q :  0
P :  0
S :  0
R :  0
U :  0
T :  0
W :  0
V :  0
A :  0
C :  0
523
['B', 'J', 'S', 'J', 'I', 'K', 'Q', 'L', 'I', 'K', 'P', 'T', 'U', 'P', 'T', 'U', 'W', 'V', 'O', 'V', 'N', 'E', 'N', 'O', 'V', 'N', 'O', 'V', 'O', 'G', 'F', 'O', 'V', 'O', 'F', 'E', 'N', 'V', 'W', 'U', 'T', 'P', 'U', 'T', 'P', 'K', 'I', 'L', 'Q', 'K', 'I', 'L', 'M', 'R', 'Q', 'K', 'P', 'T', 'H', 'C', 'D', 'C', 'A', 'D', 'B']
B :  1
E :  0
D :  0
G :  0
F :  0
I :  0
H :  0
K :  0
J :  0
M :  0
L :  0
O :  0
N :  0
Q :  0
P :  0
S :  0
R :  0
U :  0
T :  0
W :  0
V :  0