Drorbn - User contributions [en]

10-1100

2010-12-08T23:00:28Z

Cjeagle:

__NOEDITSECTION__
__NOTOC__
{{10-1100/Navigation}}
==Core Algebra I==
===Department of Mathematics, University of Toronto, Fall 2010===

{{10-1100/Crucial Information}}

===Texts===
Lang's ''Algebra'', Selick's [http://www.math.toronto.edu/mat1100/ lecture notes for this class], Dummit and Foote's ''Abstract Algebra'', Hungerford's ''Abstract Algebra''.

===Further Resources===

* [http://www.math.utoronto.ca/cms/graduate-program/ Graduate Studies] at the [http://www.math.toronto.edu/ UofT Math Department]. In particular, [http://www.math.utoronto.ca/cms/tentative-2010-2011-graduate-course-descriptions/ Graduate Course Descriptions].

* My {{Pensieve Link|Classes/10-1100/|10-1100 notebook}}.

* Paul Selick's [http://www.math.toronto.edu/mat1100/ 2007 class].

* Some (mostly complete) notes from this year's class: [[10-1100-Notes]].

10-1100-Notes

2010-12-08T22:39:15Z

Cjeagle:

I have been typing [http://katlas.math.toronto.edu/drorbn/images/c/c5/10-1100-AlgebraNotes.pdf notes] throughout the course, and have put them on the wiki in case they are of value to anyone. They are largely unedited (sorry!), and in particular there are some places where pictures were used to aid a proof in class, and those pictures do not appear in these notes. Nevertheless, I hope that they are a useful guide to what we covered. [[User:Cjeagle|Cjeagle]] 17:39, 8 December 2010 (EST)

10-1100/Navigation

2010-12-08T22:37:57Z

Cjeagle:

<noinclude>Back to [[10-1100]].<br/></noinclude>
{| border="1px" cellpadding="1" cellspacing="0" width="100%" style="font-size: small; align: left"
|- align=left
!#
!Week of...
!Notes and Links
|- align=left
|align=center|1
|Sep 13
|[[10-1100/About This Class|About This Class]], [[10-1100/Classnotes for Tuesday September 14|Tuesday]] - Non Commutative Gaussian Elimination, [[10-1100/Classnotes for Thursday September 16|Thursday]]
|- align=left
|align=center|2
|Sep 20
|[[10-1100/Classnotes for Tuesday September 21|Tuesday]] - Homomorphisms and Normal Groups, [[10-1100/Classnotes for Thursday September 23|Thursday]] - Isomorphism Theorems
|- align=left
|align=center|3
|Sep 27
|[[10-1100/Class Photo|Class Photo]], [[10-1100/Homework Assignment 1| HW1]], [http://katlas.math.toronto.edu/drorbn/images/4/4c/10-1100-hw1_solution.pdf HW1 solution]
|- align=left
|align=center|4
|Oct 4
|
|- align=left
|align=center|5
|Oct 11
|[[10-1100/Homework Assignment 2|HW2]], [http://katlas.math.toronto.edu/drorbn/images/6/6d/10-1100-hw2_solution.pdf HW2 solution]
|- align=left
|align=center|6
|Oct 18
|
|- align=left
|align=center|7
|Oct 25
|[[10-1100/Term Test|Term Test]]
|- align=left
|align=center|8
|Nov 1
|[[10-1100/Homework Assignment 3|HW3]], [http://katlas.math.toronto.edu/drorbn/images/0/0a/10-1100-hw3_solution.pdf HW3 solution]
|- align=left
|align=center|9
|Nov 8
|Monday-Tuesday is Fall Break, {{Pensieve Link|Classes/10-1100/1t2c4w.pdf|One Theorem, Two Corollaries, Four Weeks}}
|- align=left
|align=center|10
|Nov 15
|[[10-1100/Homework Assignment 4|HW4]], [http://katlas.math.toronto.edu/drorbn/images/4/47/10-1100-hw4_solution.pdf HW4 solution]
|- align=left
|align=center|11
|Nov 22
|
|- align=left
|align=center|12
|Nov 29
|[[10-1100/Homework Assignment 5|HW5]]
|- align=left
|align=center|13
|Dec 6
|{{Home Link|classes/1011/1100-AlgebraI/bdh.html|Boxing Day Handout}}, see also [[December 2010 Schedule]]. Some [[10-1100-Notes|Class Notes]]
|- align=left
|align=center|F
|Dec 13
|Final exam, Tuesday December 14 10-1, Bahen 6183
|- align=left
|colspan=3 align=center|[[10-1100/Register of Good Deeds|Register of Good Deeds]] / [[10-1100/To Do|To Do List]]
|- align=left
|colspan=3 align=center|[[Image:10-1100-ClassPhoto.jpg|310px]]<br/>[[10-1100/Class Photo|Add your name / see who's in!]]
|- align=left
|colspan=3 align=center|[[Image:10-1100-Splash.png|310px]]<br/>See {{Home Link|Talks/Mathcamp-0907/NCGE.html|Non Commutative Gaussian Elimination}}
|}

10-1100-Notes

2010-12-08T22:34:58Z

Cjeagle:

File:10-1100-AlgebraNotes.pdf

2010-12-08T22:28:58Z

Cjeagle:

10-1100-Assignment 1 Part 1 by cjeagle

2010-10-12T16:46:53Z

Cjeagle:

Here I present a solution to [http://en.wikipedia.org/wiki/Megaminx MegaMinx]. The puzzle is in the form of a regular dodecahedron, with each face capable of rotating. There are two versions to this puzzle. The first version, which I solve here, has a different colour on each face. The other version, which introduces parity issues, gives the same colour to opposite faces. I will only be considering the version with unique colours on each face. There are 132 tiles, which I have numbered from 0 to 131 to make coding easier. Here is a model, with numbering of the tiles (thanks to Amy Eagle for building this!):

[[Image:10-1100-cjeagleMinx1.JPG]] [[Image:10-1100-cjeagleMinx2.JPG]]

[[Image:10-1100-cjeagleMinx3.JPG]] [[Image:10-1100-cjeagleMinx4.JPG]]

Each face can be rotated clockwise or counterclockwise. Of course, we only need to consider one of these rotations, since the group generated will then contain the other as well. Here is a list of generating permutations which arises from rotating each face counterclockwise:

orange = [10 7 4 1 8 5 2 0 9 6 3 57 12 13 56 15 16 55 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 101 47 48 104 50 51 52 108 54 46 49 53 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 110 102 103 111 105 106 107 112 109 17 14 11 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 ]

grey = [0 1 2 112 4 5 115 7 8 9 119 17 14 11 18 15 12 21 19 16 13 20 55 23 24 58 26 27 61 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 10 56 57 6 59 60 3 62 63 64 65 22 67 68 25 70 71 28 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 72 113 114 69 116 117 118 66 120 121 122 123 124 125 126 127 128 129 130 131 ]

red = [0 1 2 3 4 5 6 7 8 9 10 11 12 66 14 15 67 17 18 19 68 21 28 25 22 29 26 23 32 30 27 24 31 61 34 35 62 37 38 65 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 20 16 63 64 13 77 78 79 69 70 71 72 73 74 75 76 39 36 33 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 ]

light blue = [0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 79 25 26 82 28 29 30 86 32 39 36 33 40 37 34 43 41 38 35 42 65 45 46 63 48 49 64 51 52 53 54 55 56 57 58 59 60 61 62 27 24 31 66 67 68 69 70 71 72 73 74 75 76 77 78 88 80 81 89 83 84 85 90 87 50 47 44 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 ]

light brown = [0 64 2 3 60 5 6 57 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 90 36 37 93 39 40 41 97 43 50 47 44 51 48 45 54 52 49 46 53 55 56 35 58 59 38 61 62 63 42 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 99 91 92 100 94 95 96 101 98 7 4 1 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 ]

purple = [0 11 12 13 4 5 6 7 8 9 10 22 23 24 14 15 16 17 18 19 20 21 33 34 35 25 26 27 28 29 30 31 32 44 45 46 36 37 38 39 40 41 42 43 1 2 3 47 48 49 50 51 52 53 54 61 58 55 62 59 56 65 63 60 57 64 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 ]

light green = [0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 118 119 120 22 23 24 25 26 27 21 19 30 31 20 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 72 69 66 73 70 67 76 74 71 68 75 28 78 79 29 81 82 32 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 124 127 121 77 122 123 80 125 126 83 128 129 130 131 ]

dark brown = [0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 71 68 75 33 34 35 36 37 38 32 30 41 42 31 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 121 69 70 122 72 73 74 123 76 83 80 77 84 81 78 87 85 82 79 86 39 89 90 40 92 93 43 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 94 91 88 124 125 126 127 128 129 130 131 ]

pink = [0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 85 86 87 44 45 46 47 48 49 43 41 52 53 42 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 126 123 130 94 91 88 95 92 89 98 96 93 90 97 50 100 101 51 103 104 54 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 105 124 125 102 127 128 129 99 131 ]

dark green = [53 1 2 3 4 5 6 54 52 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 96 97 98 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 129 130 131 105 102 99 106 103 100 109 107 104 101 108 7 111 112 8 114 115 0 117 118 119 120 121 122 123 124 125 126 127 128 113 116 110 ]

dark blue = [109 1 2 3 4 5 6 7 8 107 108 11 12 13 14 15 16 0 9 19 20 10 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 17 18 74 75 21 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 128 131 127 116 113 110 117 114 111 120 118 115 112 119 121 122 123 124 125 126 72 73 129 130 76 ]

magenta = [0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 117 120 116 77 78 79 80 81 82 76 74 85 86 75 88 89 90 91 92 93 83 84 96 97 87 99 100 101 102 103 104 94 95 107 108 98 110 111 112 113 114 115 105 106 118 119 109 127 124 121 128 125 122 131 129 126 123 130 ]

The group generated by these permutations has 100669616553523347122516032313645505168688116411019768627200000000000 elements, which is certainly higher than I can count. The complete C++ source code I used to find this number is at [[10-1100-cjeagleA1Code]] (and includes the input of the generating permutations). The output file is here: [[10-1100-cjeagleA1Output]].

10-1100-Assignment 1 Part 1 by cjeagle

2010-10-12T16:21:19Z

Cjeagle:

Here I present a solution to [http://en.wikipedia.org/wiki/Megaminx MegaMinx]. The puzzle is in the form of a regular dodecahedron, with each face capable of rotating. There are two versions to this puzzle. The first version, which I solve here, has a different colour on each face. The other version, which introduces parity issues, gives the same colour to opposite faces. I will only be considering the version with unique colours on each face. There are 132 tiles, which I have numbered from 0 to 131 to make coding easier. Here is a model, with numbering of the tiles (thanks to Amy Eagle for building this!):

[[Image:10-1100-cjeagleMinx1.JPG]] [[Image:10-1100-cjeagleMinx1.JPG]]

[[Image:10-1100-cjeagleMinx1.JPG]] [[Image:10-1100-cjeagleMinx1.JPG]]

Each face can be rotated clockwise or counterclockwise. Of course, we only need to consider one of these rotations, since the group generated will then contain the other as well. Here is a list of generating permutations which arises from rotating each face counterclockwise:

orange = [10 7 4 1 8 5 2 0 9 6 3 57 12 13 56 15 16 55 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 101 47 48 104 50 51 52 108 54 46 49 53 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 110 102 103 111 105 106 107 112 109 17 14 11 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 ]

grey = [0 1 2 112 4 5 115 7 8 9 119 17 14 11 18 15 12 21 19 16 13 20 55 23 24 58 26 27 61 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 10 56 57 6 59 60 3 62 63 64 65 22 67 68 25 70 71 28 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 72 113 114 69 116 117 118 66 120 121 122 123 124 125 126 127 128 129 130 131 ]

red = [0 1 2 3 4 5 6 7 8 9 10 11 12 66 14 15 67 17 18 19 68 21 28 25 22 29 26 23 32 30 27 24 31 61 34 35 62 37 38 65 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 20 16 63 64 13 77 78 79 69 70 71 72 73 74 75 76 39 36 33 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 ]

light blue = [0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 79 25 26 82 28 29 30 86 32 39 36 33 40 37 34 43 41 38 35 42 65 45 46 63 48 49 64 51 52 53 54 55 56 57 58 59 60 61 62 27 24 31 66 67 68 69 70 71 72 73 74 75 76 77 78 88 80 81 89 83 84 85 90 87 50 47 44 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 ]

light brown = [0 64 2 3 60 5 6 57 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 90 36 37 93 39 40 41 97 43 50 47 44 51 48 45 54 52 49 46 53 55 56 35 58 59 38 61 62 63 42 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 99 91 92 100 94 95 96 101 98 7 4 1 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 ]

purple = [0 11 12 13 4 5 6 7 8 9 10 22 23 24 14 15 16 17 18 19 20 21 33 34 35 25 26 27 28 29 30 31 32 44 45 46 36 37 38 39 40 41 42 43 1 2 3 47 48 49 50 51 52 53 54 61 58 55 62 59 56 65 63 60 57 64 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 ]

light green = [0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 118 119 120 22 23 24 25 26 27 21 19 30 31 20 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 72 69 66 73 70 67 76 74 71 68 75 28 78 79 29 81 82 32 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 124 127 121 77 122 123 80 125 126 83 128 129 130 131 ]

dark brown = [0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 71 68 75 33 34 35 36 37 38 32 30 41 42 31 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 121 69 70 122 72 73 74 123 76 83 80 77 84 81 78 87 85 82 79 86 39 89 90 40 92 93 43 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 94 91 88 124 125 126 127 128 129 130 131 ]

pink = [0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 85 86 87 44 45 46 47 48 49 43 41 52 53 42 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 126 123 130 94 91 88 95 92 89 98 96 93 90 97 50 100 101 51 103 104 54 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 105 124 125 102 127 128 129 99 131 ]

dark green = [53 1 2 3 4 5 6 54 52 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 96 97 98 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 129 130 131 105 102 99 106 103 100 109 107 104 101 108 7 111 112 8 114 115 0 117 118 119 120 121 122 123 124 125 126 127 128 113 116 110 ]

dark blue = [109 1 2 3 4 5 6 7 8 107 108 11 12 13 14 15 16 0 9 19 20 10 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 17 18 74 75 21 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 128 131 127 116 113 110 117 114 111 120 118 115 112 119 121 122 123 124 125 126 72 73 129 130 76 ]

magenta = [0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 117 120 116 77 78 79 80 81 82 76 74 85 86 75 88 89 90 91 92 93 83 84 96 97 87 99 100 101 102 103 104 94 95 107 108 98 110 111 112 113 114 115 105 106 118 119 109 127 124 121 128 125 122 131 129 126 123 130 ]

The group generated by these permutations has 100669616553523347122516032313645505168688116411019768627200000000000 elements, which is certainly higher than I can count. The complete C++ source code I used to find this number is at [[10-1100-cjeagleA1Code]] (and includes the input of the generating permutations). The output file is here: [[10-1100-cjeagleA1Output]].

10-1100-cjeagleA1Code

2010-10-12T16:20:17Z

Cjeagle:

This is the C++ source code I used to solve the MegaMinx. Aside from ([http://mattmccutchen.net/bigint/ BigInteger by Matt McCutcheon]), which is a class in the public domain, it uses only standard C++. The algorithm is not terribly efficient (took about 6 hours to run), but it got the job done.

----

<pre>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <vector>
#include "BigIntegerLibrary.hh"

using namespace std;

//sloppy code, but it made it easier to write
const int N = 132;
const int numGens = 12;

typedef vector<int> perm;

perm table[N][N];
perm ID;
perm blank;

/*to make it easier to input generating permutations
this algorithm takes in a list of an even number of numbers
and produces the permutation which sends a(i) to a(i+1) for each even i*/
perm permGen(vector<int> a){
perm result(N);

for(int i=0;i<N; i++){
result[i] = i;
}
for(int i=0;i<a.size()-1;i+=2){
result[a[i]]=a[i+1];
}
return result;
}

//an error-checking routine, making sure every element of the table is
//a valid permutation
bool isPerm(perm a){
int checkr[N];
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(a[j] == i){checkr[i] = i;}
}
}

for(int i=0; i<N;i++){
if(checkr[i] != i){return false;}
}
return true;
}

//tests if two tables of permutations are the same
bool tableEqual(perm a[N][N], perm b[N][N]){
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
if(a[i][j] != b[i][j]){return false;}
}
}
return true;
}

//Write one permutation to standard output
//Used for testing and error-checking
void permOutput(perm a){
cout << "[";
for(int i=0; i<N; i++){
cout << a[i] << " ";
}
cout << "]";
}

//write the entire table to standard output
//this was useful in testing on small groups, but would not be suitable for
//groups as large as the MegaMinx
void tableOutput(){
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
permOutput(table[i][j]);
cout << " ";
}
cout << endl;
}
}

//find the pivot position of a permutation
int pivotPosition(perm s){
for(int i=0; i<N; i++){
if(s[i] != i) return i;
}
return -1;
}

//given permutations a and b, produce ab
perm mult(perm a, perm b){
perm result(N);
for(int i=0; i<N; i++){
result[i] = a[b[i]];
}

return result;
}

//given a permutation a, produce a^{-1}
perm invert(perm a){
perm result(N);
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(a[j] == i){result[i] = j;}
}
}
return result;
}

//the Feed algorithm from class
void Feed(perm s) {
if(s == ID){return;}

int pivot = pivotPosition(s);
int value = s[pivot];
if(table[pivot][value] == blank){
table[pivot][value] = s;
return;
}

Feed(mult(invert(table[pivot][value]), s));
}

//compute the product of the sizes of the columns in the table
BigInteger groupOrder(){
BigInteger result = 1;
BigInteger colSize[N];
for(int i=0; i<N; i++){
colSize[i] = 0;
for(int j=0;j<N;j++){
if(table[i][j] != blank){colSize[i] = colSize[i]+1;}
}
}

for(int i=0; i<N; i++){
result = result * colSize[i];
}

return result;
}

int main(int argc, char *argv[])
{
ofstream outputFile;
outputFile.open("megaminx.txt");

outputFile << "MegaMinx" << endl << endl;
//start by initializing the two constant permutations - blank and identity.
//we make blank and invalid permutation for easier error-checking
for(int i=0; i<N; i++){
ID.push_back(i);
blank.push_back(-1);
}

perm generators[numGens];

/*Generators come from rotating the marked face counterclockwise*/
int gens[numGens][50] = {
{3,1,10,3,0,10,7,0,1,7,6,2,9,6,8,9,4,8,2,4,17,55,14,56,11,57,55,46,56,49,57,53,46,101,49,104,53,108,101,110,104,111,108,112,110,17,111,14,112,11}, /*orange*/
{20,13,21,20,17,21,11,17,13,11,19,16,18,19,14,18,12,14,16,12,112,72,115,69,119,66,72,28,69,25,66,22,28,61,25,58,22,55,61,3,58,6,55,10,3,112,6,115,10,119}, /*grey*/
{31,24,32,31,28,32,22,28,24,22,27,23,30,27,29,30,25,29,23,25,66,77,67,78,68,79,77,39,78,36,79,33,39,65,36,62,33,61,65,13,62,16,61,20,13,66,16,67,20,68}, /*red*/
{35,33,42,35,43,42,39,43,33,39,38,34,41,38,40,41,36,40,34,36,79,88,82,89,86,90,88,50,89,47,90,44,50,64,47,63,44,65,64,24,63,27,65,31,24,79,27,82,31,86}, /*light blue*/
{46,44,53,46,54,53,50,54,44,50,49,45,52,49,51,52,47,51,45,47,90,99,93,100,97,101,99,7,100,4,101,1,7,57,4,60,1,64,57,35,60,38,64,42,35,90,38,93,42,97}, /*light brown*/
{57,55,64,57,65,64,61,65,55,61,60,56,63,60,62,63,58,62,56,58,22,33,23,34,24,35,33,44,34,45,35,46,44,1,45,2,46,3,1,11,2,12,3,13,11,22,12,23,13,24}, /*purple*/
{68,66,75,68,76,75,72,76,66,72,71,67,74,71,73,74,69,73,67,69,119,127,118,124,120,121,127,83,124,80,121,77,83,32,80,29,77,28,32,20,29,19,28,21,20,119,19,118,21,120}, /*light green*/
{86,79,87,86,83,87,77,83,79,77,82,78,85,82,84,85,80,84,78,80,121,94,122,91,123,88,94,43,91,40,88,39,43,31,40,30,39,32,31,68,30,71,32,75,68,121,71,122,75,123}, /*dark brown*/
{97,90,98,97,94,98,88,94,90,88,93,89,96,93,95,96,91,95,89,91,123,105,126,102,130,99,105,54,102,51,99,50,54,42,51,41,50,43,42,86,41,85,43,87,86,123,85,126,87,130}, /*pink*/
{108,101,109,108,105,109,99,105,101,99,104,100,107,104,106,107,102,106,100,102,130,116,129,113,131,110,116,0,113,8,110,7,0,53,8,52,7,54,53,97,52,96,54,98,97,130,96,129,98,131}, /*dark green*/
{119,112,120,119,116,120,110,116,112,110,115,111,118,115,117,118,113,117,111,113,131,76,128,73,127,72,76,21,73,18,72,17,21,10,18,9,17,0,10,108,9,107,0,109,108,131,107,128,109,127}, /*dark blue*/
{123,121,130,123,131,130,127,131,121,127,122,124,126,122,129,126,128,129,124,128,120,109,117,106,116,105,109,98,106,95,105,94,98,87,95,84,94,83,87,75,84,74,83,76,75,120,74,117,76,116} /*magenta*/
};

//construct the actual generators from the above list
for(int i=0;i<numGens; i++){
generators[i] = permGen(vector<int>(gens[i], gens[i]+50));
}

//prepare a blank table
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
table[i][j] = blank;
}
}

//set the diagonal of the table to be the identity permutation
for(int i=0; i<N; i++){
table[i][i] = ID;
}

//write out the complete list of generators
outputFile << "The generating permutations are: " << endl;
for(int i=0;i<numGens;i++){
outputFile << "[";
for(int j=0; j<N; j++){
outputFile << generators[i][j] << " ";
}
outputFile << "]" << endl;
}

//Feed the generators into the table
for(int i=0; i<numGens; i++){
Feed(generators[i]);
}

perm tableCopy[N][N];

do{
//put a copy of table in tableCopy, so we can check if anything changed
for(int i=0; i<N; i++){
for(int j=0;j<N;j++){
tableCopy[i][j] = perm(table[i][j]);
}
}

//check each pair of indices. Every time we find (i,j) and (k,l) such that
//table[i][j] and table[k][l] have entries, we feed the product of those entries
for(int i=0;i<N;i++){
for(int j=0; j<N; j++){
if(table[i][j] != blank){
for(int k=0;k<N;k++){
for(int l=0;l<N;l++){
if(table[k][l] != blank){
Feed(mult(table[i][j], table[k][l]));
}
}
}
}
}
}
//keep on going until nothing changes
}while(!tableEqual(tableCopy, table));

//now the size of G is the product of the sizes of the columns.
BigInteger orderOfGroup = groupOrder();
outputFile << endl << endl << "The order of the subgroup of S_132 generated by the above is: " << orderOfGroup;
outputFile.close();
return 0;
}
</pre>

10-1100-cjeagleA1Output

2010-10-12T16:18:58Z

Cjeagle:

This is a copy of the output produced by the program [[10-1100-cjeagleA1Code]].

----

<pre>
MegaMinx

The generating permutations are:
[10 7 4 1 8 5 2 0 9 6 3 57 12 13 56 15 16 55 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
101 47 48 104 50 51 52 108 54 46 49 53 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
88 89 90 91 92 93 94 95 96 97 98 99 100 110 102 103 111 105 106 107 112 109 17 14 11 113 114 115 116 117 118 119 120 121 122 123
124 125 126 127 128 129 130 131 ]

[0 1 2 112 4 5 115 7 8 9 119 17 14 11 18 15 12 21 19 16 13 20 55 23 24 58 26 27 61 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
45 46 47 48 49 50 51 52 53 54 10 56 57 6 59 60 3 62 63 64 65 22 67 68 25 70 71 28 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88
89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 72 113 114 69 116 117 118 66 120 121 122 123 124
125 126 127 128 129 130 131 ]

[0 1 2 3 4 5 6 7 8 9 10 11 12 66 14 15 67 17 18 19 68 21 28 25 22 29 26 23 32 30 27 24 31 61 34 35 62 37 38 65 40 41 42 43 44 45 46
47 48 49 50 51 52 53 54 55 56 57 58 59 60 20 16 63 64 13 77 78 79 69 70 71 72 73 74 75 76 39 36 33 80 81 82 83 84 85 86 87 88 89
90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124
125 126 127 128 129 130 131 ]

[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 79 25 26 82 28 29 30 86 32 39 36 33 40 37 34 43 41 38 35 42 65 45 46
63 48 49 64 51 52 53 54 55 56 57 58 59 60 61 62 27 24 31 66 67 68 69 70 71 72 73 74 75 76 77 78 88 80 81 89 83 84 85 90 87 50 47 44
91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125
126 127 128 129 130 131 ]

[0 64 2 3 60 5 6 57 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 90 36 37 93 39 40 41 97 43 50 47
44 51 48 45 54 52 49 46 53 55 56 35 58 59 38 61 62 63 42 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
99 91 92 100 94 95 96 101 98 7 4 1 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125
126 127 128 129 130 131 ]

[0 11 12 13 4 5 6 7 8 9 10 22 23 24 14 15 16 17 18 19 20 21 33 34 35 25 26 27 28 29 30 31 32 44 45 46 36 37 38 39 40 41 42 43 1 2 3
47 48 49 50 51 52 53 54 61 58 55 62 59 56 65 63 60 57 64 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125
126 127 128 129 130 131 ]

[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 118 119 120 22 23 24 25 26 27 21 19 30 31 20 33 34 35 36 37 38 39 40 41 42 43 44 45
46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 72 69 66 73 70 67 76 74 71 68 75 28 78 79 29 81 82 32 84 85 86 87 88
89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 124 127 121 77 122 123 80
125 126 83 128 129 130 131 ]

[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 71 68 75 33 34 35 36 37 38 32 30 41 42 31 44 45 46
47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 121 69 70 122 72 73 74 123 76 83 80 77 84 81 78 87 85 82 79 86 39 89
90 40 92 93 43 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 94 91 88 124 125
126 127 128 129 130 131 ]

[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 85 86 87 44 45 46
47 48 49 43 41 52 53 42 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 126 123 130 94
91 88 95 92 89 98 96 93 90 97 50 100 101 51 103 104 54 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 105 124
125 102 127 128 129 99 131 ]

[53 1 2 3 4 5 6 54 52 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
46 47 48 49 50 51 96 97 98 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
90 91 92 93 94 95 129 130 131 105 102 99 106 103 100 109 107 104 101 108 7 111 112 8 114 115 0 117 118 119 120 121 122 123 124 125
126 127 128 113 116 110 ]

[109 1 2 3 4 5 6 7 8 107 108 11 12 13 14 15 16 0 9 19 20 10 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 17 18 74 75 21 77 78 79 80 81 82 83 84 85 86 87 88
89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 128 131 127 116 113 110 117 114 111 120 118 115 112 119 121 122 123
124 125 126 72 73 129 130 76 ]

[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 117 120 116 77 78 79 80 81 82 76 74 85 86 75 88 89
90 91 92 93 83 84 96 97 87 99 100 101 102 103 104 94 95 107 108 98 110 111 112 113 114 115 105 106 118 119 109 127 124 121 128 125
122 131 129 126 123 130 ]

The order of the subgroup of S_132 generated by the above is: 100669616553523347122516032313645505168688116411019768627200000000000
</pre>

10-1100-cjeagleA1Output

2010-10-12T16:18:34Z

Cjeagle:

This is a copy of the output produced by the program [[10-1100-cjeagleA1Code]].

----

<pre>
MegaMinx

The generating permutations are:
[10 7 4 1 8 5 2 0 9 6 3 57 12 13 56 15 16 55 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
101 47 48 104 50 51 52 108 54 46 49 53 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
88 89 90 91 92 93 94 95 96 97 98 99 100 110 102 103 111 105 106 107 112 109 17 14 11 113 114 115 116 117 118 119 120 121 122 123
124 125 126 127 128 129 130 131 ]

[0 1 2 112 4 5 115 7 8 9 119 17 14 11 18 15 12 21 19 16 13 20 55 23 24 58 26 27 61 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
45 46 47 48 49 50 51 52 53 54 10 56 57 6 59 60 3 62 63 64 65 22 67 68 25 70 71 28 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88
89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 72 113 114 69 116 117 118 66 120 121 122 123 124
125 126 127 128 129 130 131 ]

[0 1 2 3 4 5 6 7 8 9 10 11 12 66 14 15 67 17 18 19 68 21 28 25 22 29 26 23 32 30 27 24 31 61 34 35 62 37 38 65 40 41 42 43 44 45 46
47 48 49 50 51 52 53 54 55 56 57 58 59 60 20 16 63 64 13 77 78 79 69 70 71 72 73 74 75 76 39 36 33 80 81 82 83 84 85 86 87 88 89
90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124
125 126 127 128 129 130 131 ]

[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 79 25 26 82 28 29 30 86 32 39 36 33 40 37 34 43 41 38 35 42 65 45 46
63 48 49 64 51 52 53 54 55 56 57 58 59 60 61 62 27 24 31 66 67 68 69 70 71 72 73 74 75 76 77 78 88 80 81 89 83 84 85 90 87 50 47 44
91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125
126 127 128 129 130 131 ]

[0 64 2 3 60 5 6 57 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 90 36 37 93 39 40 41 97 43 50 47
44 51 48 45 54 52 49 46 53 55 56 35 58 59 38 61 62 63 42 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
99 91 92 100 94 95 96 101 98 7 4 1 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125
126 127 128 129 130 131 ]

[0 11 12 13 4 5 6 7 8 9 10 22 23 24 14 15 16 17 18 19 20 21 33 34 35 25 26 27 28 29 30 31 32 44 45 46 36 37 38 39 40 41 42 43 1 2 3
47 48 49 50 51 52 53 54 61 58 55 62 59 56 65 63 60 57 64 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125
126 127 128 129 130 131 ]

[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 118 119 120 22 23 24 25 26 27 21 19 30 31 20 33 34 35 36 37 38 39 40 41 42 43 44 45
46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 72 69 66 73 70 67 76 74 71 68 75 28 78 79 29 81 82 32 84 85 86 87 88
89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 124 127 121 77 122 123 80
125 126 83 128 129 130 131 ]

[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 71 68 75 33 34 35 36 37 38 32 30 41 42 31 44 45 46
47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 121 69 70 122 72 73 74 123 76 83 80 77 84 81 78 87 85 82 79 86 39 89
90 40 92 93 43 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 94 91 88 124 125
126 127 128 129 130 131 ]

[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 85 86 87 44 45 46
47 48 49 43 41 52 53 42 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 126 123 130 94
91 88 95 92 89 98 96 93 90 97 50 100 101 51 103 104 54 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 105 124
125 102 127 128 129 99 131 ]

[53 1 2 3 4 5 6 54 52 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 96 97 98 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 129 130 131 105 102 99 106 103 100 109 107 104 101 108 7 111 112 8 114 115 0 117 118 119 120 121 122 123 124 125 126 127 128 113 116 110 ]

[109 1 2 3 4 5 6 7 8 107 108 11 12 13 14 15 16 0 9 19 20 10 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 17 18 74 75 21 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 128 131 127 116 113 110 117 114 111 120 118 115 112 119 121 122 123 124 125 126 72 73 129 130 76 ]

[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 117 120 116 77 78 79 80 81 82 76 74 85 86 75 88 89 90 91 92 93 83 84 96 97 87 99 100 101 102 103 104 94 95 107 108 98 110 111 112 113 114 115 105 106 118 119 109 127 124 121 128 125 122 131 129 126 123 130 ]

The order of the subgroup of S_132 generated by the above is: 100669616553523347122516032313645505168688116411019768627200000000000
</pre>

10-1100-cjeagleA1Output

2010-10-12T16:17:24Z

Cjeagle:

This is a copy of the output produced by the program [[10-1100-cjeagleA1Code]].

----

<pre>
MegaMinx

The generating permutations are:
[10 7 4 1 8 5 2 0 9 6 3 57 12 13 56 15 16 55 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 101 47 48 104 50 51 52 108 54 46 49 53 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 110 102 103 111 105 106 107 112 109 17 14 11 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 ]

[0 1 2 112 4 5 115 7 8 9 119 17 14 11 18 15 12 21 19 16 13 20 55 23 24 58 26 27 61 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 10 56 57 6 59 60 3 62 63 64 65 22 67 68 25 70 71 28 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 72 113 114 69 116 117 118 66 120 121 122 123 124 125 126 127 128 129 130 131 ]

[0 1 2 3 4 5 6 7 8 9 10 11 12 66 14 15 67 17 18 19 68 21 28 25 22 29 26 23 32 30 27 24 31 61 34 35 62 37 38 65 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 20 16 63 64 13 77 78 79 69 70 71 72 73 74 75 76 39 36 33 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 ]

[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 79 25 26 82 28 29 30 86 32 39 36 33 40 37 34 43 41 38 35 42 65 45 46 63 48 49 64 51 52 53 54 55 56 57 58 59 60 61 62 27 24 31 66 67 68 69 70 71 72 73 74 75 76 77 78 88 80 81 89 83 84 85 90 87 50 47 44 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 ]

[0 64 2 3 60 5 6 57 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 90 36 37 93 39 40 41 97 43 50 47 44 51 48 45 54 52 49 46 53 55 56 35 58 59 38 61 62 63 42 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 99 91 92 100 94 95 96 101 98 7 4 1 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 ]

[0 11 12 13 4 5 6 7 8 9 10 22 23 24 14 15 16 17 18 19 20 21 33 34 35 25 26 27 28 29 30 31 32 44 45 46 36 37 38 39 40 41 42 43 1 2 3 47 48 49 50 51 52 53 54 61 58 55 62 59 56 65 63 60 57 64 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 ]

[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 118 119 120 22 23 24 25 26 27 21 19 30 31 20 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 72 69 66 73 70 67 76 74 71 68 75 28 78 79 29 81 82 32 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 124 127 121 77 122 123 80 125 126 83 128 129 130 131 ]

[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 71 68 75 33 34 35 36 37 38 32 30 41 42 31 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 121 69 70 122 72 73 74 123 76 83 80 77 84 81 78 87 85 82 79 86 39 89 90 40 92 93 43 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 94 91 88 124 125 126 127 128 129 130 131 ]

[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 85 86 87 44 45 46 47 48 49 43 41 52 53 42 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 126 123 130 94 91 88 95 92 89 98 96 93 90 97 50 100 101 51 103 104 54 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 105 124 125 102 127 128 129 99 131 ]

[53 1 2 3 4 5 6 54 52 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 96 97 98 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 129 130 131 105 102 99 106 103 100 109 107 104 101 108 7 111 112 8 114 115 0 117 118 119 120 121 122 123 124 125 126 127 128 113 116 110 ]

[109 1 2 3 4 5 6 7 8 107 108 11 12 13 14 15 16 0 9 19 20 10 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 17 18 74 75 21 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 128 131 127 116 113 110 117 114 111 120 118 115 112 119 121 122 123 124 125 126 72 73 129 130 76 ]

[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 117 120 116 77 78 79 80 81 82 76 74 85 86 75 88 89 90 91 92 93 83 84 96 97 87 99 100 101 102 103 104 94 95 107 108 98 110 111 112 113 114 115 105 106 118 119 109 127 124 121 128 125 122 131 129 126 123 130 ]

The order of the subgroup of S_132 generated by the above is: 100669616553523347122516032313645505168688116411019768627200000000000
</pre>

10-1100-cjeagleA1Code

2010-10-12T16:15:41Z

Cjeagle:

This is the C++ source code I used to solve the MegaMinx. Aside from BigInteger, which is a class in the public domain, it uses only standard C++. The algorithm is not terribly efficient (took about 6 hours to run), but it got the job done.

----

<pre>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <vector>
#include "BigIntegerLibrary.hh"

using namespace std;

//sloppy code, but it made it easier to write
const int N = 132;
const int numGens = 12;

typedef vector<int> perm;

perm table[N][N];
perm ID;
perm blank;

/*to make it easier to input generating permutations
this algorithm takes in a list of an even number of numbers
and produces the permutation which sends a(i) to a(i+1) for each even i*/
perm permGen(vector<int> a){
perm result(N);

for(int i=0;i<N; i++){
result[i] = i;
}
for(int i=0;i<a.size()-1;i+=2){
result[a[i]]=a[i+1];
}
return result;
}

//an error-checking routine, making sure every element of the table is
//a valid permutation
bool isPerm(perm a){
int checkr[N];
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(a[j] == i){checkr[i] = i;}
}
}

for(int i=0; i<N;i++){
if(checkr[i] != i){return false;}
}
return true;
}

//tests if two tables of permutations are the same
bool tableEqual(perm a[N][N], perm b[N][N]){
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
if(a[i][j] != b[i][j]){return false;}
}
}
return true;
}

//Write one permutation to standard output
//Used for testing and error-checking
void permOutput(perm a){
cout << "[";
for(int i=0; i<N; i++){
cout << a[i] << " ";
}
cout << "]";
}

//write the entire table to standard output
//this was useful in testing on small groups, but would not be suitable for
//groups as large as the MegaMinx
void tableOutput(){
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
permOutput(table[i][j]);
cout << " ";
}
cout << endl;
}
}

//find the pivot position of a permutation
int pivotPosition(perm s){
for(int i=0; i<N; i++){
if(s[i] != i) return i;
}
return -1;
}

//given permutations a and b, produce ab
perm mult(perm a, perm b){
perm result(N);
for(int i=0; i<N; i++){
result[i] = a[b[i]];
}

return result;
}

//given a permutation a, produce a^{-1}
perm invert(perm a){
perm result(N);
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(a[j] == i){result[i] = j;}
}
}
return result;
}

//the Feed algorithm from class
void Feed(perm s) {
if(s == ID){return;}

int pivot = pivotPosition(s);
int value = s[pivot];
if(table[pivot][value] == blank){
table[pivot][value] = s;
return;
}

Feed(mult(invert(table[pivot][value]), s));
}

//compute the product of the sizes of the columns in the table
BigInteger groupOrder(){
BigInteger result = 1;
BigInteger colSize[N];
for(int i=0; i<N; i++){
colSize[i] = 0;
for(int j=0;j<N;j++){
if(table[i][j] != blank){colSize[i] = colSize[i]+1;}
}
}

for(int i=0; i<N; i++){
result = result * colSize[i];
}

return result;
}

int main(int argc, char *argv[])
{
ofstream outputFile;
outputFile.open("megaminx.txt");

outputFile << "MegaMinx" << endl << endl;
//start by initializing the two constant permutations - blank and identity.
//we make blank and invalid permutation for easier error-checking
for(int i=0; i<N; i++){
ID.push_back(i);
blank.push_back(-1);
}

perm generators[numGens];

/*Generators come from rotating the marked face counterclockwise*/
int gens[numGens][50] = {
{3,1,10,3,0,10,7,0,1,7,6,2,9,6,8,9,4,8,2,4,17,55,14,56,11,57,55,46,56,49,57,53,46,101,49,104,53,108,101,110,104,111,108,112,110,17,111,14,112,11}, /*orange*/
{20,13,21,20,17,21,11,17,13,11,19,16,18,19,14,18,12,14,16,12,112,72,115,69,119,66,72,28,69,25,66,22,28,61,25,58,22,55,61,3,58,6,55,10,3,112,6,115,10,119}, /*grey*/
{31,24,32,31,28,32,22,28,24,22,27,23,30,27,29,30,25,29,23,25,66,77,67,78,68,79,77,39,78,36,79,33,39,65,36,62,33,61,65,13,62,16,61,20,13,66,16,67,20,68}, /*red*/
{35,33,42,35,43,42,39,43,33,39,38,34,41,38,40,41,36,40,34,36,79,88,82,89,86,90,88,50,89,47,90,44,50,64,47,63,44,65,64,24,63,27,65,31,24,79,27,82,31,86}, /*light blue*/
{46,44,53,46,54,53,50,54,44,50,49,45,52,49,51,52,47,51,45,47,90,99,93,100,97,101,99,7,100,4,101,1,7,57,4,60,1,64,57,35,60,38,64,42,35,90,38,93,42,97}, /*light brown*/
{57,55,64,57,65,64,61,65,55,61,60,56,63,60,62,63,58,62,56,58,22,33,23,34,24,35,33,44,34,45,35,46,44,1,45,2,46,3,1,11,2,12,3,13,11,22,12,23,13,24}, /*purple*/
{68,66,75,68,76,75,72,76,66,72,71,67,74,71,73,74,69,73,67,69,119,127,118,124,120,121,127,83,124,80,121,77,83,32,80,29,77,28,32,20,29,19,28,21,20,119,19,118,21,120}, /*light green*/
{86,79,87,86,83,87,77,83,79,77,82,78,85,82,84,85,80,84,78,80,121,94,122,91,123,88,94,43,91,40,88,39,43,31,40,30,39,32,31,68,30,71,32,75,68,121,71,122,75,123}, /*dark brown*/
{97,90,98,97,94,98,88,94,90,88,93,89,96,93,95,96,91,95,89,91,123,105,126,102,130,99,105,54,102,51,99,50,54,42,51,41,50,43,42,86,41,85,43,87,86,123,85,126,87,130}, /*pink*/
{108,101,109,108,105,109,99,105,101,99,104,100,107,104,106,107,102,106,100,102,130,116,129,113,131,110,116,0,113,8,110,7,0,53,8,52,7,54,53,97,52,96,54,98,97,130,96,129,98,131}, /*dark green*/
{119,112,120,119,116,120,110,116,112,110,115,111,118,115,117,118,113,117,111,113,131,76,128,73,127,72,76,21,73,18,72,17,21,10,18,9,17,0,10,108,9,107,0,109,108,131,107,128,109,127}, /*dark blue*/
{123,121,130,123,131,130,127,131,121,127,122,124,126,122,129,126,128,129,124,128,120,109,117,106,116,105,109,98,106,95,105,94,98,87,95,84,94,83,87,75,84,74,83,76,75,120,74,117,76,116} /*magenta*/
};

//construct the actual generators from the above list
for(int i=0;i<numGens; i++){
generators[i] = permGen(vector<int>(gens[i], gens[i]+50));
}

//prepare a blank table
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
table[i][j] = blank;
}
}

//set the diagonal of the table to be the identity permutation
for(int i=0; i<N; i++){
table[i][i] = ID;
}

//write out the complete list of generators
outputFile << "The generating permutations are: " << endl;
for(int i=0;i<numGens;i++){
outputFile << "[";
for(int j=0; j<N; j++){
outputFile << generators[i][j] << " ";
}
outputFile << "]" << endl;
}

//Feed the generators into the table
for(int i=0; i<numGens; i++){
Feed(generators[i]);
}

perm tableCopy[N][N];

do{
//put a copy of table in tableCopy, so we can check if anything changed
for(int i=0; i<N; i++){
for(int j=0;j<N;j++){
tableCopy[i][j] = perm(table[i][j]);
}
}

//check each pair of indices. Every time we find (i,j) and (k,l) such that
//table[i][j] and table[k][l] have entries, we feed the product of those entries
for(int i=0;i<N;i++){
for(int j=0; j<N; j++){
if(table[i][j] != blank){
for(int k=0;k<N;k++){
for(int l=0;l<N;l++){
if(table[k][l] != blank){
Feed(mult(table[i][j], table[k][l]));
}
}
}
}
}
}
//keep on going until nothing changes
}while(!tableEqual(tableCopy, table));

//now the size of G is the product of the sizes of the columns.
BigInteger orderOfGroup = groupOrder();
outputFile << endl << endl << "The order of the subgroup of S_132 generated by the above is: " << orderOfGroup;
outputFile.close();
return 0;
}
</pre>

File:10-1100-cjeagleMinx4.JPG

2010-10-12T16:13:53Z

Cjeagle:

File:10-1100-cjeagleMinx3.JPG

2010-10-12T16:13:40Z

Cjeagle:

File:10-1100-cjeagleMinx2.JPG

2010-10-12T16:13:27Z

Cjeagle:

File:10-1100-cjeagleMinx1.JPG

2010-10-12T16:13:13Z

Cjeagle:

10-1100/Class Photo

2010-09-29T13:20:27Z

Cjeagle: /* Who We Are... */

Our class on September 28, 2010:

[[Image:10-1100-ClassPhoto.jpg|thumb|centre|800px|Class Photo: click to enlarge]]
{{10-1100/Navigation}}

Please identify yourself in this photo! There are two ways to do that:

* [[Special:Userlogin|Log in]] to this Wiki and edit this page. Put your name, userid, email address and location in the picture in the alphabetical list below.
* Send [[User:Drorbn|Dror]] an email message with this information.

The first option is more fun but less private.

===Who We Are...===

{| align=center border=1 cellspacing=0
|-
!First name
!Last name
!UserID
!Email
!In the photo
!Comments
{{Photo Entry|last=Bar-Natan|first=Dror|userid=Drorbn|email=drorbn@ math.toronto.edu|location=facing everybody, as the photographer|comments=Take this entry as a model and leave it first. Otherwise alphabetize by last name. Feel free to leave some fields blank. For better line-breaking, leave a space next to the "@" in email addresses.}}
{{Photo Entry|last=Dema|first=Ilir|userid=idema|email=ilir.dema@ utoronto.ca|location=The only one with gray hair|comments=First name is ILIR - just want to avoid confusion by similar-looking capital I and lower case l}}
{{Photo Entry|last=Eagle|first=Chris|userid=cjeagle|email=cjeagle@ math.utoronto.ca|location=Towards the right, in the back row. You can see only the top of my head, as I'm directly behind someone.|comments=}}
{{Photo Entry|last=MeneZes|first=Allan|userid=Amenezes007|email=amenezes007@ sympatico.ca|location=The only brown dude in the middle of the photo|comments=Knowledge is Power, Ignorance is Dangerous, War is Peace}}

|}