Creating a Program to Decompose a Number and Run a Function on that Decomposition

[CTSB01]

I've been puzzling over how to get a certain function working in Python. The function, takes positive integers to other positive integers as follows:

    Phi_m(n2) = Phi_m(m*n + r) = m*x[n1] + r*(x[n1 + 1] - x[n1])

The above terms are all integer valued and are defined as follows:

    n2 = the (n2)th slot of the output string
    
    m = a fixed positive integer
    
    n = some multiple of m such that n*m is less than or equal to n2
    
    r = a remainder term to fill in the amount missing from n*m in decomposing n2
    
    x[n1] = the element in the [n1]th slot of the input string
    
    x[n1 + 1] = the element in the [n1 + 1]th slot of the input string

In general we start with a string of numbers, say 0, 1, 1, 2, 3, 3 and end up with a string of (k+1)m-1 terms, where k is the number of terms you started with. To use the function we first fix an m, say m = 2.  Now we decompose n2 in terms of m, where n2 is representing a 'slot' of our output sequence. Say n2=5.  Then we are asking 'what is in the fifth 'slot' of our output string'.  In this case our total output string will be of length (5+1)2+1.  Notice that we do not count 0 - it is always present and is for our purposes the 0th term, hence we have 5 initial terms. To answer our question of what goes in the slot we take 5=2*2+1 as our decomposition.  Now that we have a decomposition we can apply our function: 

    F(x(5)) = F(x(2*2+1)) 2x[2] + 1(x[3] - x[2]). 

The thing is, for Python to do this it has to know how to decompose each number. So it knows 2 is fixed, and knows 2*3 is too much and so chooses 2*2. Then it has to know this is too little and add remainder 1. Only once it's done this can it actually grab n = 5. That is, it can run the function. It seems clear that once it knows how to do this it can just run through every n in our range, but I'm really not sure how to program the meat of this function.

Now to answer some questions:  Is x a function? A list? A number? x[n] is essentially a list.   

What do you mean when you say "values of an input string"? What's the signature of Phi_m? 

The function acting on this list takes in a single element of the list, gives us a decomposition of the number somehow, and then applies the 'formula' you see above.  In this sense it is more of a two step algorithm.

To give another example, say we want to apply psi_2 to 0,1,2,2.  Then we have an output of length (3+1)2-1=7.  F(7)=F(2*3+1) = 2x[3] + 1(x[4] - x[3]).  As we can see, we are missing x[4] (remember 0 doesn't count as a term).  So we actually need to stop our calculation one shy of the 7 terms we 'should' have.  Hence, although we actually want 7 terms the program really only needs to give 6 terms, the other term can be hand calculated, or the user can append one extra term to the input string 0,1,2,2 and run the program again.

Please let me know if this is unclear.  I will certainly continue revising until it makes sense to those reading.