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