#John Kim #Use whatever you like #read "C:/Users/John Y. Kim/Documents/Maple/hw24.txt": PSP:=proc() local a,b,c,d,n: a:=3: b:=0: c:=2: #n:=2: #want n|c and n composite for n from 2 to 1000000 do #while c mod n != 0 or IsPrime(n) do if c mod n = 0 and not IsPrime(n) then print(n): fi: d:=a+b: a:=b: b:=c: c:=d: #n:=n+1: od: n: end: IsPrime:=proc(n) local d: for d from 2 to n^0.5 do if n mod d = 0 then RETURN(false): fi: od: RETURN(true): end: Primes:=proc(n) local P,d,i,comp: P:={2,3,5,7,11,13,17,19}: for i from 23 to n do comp:=false: for d from 1 while P[d]^2<=i do if i mod P[d] = 0 then comp:=true: break: fi: od: if not comp then P:=P union {i}: fi: od: P: end: #PSP(); # 271441 # 904631 #P(n): the nth term of the Perrin sequence #using matrix methods P:=proc(n) local M,v,b: M:=Matrix(3,3,[0,1,0,0,0,1,1,1,0]): v:=Matrix(3,1,[3,0,2]): b:=evalm(M^n &* v): b[1,1]: end: #P(2^20); #4907486623903722805297725232245265827055249791214434138116795812\ # 716167879116566939532285784203887477[...127856 digits...]28213\ # 51663672505468646787355488245123653236152134178820592060343691\ # 155925212651423598055857578598490 #PseudoPrime(A,B,N): inputs positive integers A and B and a #positive integer N and finds all composite (i.e. non-prime) #n such that PAB(A,B,n)/n is an integer. PseudoPrimeJohn:=proc(A,B) local a,b,c,d,n,P: a:=3: b:=0: c:=2*A: P:=Primes(2^20): #want n|c and n composite for n from 2 do if c mod n = 0 and not member(n,P) and n mod A <> 0 and n mod B <>0 then RETURN(n): fi: d:=B*a+A*b: a:=b: b:=c: c:=d: od: end: #PseudoPrime(A,B,N): inputs positive integers A and B and a #positive integer N and finds all composite (i.e. non-prime) #n such that PAB(A,B,n)/n is an integer. PseudoPrime:=proc(A,B,N) local a,b,c,d,n: a:=3: b:=0: c:=2*A: #want n|c and n composite for n from 2 to N do if c mod n = 0 and not IsPrime(n) then print(n): fi: d:=B*a+A*b: a:=b: b:=c: c:=d: od: n: end: #Mul(P,Q) that inputs two permutations (written as lists) of the same lengths and outputs their product. For example, #Mul([2,3,1,4],[2,1,4,3]); #should output #[1,4,2,3] Mul:=proc(P,Q) local i: [seq(Q[P[i]],i=1..nops(P))]: end: #Gp(S) that inputs a set of permutations of the same length #(output FAIL if S is not a set or it is not a set of lists #of the same length, etc.) and outputs the set of all #permutations that belong to the group generated by the #members of S. (Don't forget the identity permutation!). #For example #Gp({[2,1]}); #should output #{[1,2],[2,1]}. #Gp({[2,1,3,4],[1,2,4,3]}); #should output #{[1,2,3,4],[2,1,3,4],[1,2,4,3],[2,1,4,3]} . Gp:=proc(S) local G1,G,pi,g: G1:={}: G:=S: while G1<>G do G1:=G: for pi in S do for g in G do G:=G union {Mul(g,pi)}: od: od: od: G: end: #Find the subgroup of S6 generated by the three rotations #(about the x,y, and z axes) of a cube. Using Nathaniel Shar's #suggestion, let's stick to the usual convention: #Front: 1 ; Back: 6; Left:3; Right: 4; Bottom:2; Top=5. #Gp({[1,4,2,5,3,6],[5,1,3,4,6,2],[4,2,1,6,5,3]}); #{[1, 2, 3, 4, 5, 6], [1, 3, 5, 2, 4, 6], [1, 4, 2, 5, 3, 6], [1, 5, 4, 3, 2, 6], [2, 1, 4, 3, 6, 5], [2, 3, 1, 6, 4, 5], [2, 4, 6, 1, 3, 5], [2, 6, 3, 4, 1, 5], [3, 1, 2, 5, 6, 4], [3, 2, 6, 1, 5, 4], [3, 5, 1, 6, 2, 4], [3, 6, 5, 2, 1, 4], [4, 1, 5, 2, 6, 3], [4, 2, 1, 6, 5, 3], [4, 5, 6, 1, 2, 3], [4, 6, 2, 5, 1, 3], [5, 1, 3, 4, 6, 2], [5, 3, 6, 1, 4, 2], [5, 4, 1, 6, 3, 2], [5, 6, 4, 3, 1, 2], [6, 2, 4, 3, 5, 1], [6, 3, 2, 5, 4, 1], [6, 4, 5, 2, 3, 1], [6, 5, 3, 4, 2, 1]} #PermToCyc(P): inputs a permutation P and outputs its #cycle structre, as a set of cycles, with the convention #that the smallest entry of the cycle is written first. #For example #PermToCyc([3,5,6,4,2,1]); #should output #{[1,3,6],[2,5],[4]} . PermToCyc:=proc(P) local n,cycles,c,left,i,j: n:=nops(P): cycles:={}: left:={seq(i,i=1..n)}: while left<>{} do i:=left[1]: c:=[i]: left:=left minus {i}: j:=P[i]: while j<>i do c:=[op(c),j]: left:=left minus {j}: j:=P[j]: od: cycles:=cycles union {c}: od: cycles: end: #Polya(G,c): inputs a subgroup of the symmetric group Sn, G, #and outputs the number of ways to color a combinatorial #structure on n vertices with c colors, whose group of #symmetry happens to be G. #For example #Polya({[1,2],[2,1]},c); #should output #(c^2+c)/2 Polya:=proc(G,c) local g,cyc,C: C:=0: for g in G do cyc:=PermToCyc(g): C:=C+c^nops(cyc): od: C/nops(G): end: #Polya(Gp({[1,4,2,5,3,6],[5,1,3,4,6,2],[4,2,1,6,5,3]}),c); # 1 6 1 3 1 4 1 2 # -- c + - c + - c + - c # 24 2 8 3 #1, 10, 57, 240, 800, 2226, 5390, 11712, 23355, 43450 #A047780 Number of inequivalent ways to color faces of a cube using at most n colors.