Seeking an efficient way to calculate $\sum_{k=2}^n\frac{1}{a_k}$ in a computer program, where the $a_k$ are integers stored in a vector

Question

I need an efficient way to compute sums of reciprocal of numbers using a computer program. Currently, I have a set of integers $\{a_{0}, a_{1}, \ldots a_{n}\}$, and I want to compute

$$\sum_{i=0}^{n} \frac{1}{a_{0}}$$ as a fraction.

I know what $n$ is. Is there a good way to do this? For example, if $n = 1$, it's just $1/a_{0}$. If $n = 2$, it's $(a_{0} + a_{1})/(a_{0} \cdot a_{1})$.

But, it gets more complicated for $n = 3$.

---

More specifically, I'm writing a computer program to compute the sum $S$ given by

$$S = \sum_{k=2}^{N} \frac{1}{v(k)u(k)}$$

where $v(k)$ and $u(k)$ are guaranteed to be integers. I don't think what the functions are doing actually matters for my question, but $v(k)$ represents the largest prime $p$ that does not exceed $k$, and the function $u(k)$ represents the smallest prime strictly greater than $k$. Also, $N$ is passed in as a parameter. Currently, I've stored each of the products of $v(k)u(k)$ in a vector.

Answer 1

You can store each partial sum as a fraction by using 2 vectors, or one vector of an object with 2 integers. In particular, you store the numerator and denominator, starting off with $1$ for the numerator and the first value of the denominator. Then for each next value to add, you can create the next partial sum of a numerator and denominator as follows for the $m$'th (for $m \ge 2$) term, where $n_{m - 1}$ is the latest stored numerator, $d_{m - 1}$ is the latest stored denominator and $\frac{1}{a_m}$ is the next fraction value:

$$\cfrac{n_{m - 1}}{d_{m - 1}} + \cfrac{1}{a_m} = \cfrac{a_m n_{m - 1} + d_{m - 1}}{a_m d_{m - 1}} \tag{1}\label{eq1} $$

This means the new next numerator can be stored as $n_m = a_m n_{m - 1} + d_{m - 1}$ and the new next denominator can be stored as $d_m = a_m d_{m - 1}$. To get a particular value, as I suggested in my comment to your question, you can either retrieve it from the vector(s), if they're already there, or use the last available one to calculate additional terms, potentially also adding each set of numerator / denominator values to your vector (if there is enough memory available).

This is one of the simplest ways to handle this issue. However, you may wish to optimize things like trying to find any common factors of the numerator and denominator to reduce their values as, depending on the type of integer type objects you are using & have available, how large each integral value can be and what sort of maximum size of $n$ is permitted, you can get numeric overflow. However, this is mainly a computing issue that you can determine on your own or ask elsewhere, such as an appropriate other forum on StackExchange.

Answer 2

To repeat myself, from another site, on a different problem:

The way I'd do it? Build a class representing fractions. Obviously, this class would have two integer fields for the numerator and denominator.

Methods to implement:

• Reduction to lowest terms. Find the gcd of the numerator and denominator, and divide both by it. Swap signs if necessary so that the denominator becomes positive. This one's behind the scenes - you should never need to call it from the outside, only from other methods.

• A constructor, that takes a pair of integers as input and gives you that fraction.

• Arithmetic. The problem technically only calls for addition, but subtraction and multiplication aren't any harder. Division or inverses call for error handling, if you go there.

If you're going to reuse this for other purposes, some other things like comparison would be worthwhile. I was thinking in Java terms when I wrote this originally; the details of the jargon might change, but the concepts will be there in any standard programming language.

Answer 3

Using the method described by John Omielan to get the values of $S$ for $n<20$, I examined the output and was able to find this closed-form solution: $$\sum_{k=2}^{n} \frac{1}{v(k)u(k)}=\frac{v(n)u(n)-2(v(n)+u(n)-n-1)}{2v(n)u(n)}$$