#Yusra Naqvi #HW 24 #OK to post ################################################################################ #1 #P(n) is defined by #P(0)=3,P(1)=0,P(2)=2 #and for n ≥ 3, by the recurrence #P(n)=P(n-2)+P(n-3) P:=proc(n) option remember: if n=0 then 3: elif n=1 then 0: elif n=2 then 2: else P(n-2)+P(n-3): fi: end: ### #Perrin pseudoprimes between n and N. PP:=proc(n,N) local S,i: S:={}: for i from n to N do if type(P(i)/i,integer) then if not isprime(i) and i<>1 then S:=S union {i}: fi: fi: od: S: end: ### #The Perrin pseudoprimes less than 400000 are: #{271441} #The computation takes too long for my computer beyond this point. ### #Matrix formula for Perrin numbers P2:=proc(n) local M,b: with(linalg): M:=matrix( [ [0,1,0], [0,0,1], [1,1,0] ] ): M:=evalm(M^n): b:=vector( [3,0,2] ): b:=multiply(M,b): b[1]: end: ### #P(2^20)= #4907486623903722805297725232245265827055249791214434138116795812716167879116566 #939532285784203887477[...127856 digits...]2821351663672505468646787355488245123 #653236152134178820592060343691155925212651423598055857578598490 ################################################################################ #2 #PAB(A,B,n): generalized Perrin sequence, defined by #PAB(A,B,0)=3, PAB(A,B,1)=0, P(A,B,2)=2*A #and for n ≥ 3, by the recurrence #PAB(A,B,n)=A*PAB(A,B,n-2)+B*PAB(A,B,n-3) PAB:=proc(A,B,n) option remember: if n=0 then 3: elif n=1 then 0: elif n=2 then 2*A: else A*PAB(A,B,n-2)+B*PAB(A,B,n-3): fi: end: ### #PseudoPrime(A,B,N): inputs positive integers A and B and a positive integer N #and finds all composite n<=N such that PAB(A,B,n)/n is an integer. PseudoPrime:=proc(A,B,N) local S,i: S:={}: for i from 2 to N do if type(PAB(A,B,i)/i,integer) then if not isprime(i) and i<>1 then S:=S union {i}: fi: fi: od: S: end: ################################################################################ #3 #Mul(P,Q): inputs two permutations (written as lists) of the same lengths and #outputs their product Mul:=proc(P,Q) local L,i: if nops(P)<>nops(Q) then return(FAIL): fi: L:=[]: for i from 1 to nops(P) do L:=[op(L),Q[P[i]]]: od: L: end: ################################################################################ #4 #Gp(S): inputs a set of permutations of the same length and outputs the set #of all permutations in the group generated by the members of S Gp:=proc(S) local check,G,NewP,s,p: if not type(S,set) then return(FAIL): fi: check:={}: for s in S do check:=check union {nops(s)}: od: if nops(check)<>1 then return(FAIL): fi: G:={}: NewP:=S: while NewP minus G <> {} do G:=G union NewP: NewP:={seq(seq(Mul(s,p),s in S),p in NewP)}: od: G: end: ################################################################################ #5 #Using the convention that a cubic die is given by: #Front: 1 ; Back: 6; Left:3; Right: 4; Bottom: 2; Top: 5; #we get the following permutations: #Rotation about x-axis: #[1,4,2,5,3,6] #Rotation about y-axis: #[2,6,3,4,1,5] #Rotation about z-axis: #[4,2,1,6,5,3] #The subgroup of S_6 generated by these rotations is: #Gp({[1,4,2,5,3,6],[2,6,3,4,1,5],[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]} ################################################################################ #6 #PermToCyc(P): inputs a permutation P and outputs its cycle structure. PermToCyc:=proc(P) local S,P1,c,L: S:=[]: P1:=convert(P,set): while P1 <> {} do c:=min(P1): L:=[]: while not member(c,L) do L:=[op(L),c]: c:=P[c]: od: S:=[op(S),L]: P1:=convert(P1,set) minus convert(L,set): od: S: end: ################################################################################ #7 #Polya(G,c): inputs a subgroup, G, of the symmetric group S_n, 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 Polya:=proc(G,c): add(c^nops(PermToCyc(g)),g in G)/nops(G): end: ################################################################################ #8 #CC(c): the number of ways of coloring a cube with c colors, where two colorings #are considered the same if one can be gotten from the other by a sequence of #rotations about the x,y,z-axes CC:=proc(c) local G: G:=Gp({[1,4,2,5,3,6],[2,6,3,4,1,5],[4,2,1,6,5,3]}): Polya(G,c): end: ### #[seq(CC(i),i=1..30)]; #[1, 10, 57, 240, 800, 2226, 5390, 11712, 23355, 43450, 76351, 127920, 205842, #319970, 482700, 709376, 1018725, 1433322, 1980085, 2690800, 3602676, 4758930, #6209402, 8011200, 10229375, 12937626, 16219035, 20166832, 24885190, 30490050] #A47780 in OEIS ################################################################################