# Author: John Lentfer
# Date: May 11, 2021
def generatePLRS(n, coeffs):
"""
Generates a PLRS.
Parameters:
n (int): Number of PLRS terms to generate.
coeffs (lst): Coefficients used to define the PLRS.
Returns:
lst: List of n terms of the PLRS defined by coeffs.
"""
L = len(coeffs)
terms = [1]
# generate the first L terms
for _ in range(min(n, L-1)):
terms.append(sum(terms[-1-i]*coeffs[i] for i in \
range(len(terms)))+1)
# generate any additional terms
for _ in range(n-L):
terms.append(sum(terms[-1-i]*coeffs[i] for i in \
range(L)))
return terms
def PLRSdecomposition(coeffs, n):
"""
Represents the decomposition of a number into terms of
a PLRS.
Parameters:
coeffs (lst): The list of coefficients used to generate
the PLRS.
n (int): A number to decompose.
Returns:
lst: A list where each entry contains a decomposition
block and the location of the rightmost element in the
decomposition block. The indexing begins with 0 for "0"
and is i for "h_i", the i-th term in the PLRS.
"""
# generate enough PLRS terms
a = 10
plrs = generatePLRS(a, coeffs)[:]
while plrs[-1] < n:
a += 1
plrs = generatePLRS(a, coeffs)[:]
# begin making the decomposition
l = []
while n > 0:
(l, n) = decomp(l, plrs, coeffs, n)
location_list = []
for r in range(len(l)):
location = l[r][1]
length = len(l[r][0])
location_list.append([length, location])
# check for gaps
for t in (range (len(location_list)-1)):
ending = location_list[t][1] - location_list[t][0]
gap = ending - location_list[t+1][1]
shift = 0
while gap > 0:
l.insert(t+1+shift, [[0], ending - shift])
gap -= 1
shift += 1
# check for an initial gap
ending = location_list[-1][1] - location_list[-1][0]
gap = ending + 2
shift = 0
while gap > 0:
l.append([[0], ending - shift])
gap -= 1
shift += 1
# adjust the indexing
l = [[x[0],x[1]+1] for x in l]
return l
def decomp(l, plrs, coeffs, n):
"""
Helper function that assists in the decomposition of a
number.
Parameters:
l (lst): The decomposition blocks that have already
been determined.
plrs (lst): The PLRS generated by coeffs.
coeffs (lst): The coefficients used to generate the
PLRS.
n (int): The remaining amount left to decompose.
Returns:
l (lst): The previously determined decomposition
blocks, along with one more new decomposition block.
n (int): The new remaining amount left to decompose.
"""
# locate the index i of the larget term in the PLRS
# that will be used
i = 0
while plrs[i] <= n:
i += 1
i -=1
# locate the largest multiple of the largest term
# that will be used; if that is the maximum, consider
# the subsequent coefficients
coeffs_maxed = 0
temp_l = []
while True:
# j is the multiple of the sequence term
j = 0
while (j*plrs[i-coeffs_maxed] <= n) and \
(j <= coeffs[coeffs_maxed]):
j += 1
j -= 1
# j has now been maximized
temp_l.append(j)
n -= j*plrs[i-coeffs_maxed]
if j==coeffs[coeffs_maxed]:
coeffs_maxed += 1
else:
break
l.append([temp_l, i])
return (l, n)