Problem 2.3.5: Develop an algorithm to compute the sums for the first n terms of the following series:
(a) s = 1 + 2 + 3 + ... (b) s = 1 + 3 + 5 + ... (c) s = 2 + 4 + 6 + ... (d) s = 1 + 1/2 + 1/3 + ...
I want to generalize a function to create all these sums. Also there’s one from
Problem 2.3.8: Develop an algorithm to compute the sum of the first n terms of the series
s = 1 - 3 + 5 - 7 + 9 - ...
which should also be solved by the function.
One can easily see that all follow the general pattern on s = a_1 + a_2 + ... aka. a sum. The only thing that changes is the value of a_i. Let’s look at the individual patterns (I call 2.3.8 (e)):
(a) start = 1, increment = + 1 (b) start = 1, increment = + 2 (c) start = 2, increment = + 2 (d) start = 1, increment = ? (e) start = 1, increment = ?
Let’s take a look at (d) first. It doesn’t follow the ‘increment’ formula so easy. However, we can see that it follows an other formula: 1/1 + 1/2 + 1/3 which is inversed. That is, we generally need the previous value to create the next one.
When we take a look at (e) we can see, that it also depends on the previous value. 1, -3, 5, -7. Generally it adds two but changes the sign. Now we can extend our table.
(a) start = 1, increment = previous + 1, (b) start = 1, increment = previous + 2 (c) start = 2, increment = previous + 2 (d) start = 1, increment = (1 / ((1 / previous) + 1) ) (e) start = 1, increment = (abs(previous) + 2) * (-1)
I just want to explain quickly how I got the increments for (d) and (e). An example is always good.
For 1/2 we take the inverse which is (1 / (1/2)) = 2, add one which makes it 3 and take the inverse, which makes it 1/3. Done.
For (e) we add 2 to the absolute value (abs(-2) = 2), which is trivial and multiply it by -1 which just changes the sign. Example: 2 * -1 = -2, and -3 * -1 = 3.
Now, let’s write some code. I’m currently learning Clojure, so that’s my choice.
Clojure has some cool functions for doing that which I will use. Let’s start with the first series. The function is pretty straight forward:
(defn add-one [previous] (+ previous 1))
It takes a number and adds one. Looks good. One noticeable thing is that we also have the start attribute. And when you think about it it’s the same as the previous for the first call.
Here’s my function return-series which actually returns the series of terms. It’s evaluated lazily therefore it isn’t that problematic on the resources. Also it helps debugging the software in case something breaks.
(defn return-series
"Returns a series of a given series which is generated
by the function increment. This function takes a parameter
which is the previous value"
[start increment]
(lazy-seq
(let [value (increment start)]
(cons start (return-series value increment)))))
Here’s an example with the add-one function:
user=> (take 4 (return-series 1 add-one)) (1 2 3 4)
I need the take function because otherwise the return-series function creates an infinite series. Here are the functions for each series:
(defn add-one [previous] (+ previous 1)) (defn add-two [previous] (+ previous 2)) (defn inverse-add [previous] (/ 1 (+ 1 (/ 1 previous)))) (defn sign-add [previous] (* -1 (+ (abs previous) 2)))
Which return the sequence like we wanted:
user=> (take 4 (return-series 1 add-two)) (1 3 5 7) user=> (take 4 (return-series 2 add-two)) (2 4 6 8) user=> (take 4 (return-series 1 inverse-add)) (1 1/2 1/3 1/4) user=> (take 4 (return-series 1 sign-add)) (1 -3 -5 -7)
Now that we verified that the terms look correct, we can call get-sum:
(defn get-sum "Returns the sum of a given start value, number of elements and function" [start n function] (reduce + (take n (sum-series start function))))
user=> (get-sum 1 10 add-two) 120 user=> (get-sum 1 10 inverse-add) 55991/27720
It works.