_________________________________
|
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.
|
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 8.90 s, Wall: 8.92 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 8.90 s, Wall: 8.92 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:
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.
|
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.87 s, Wall: 0.87 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.87 s, Wall: 0.87 s |
|
|
|
|
|
|
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.
|
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.22 s, Wall: 1.22 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.22 s, Wall: 1.22 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.
|
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 214.91 s, Wall: 219.24 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 214.91 s, Wall: 219.24 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().
|
The function, Lehmer, is defined recursively as
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.
|
|
|
|