2
$\begingroup$

I am trying to create a list where each element of the list is calculated using the sum of all previous elements of the list and also uses the $N$th element of another list. The initial value of the list is a known quantity. $k1$ is simply a constant value. $k2$ is a known list of $N$ elements.

$\quad \quad Q_N=\sum_{i=0}^{N-1}{k1(Q_i/k2_N)},\,N>0$ $\quad \quad Q_0=k0$

I'm not quite sure how to code this. I think the Nest function is somewhat close to what I want, but I need to keep plugging in the sum of all previous values, not just the previous value.

Any help would be greatly appreciated.

Edit: As I keep digging, FoldList seems like it might be useful, but I just can't seem to crack this problem.

Edit 2: It may be relevant that $N$ is going to be rather large. The context is a numeric solution to the time evolution of a system. So I want to have smaller time-steps, which leads to a large number of elements.

Improve this question
$\endgroup$
  • 1
    $\begingroup$ Try something like Accumulate? reference.wolfram.com/language/ref/Accumulate.html $\endgroup$ – Chen Stats Yu Jan 9 '15 at 14:23
  • $\begingroup$ Accumulate looks interesting. I'll read up on that. Thanks! $\endgroup$ – matt Jan 9 '15 at 14:25
  • $\begingroup$ Ultimately, do you only need Q[N] or all Q[i] for 0 ≤ i ≤ N? $\endgroup$ – Martin Ender Jan 9 '15 at 15:38
  • $\begingroup$ Ultimately, I will need all Q[i]'s, but just getting Q[N] would be a great start. $\endgroup$ – matt Jan 9 '15 at 15:41
  • $\begingroup$ Is k1 an arbitrary function? If yes, then FoldList which seemed to be the way to do it no longer works. $\endgroup$ – FJRA Jan 9 '15 at 15:58
3
$\begingroup$ 
q[0] = 1;
k2 = {1,2,3,4,5};
q[n_] := q[n] = Sum[k1 q[i]/k2[[n]], {i, 0, n - 1}]

q /@ Range@5
(*{5, 15, 35, 70, 126}*)
Improve this answer
$\endgroup$
  • 1
    $\begingroup$ You should note that this is still $O(n)$. It's nice and simple though. $\endgroup$ – Martin Ender Jan 10 '15 at 20:45
  • $\begingroup$ Wow, this is very slick. This was actually one of my first thoughts. There is a tutorial in the documentation called Functions That Remember Values They Have Found. I couldn't initially wrap my brain around it, but now I see how simple it is. I'm assuming that your value of k1 is 5. I would appreciate if you could confirm that, as I am making sure I understand this fully. Also, I posted another question that has to do with this situation. This would be a good answer to that if you want to put it up there too. mathematica.stackexchange.com/questions/71432 $\endgroup$ – matt Jan 12 '15 at 15:10
  • $\begingroup$ Ummm. Scratch my above comment. I meant to say, this is $O(n^2)$, not $O(n)$. $\endgroup$ – Martin Ender Jan 12 '15 at 16:08
3
$\begingroup$

Here is one way to do it using FoldList. It will give you a list of all $Q_i$ for $0 < i \le n$.

n = 5;
k0 = 1;
k1 = 5;
k2 = {1, 2, 3, 4, 5};
FoldList[
 (k2[[#2]] + k1)#/k2[[#2 + 1]] &,
 k0 k1/k2[[1]], 
 Range[n - 1]
]
(* {5, 15, 35, 70, 126} *)

An important observation, which reduces the runtime from $O(n^2)$ to $O(n)$: for $i > 1$ we have

$$ Q_N = \sum_{i=0}^{N-1} \frac{k_1 Q_i}{k_{2,N}} = \sum_{i=0}^{N-2} \frac{k_1 Q_i}{k_{2,N}} + \frac{k_1 Q_{N-1}}{k_{2,N}} = \frac{k_{2,N-1}}{k_{2,N}}\sum_{i=0}^{N-2} \frac{k_1 Q_i}{k_{2,N-1}} + \frac{k_1 Q_{N-1}}{k_{2,N}} = \frac{Q_{N-1}}{k_{2,N}}(k_{2,N-1}+k_1) $$

Note that this doesn't hold for $Q_1$, which is why we start the folding from there, instead of $Q_0$, such the first call of the function computes $Q_2$.

This observation lets us compute $Q_N$ solely based on $Q_{N-1}$, instead of having to look at all previous $Q_i$. The function inside the FoldList computes exactly this expression, where # is $Q_{N-1}$ and #2 is $N$.

Lastly, we fold onto a range of $i$ values, which we need to index into the $k_2$ list.

Improve this answer
$\endgroup$
  • $\begingroup$ When I try to run your code, I get an error that has to do with the #k2 part. It says Part 2 (and 3 and 4) of #k2 does not exist. I simply copied and pasted your code into a newly started kernel, so that there wouldn't be any errors from stuff I had tried. I am running Mathematica 10.0. $\endgroup$ – matt Jan 9 '15 at 16:43
  • 1
    $\begingroup$ @matt Sorry, I accidentally swapped two characters. $\endgroup$ – Martin Ender Jan 9 '15 at 16:53
  • $\begingroup$ Thank you very much. I am still working on understanding what is going on, but your example is working on my machine with that last edit. $\endgroup$ – matt Jan 9 '15 at 16:55
  • 1
    $\begingroup$ @matt If it helps, think of # as $Q_{N-1}$ and of #2 as $N$. $\endgroup$ – Martin Ender Jan 9 '15 at 16:57
0
$\begingroup$ 
myFirstList = RandomVariate[UniformDistribution[], {10}];

mySecondList = RandomVariate[UniformDistribution[], {10}];

Take[FoldList[Plus, 0, myFirstList], {2,Length[myFirstList] + 1}] + mySecondList
Improve this answer
$\endgroup$
  • $\begingroup$ You've got an error: myFistList and correcting it produces another error. $\endgroup$ – Mr.Wizard Jan 10 '15 at 18:04
  • 1
    $\begingroup$ It's a bit hard to tell; were you aiming for Accumulate[myFirstList] + mySecondList? $\endgroup$ – Mr.Wizard Jan 10 '15 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.