### 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: