### Kristen Lew, Homework 24 ### ExpMath, Spring 2012 ## Post if you wish. ### Problem 1 ## Background: The Perrin sequence 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) # Perrin (and other people, e.g. E.B. Escott in 1909) proved that if n is prime, # then P(n)/n must be an integer. Perrin and Escott wondered whether the converse is true. # Escott believed that it was false, but did not find a counterexample. # The first counterexample, n=271441, was found in 1982 by Adams and Shanks, # and again, in 2012, in a few minutes of programming and a few seconds of computation, # by Neil Lutz, and quite a few other people in today's class. # (a) Find all such n less than one million. # (b) By using the Matrix formula given in the wiki article, find P(2^20). Pfinder:=proc() local k,P0,P1,P2,P3,P: P:={}: P0:=3: P1:=0: P2:=2: for k from 3 to 1000000 do P3:=P0+P1: if type(P3/k,integer) and not type(k,prime) then P:=P union {k}: print℗: fi: P0:=P1: P1:=P2: P2:=P3: od: P: end: # Pfinder(); # {271441, 904631} ### Problem 2 ## Define the generalized Perrin sequence, PAB(A,B,n), 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) # Write a procedure, PseudoPrime(A,B,N) that 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. PAB:=proc(A,B,n) local k,P0,P1,P2,P3,P: P:={}: P0:=3: P1:=0: P2:=2*A: for k from 3 to n do P3:= B*P0 + A*P1: if type(P3/k,integer) and not type(k,prime) then P:=P union {k}: fi: P0:=P1: P1:=P2: P2:=P3: od: P: end: ### Problem 3 ## Write a procedure 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 perm,k: if nops( P) <> nops(Q) then RETURN(FAIL): fi: perm:=[seq(Q[P[k]],k=1..nops(Q))]: end: ### Problem 4 ## Write a procedure 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]}. # and 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 s,length,All,j,k,ident: if not type(S,set) then RETURN(FAIL): fi: length:=nops(S[1]): for s in S do if not type(s,list) then RETURN(FAIL): fi: if nops(s)<>length then RETURN(FAIL): fi: od: ident:=[seq(i,i=1..length)]: All:={ident} union S: for j from 1 to nops(S) do for k from 1 to nops(S) do All:= All union {Mul(S[j],S[k])}: od: od: All: end: ### Problem 5 ## 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],[4,2,1,6,5,3],[2,6,2,4,1,5]}); # {[1, 2, 3, 4, 5, 6], [1, 4, 2, 5, 3, 6], [1, 5, 4, 3, 2, 6], # [2, 3, 2, 6, 4, 5], [2, 4, 6, 1, 2, 5], [2, 6, 2, 4, 1, 5], # [4, 2, 1, 6, 5, 3], [4, 6, 2, 5, 1, 2], [4, 6, 2, 5, 1, 3], # [4, 6, 4, 5, 1, 3], [5, 4, 1, 6, 3, 2], [6, 2, 4, 3, 5, 1], [6, 5, 6, 4, 2, 1]} ### Problem 6 ## Write a procedure 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. For example # PermToCyc([3,5,6,4,2,1]); # should output # {[1,3,6],[2,5],[4]}. PermToCyc:=proc( P) local P1, Cyc, k, l, cyc, Pset: P1:=convert(P,set): Pset:=convert(P,set): Cyc:={}: while P1<>{} do k:=P1[1]: cyc:=[k]: P1:=P1 minus {k}: l:=P[k]: while k<>l do cyc:=[op(cyc),l]: P1:=P1 minus {l}: l:=P[l]: od: Cyc:=Cyc union {cyc}: od: Cyc: end: ### Problem 7 ## Write a procedure Polya(G,c) that 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, C: C:=0: for g in G do C:=C+c^nops(PermToCyc(g)): od: C/nops(G): end: ### Problem 8 ## Find a polynomial expression, CC(c), for 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 as above. Is the sequence # [seq(CC(i),i=1..infinity)] in Sloane? CC:=proc(c ) local Colors, G: G:=Gp({[1,4,2,5,3,6],[4,2,1,6,5,3],[2,6,2,4,1,5]}): Polya(G,c): end: