#Charles Wolf #Homework 24 ##Feel free to post.## #1) P:=proc(n) local C0,C1,C2,C3,i,S: S:=[]: C0:=3: C1:=0: C2:=2: for i from 3 to n do C3:=C0+C1: C0:=C1: C1:=C2: C2:=C3: if C3 mod i=0 then if (not isprime(i)) then S:=[op(S),i]: fi:fi: od: S: end: #P(1000000)=[271441,904631]: A:=Matrix(3); A[1,2]:=1; A; A[2,3]:=1: A[3,1]:=1: A[3,2]:=1: A; B:=(A)^(2^20): C:=Matrix(3,1); C[1,1]:=3: C[3,1]:=2: C; with(LinearAlgebra); MatrixMatrixMultiply(B,C); %[3,1]; #outputs 8612038673693026305428700090429433779535296415809096544136897653785870271721964924543152310873140605[...1278 ########################################################### #2) #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 C1,C0,C2,C3,S,i: S:=[]: C0:=3: C1:=0: C2:=2: for i from 3 to n do C3:=B*C0+A*C1: C0:=C1: C1:=C2: C2:=C3: if C3 mod i=0 then if (not isprime(i)) then S:=[op(S),i]: fi:fi: od: S: end: ############################################################ #3) #Mul(P,Q) that inputs two permutations (written as lists) of the same lengths and outputs their product. Mul:=proc(P,Q) local i,R: R:=[]: for i from 1 to nops(P) do R:=[op(R),Q[P[i]]]: od: end: ############################################################## #4) #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!). Gp:=proc(S) local S1,S2,s, t,u,i: S1:={}: S2:=S: while S2 minus S1 <> {} do S1:=S2: for s in S1 do for t in S1 do S2:=S2 union {Mul(s,t)}: od:od: od: S2 union {[seq(i,i=1..nops(S2[1]))]}: end: ################################################################ #5) #Gp({[1,4,2,5,3,6],[2,6,3,4,1,5],[3,2,6,1,5,4]}); # {[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]} ################################################################## #6) #PermToCyc(P) that inputs a permutation P and outputs its cycle structure, as a set of cycles, with the convention that the smallest entry of the cycle is written first. PermToCyc:=proc(P) local c,k,i,C,w,c1,j: C:={}: for i from 1 to nops (P) do w:=true: for c1 in C do if member(i,c1) then w:=false:fi: od: if w then c:=[i]: k:=P[i]: while k<>i do c:=[op(c),k]: k:=P[k]: od: C:=C union {c}: fi: od: C: end: #################################################################### #7) # Polya:=proc(G,c) local P,g: P:=0: for g in G do P:=P+c^PermToCyc(g): od: P/nops(G): end: ##################################################################### #8) CC:=proc(c):Polya(Gp({[1,4,2,5,3,6],[2,6,3,4,1,5],[3,2,6,1,5,4]}),c):end: seq(CC(c),c=1..15); #1, 10, 57, 240, 800, 2226, 5390, 11712, 23355, 43450, 76351, 127920, 205842, 319970, 482700 #It is in OEIS!