# Experimental Math - Homework 24 - Due Sunday, April 22 # Phil Benjamin # Note: this file may be uploaded to the Experimental Math Website # Problem 1 # Perrin sequeunce: P(n): P(0) = 3, P(1) = 0, P(2) = 2 # P(n) = P(n-2) + P(n-3) (n > 2) # Fact: n prime ==> n divides P(n) # Fact: n divides P(n) =/=> n prime # Counterexample: n = 271441 (Adams and Shanks 1982) # Part 1a: find all Perrin-pseudo-primes < 10^6 # Results: # 271441 = (521)^2 # 904631 = (7)*(13)*(9941) # Search for Perrin Primes up to Nth element in sequence (maximum) FindPerrin := proc(N) local p, n, L3; L3 := [0, 2, 3]; for n from 4 to N do L3 := [L3[2],L3[3],L3[1]+L3[2]]; p := L3[3]; if (p mod n) = 0 and not isprime(n) then printf("n=%d\n",n); end if; end; end: # Part 1b: find P(2^20) [see Wikepedia: Perrin_number matrix formula] # Matrix formula (see Wikipedia: Perrin number) # [[0,1,0],[0,0,1],[1,1,0]]^n * [3,0,2] = [P(n),P(n+1),P(n+2)] # Problem 2 # Generalized Perrin sequence: PAB(A,B,[0,1,2]) = [3,0,2*A] # PAB(A,B,n) = A*PAB(A,B,n-2) + B*PAB(A,B,n-3) # PseudoPrime(A,B,N) # Output: sequence of all PAB-pseudoprimes for n <= N # that is, PAB(n) is not prime but n divides PAB(n) # TBD # Problem 3 # PermMul(P,Q) # Input: permutations P,Q form: [P(1),P(2),...P(n)] # Output: product P*Q # Example: Mul([2,3,1,4],[2,1,4,3]) --> [1,4,2,3] PermMul := proc(P,Q) local n,i; n := nops(P); return [seq(Q[P[i]],i=1..n)]; end: # Problem 4 # PermGp(S) # Input: set of permutations (check that lengths are the same!) # Output: set of all permutations in group generated by S # Examples: # Gp({[2,1]}) --> {[1,2],[2,1]} # Gp({[2,1,3,4],[1,2,4,3]}) --> # {[1,2,3,4],[2,1,3,4],[1,2,4,3],[2,1,4,3]} PermGp := proc(S) local G, G2, s1, g1; G := {}; G2 := S; while G <> G2 do G := G2; for s1 in S do for g1 in G do G2 := G2 union {PermMul(g1,s1)}; end; end; end; return G; end: # Problem 5 # Find group of rotations of cube generated by rotations around x, y, z axes. # Convention: Front = 1, Back = 6, Left = 3, Right = 4, Bottom = 2, Top = 5 # Note: x rotation [5,1,3,4,6,2] # Note: y rotation [1,4,2,5,3,6] # Note: z rotation [4,2,1,6,5,3] CubeGp := proc() return PermGp({[5,1,3,4,6,2],[1,4,2,5,3,6],[4,2,1,6,5,3]}) end: # Problem 6 # PermToCyc(P) # Input: permutation # Output: cycle structure of permutation # Example: PermToCyc([3,5,6,4,2,1]) --> {[1,3,6],[2,5],[4]} PermToCyc := proc(P) local Cyc,L,n, isDone; Cyc := {}; for n from 1 to nops(P) do # Check whether n already appears in cycle isDone := false; for L in Cyc while isDone = false do if member(n,L) then isDone := true; end if; end; if not isDone then L := [n]; while P[L[nops(L)]] <> L[1] do L := [op(L),P[L[nops(L)]]]; end; Cyc := Cyc union {L}; end if; end; return Cyc; end: # Problem 7 # Polya(G,c) # Input: G: subgroup of symmetric group Sn # Output: number of ways to color combinatorical structure with # automorphism group G using c colors # Example: Polya({[1,2],[2,1]},c) --> (1/2)(c^2 + c) # Problem 8 # CC(c) # Output: polynomial expression for number of ways of coloring cube with c colors.