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.
--
http://mail.python.org/mailman/listinfo/python-list
