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.

$\endgroup$
6
  • 1
    $\begingroup$ Try something like Accumulate? reference.wolfram.com/language/ref/Accumulate.html $\endgroup$ Commented Jan 9, 2015 at 14:23
  • $\begingroup$ Accumulate looks interesting. I'll read up on that. Thanks! $\endgroup$
    – matt
    Commented Jan 9, 2015 at 14:25
  • $\begingroup$ Ultimately, do you only need Q[N] or all Q[i] for 0 ≤ i ≤ N? $\endgroup$ Commented Jan 9, 2015 at 15:38
  • $\begingroup$ Ultimately, I will need all Q[i]'s, but just getting Q[N] would be a great start. $\endgroup$
    – matt
    Commented Jan 9, 2015 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
    Commented Jan 9, 2015 at 15:58

3 Answers 3

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}*)
$\endgroup$
3
  • 1
    $\begingroup$ You should note that this is still $O(n)$. It's nice and simple though. $\endgroup$ Commented Jan 10, 2015 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
    Commented Jan 12, 2015 at 15:10
  • $\begingroup$ Ummm. Scratch my above comment. I meant to say, this is $O(n^2)$, not $O(n)$. $\endgroup$ Commented Jan 12, 2015 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.

$\endgroup$
4
  • $\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
    Commented Jan 9, 2015 at 16:43
  • 1
    $\begingroup$ @matt Sorry, I accidentally swapped two characters. $\endgroup$ Commented Jan 9, 2015 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
    Commented Jan 9, 2015 at 16:55
  • 1
    $\begingroup$ @matt If it helps, think of # as $Q_{N-1}$ and of #2 as $N$. $\endgroup$ Commented Jan 9, 2015 at 16:57
0
$\begingroup$
myFirstList = RandomVariate[UniformDistribution[], {10}];

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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