#restart; read `d:/Teaching/NumberTheory/Project.txt`;

############################
# problem 1) LL Algorithm
############################

# RunLL
# input: positive integer N
# output: All (but(2^2-1)),Mersene primes up 2^N-1 

RunLL := proc(N) option remember;

local ret,i;

ret := [];

for i from 2 to N do
	if isprime(i) and LL(i) then
		ret := [op(ret),i];
	fi:
od:

ret;

end:

# LL
# input : a prime number p
# output : return true if 2^p-1 is a prime
# return false otherwise

LL := proc(p) 

##Fill in the details here.

end:


#################################
# Problem 2) 
#################################

# Par: 
# Input: n and a set S
# Output: a set of partition 
# (in decreasing order)
# of n where parts are in set S
# Try: Par(15,{3,1});

Par := proc(n,S) option remember; 

local i,k,newS,ret;

if S = {} then
	return(S);

elif nops(S) = 1 then
	if n mod S[1] = 0 then
		return( {[S[1]$(n/S[1])]});
	else
		return({});
	fi:
fi:

k := S[1];
ret := {};

for i from 0 to floor(n/k) do
	newS := Par(n-i*k, S minus {k} );
	ret := ret union {seq( [op(s),k$i], s in newS)} ;
od:

return(ret);

end:

# FS: 
# Input : a list of number N
# Output: the set of integer S 
# where p(n|S)=N[n] or FAIL.

FS := proc(N) local S: 
	return(FSS(N,{},1));
	
end:

FSS := proc(N,S,n)
if N = [] then
	return(S);
fi:

if N[1] = nops(Par(n,S)) then ;
	return( FSS( [op(2..nops(N),N)] , S, n+1  ));
elif N[1] = nops(Par(n,S union {n})) then
	return( FSS( [op(2..nops(N),N)] , S union {n}, n+1  )  );
else 
	return(FAIL);
fi:
end:

#####################################
## Example for problem 2)          ##
#####################################

# Find a set N such that 
# p(n| parts in N) = p(n| distinct parts).

# ProbDis
# Input : positive number n
# Output: the answer set N to the problem above 
# Try  ProbDis(25);

ProbDis := proc(n);
FS([seq( nops(Dis(i)), i =1..n)]);
end:

# Dis
# Input : positive number n
# Output: the set of partitions of n
# into distinct parts
# Try  Dis(10);

Dis := proc(n) local s,S,ret;
	
S := Par(n, {seq(i,i=1..n)});
ret := {};

for s in S do
	ret := ret union {TestDis(s)};
od:

return(ret);
end:

# TestDis
# Input : a partition s;
# Output: return s if parts in s are all distinct
# or return NULL otherwise.
# Try  TestDis([5,3,1]);

TestDis := proc(s) local dis;

dis := {seq(s[i]-s[i+1], i = 1..nops(s)-1)};
if member(0, dis) then
	return();
fi:
	
return(s);
end:


###############
# Problem 50
###############

# Prob50
# Input : positive number n
# Output: the answer set N to the problem 50
# Try  Prob50(25);

Prob50 := proc(n);
FS([seq( nops(RR2(i)), i =1..n)]);
end:

# RR2
# Input : positive number n
# Output: the set of partitions of n
# into 2-distinct parts >= 2.
# Try  RR2(15);

RR2 := proc(n) local s,S,ret;
	
S := Par(n, {seq(i,i=1..n)});
ret := {};

for s in S do
	ret := ret union {Test50(s)};
od:

return(ret);
end:

# Test50
# Input : a partition s
# Output: return s if parts
# satisfy the conditions above
# or return NULL otherwise.
# Try  Test50([8,3,2,1]);

Test50 := proc(s) 

## Fill in the details here.

end:

###############
# Problem 51
###############

# Prob51
# Input : positive number n
# Output: the answer set N to the problem 51 
# Try  Prob51(25);

Prob51 := proc(n);
FS([seq( nops(GG(i)), i =1..n)]);
end:

# GG
# Input : positive number n
# Output: the set of partitions of n
# into 2-distinct parts with 
# no consecutive multiple of 2.
# Try  GG(15);

GG := proc(n) local s,S,ret;
	
S := Par(n, {seq(i,i=1..n)});
ret := {};

for s in S do
	ret := ret union {Test51(s)};
od:

return(ret);
end:

# Test51
# Input : a partition s
# Output: return s if parts
# satisfy the conditions above
# or return NULL otherwise.
# Try  Test51([8,3,2,1]);

Test51 := proc(s) 

## Fill in the details here.

end:


###############
# Problem 52
###############

# Prob52
# Input : positive number n
# Output: the answer set N to the problem 52 
# Try  Prob52(25);

Prob52 := proc(n);
FS([seq( nops(GG2(i)), i =1..n)]);
end:

# GG2
# Input : positive number n
# Output: the set of partitions of n
# into 2-distinct parts >= 3 with 
# no consecutive multiple of 2.
# Try  GG2(15);

GG2 := proc(n) local s,S,ret;
	
S := Par(n, {seq(i,i=1..n)});
ret := {};

for s in S do
	ret := ret union {Test52(s)};
od:

return(ret);
end:

# Test52
# Input : a partition s
# Output: return s if parts
# satisfy the conditions above
# or return NULL otherwise.
# Try  Test52([8,3,2,1]);

Test52 := proc(s) 

## Fill in the details here.

end:


###############
# Problem 53
###############

# Prob53
# Input : positive number n
# Output: the answer set N to the problem 53 
# Try  Prob53(25);

Prob53 := proc(n);
FS([seq( nops(Sc(i)), i =1..n)]);
end:

# Sc
# Input : positive number n
# Output: the set of partitions of n
# into 3-distinct parts with no
# consecutive multiple of 3.
# Try  Sc(15);

Sc := proc(n) local s,S,ret;
	
S := Par(n, {seq(i,i=1..n)});
ret := {};

for s in S do
	ret := ret union {Test53(s)};
od:

return(ret);
end:

# Test53
# Input : a partition s
# Output: return s if parts
# satisfy the conditions above
# or return NULL otherwise.
# Try  Test53([8,3,2,1]);

Test53 := proc(s) 

## Fill in the details here.

end:

###############
# Problem 55
###############

# Prob55
# Input : positive number n
# Output: the answer set N to the problem 55 
# Try  Prob55(25);

Prob55 := proc(n);
FS([seq( nops(Andrew(i)), i =1..n)]);
end:

# Andrew
# Input : positive number n
# Output: the set of partitions of n
# parts >= 2, odd part is distinct and
# at least three greater than the next
# smaller part.
# Try  Andrew(15);

Andrew := proc(n) local s,S,ret;
	
S := Par(n, {seq(i,i=1..n)});
ret := {};

for s in S do
	ret := ret union {Test55(s)};
od:

return(ret);
end:

# Test55
# Input : a partition s
# Output: return s if parts
# satisfy the conditions above
# or return NULL otherwise.
# Try:  Test55([8,3,2,1]);

Test55 := proc(s) 

## Fill in the details here.

end: