I need to calculate the following sum: $$S_{n} = \sum_{i=1}^{n} GCD(i + 1, 2)$$

where $GCD(x,y)$ stands for greatest common divisor of $x$ and $y$.

The terms of this sum simply boil down to:

$$\underbrace{2}_{a_{1}} + \underbrace{1}_{a_{2}} + \underbrace{2}_{a_{3}} + \underbrace{1}_{a_{4}} + \underbrace{2}_{a_{5}} + \underbrace{1}_{a_{6}} + ... $$

What might be worth noting is that the last term is $1$ if $n$ is even, and $2$ if $n$ is odd.

I need to compute the result as a function depending on $n$, that is: $S_{n} = f(n)$.

I was thinking about splitting it into two cases:

$$S_{n} = \begin{cases} f_{1}(n) \quad \iff \text{n is odd} \\ f_{2}(n) \quad \iff \text{n is even}\end{cases}$$

Any ideas on how to proceed with computing the result?

I computed the $f_{2}(n)$ and got $f_{2}(n)= \frac{3}{2}n$. Also, I believe $f_{1}(n)= \lceil \frac{3n}{2} \rceil$ would work.

So the final answer as:

$S_{n}= \lceil \frac{3}{2}n \rceil$

should be correct?

  • 1
    $\begingroup$ Hint. Just start counting the number of $1$'s and $2$'s in each case. $\endgroup$ – Shervin Sorouri Aug 30 '19 at 13:40
  • $\begingroup$ Thanks. Trying to work out a solution. $\endgroup$ – weno Aug 30 '19 at 13:47

If $i$ is even then the $GCD(i+1,2)=1$. If $i$ is odd then $GCD(i+1,2)=2$. The number of even number is $\left \lceil \frac{n}{2} \right \rceil$. The number of odds $n-\left \lfloor \frac{n}{2} \right \rfloor$. The formula is so: $$S_n=1\cdot\left \lfloor \frac{n}{2} \right \rfloor+2\cdot\left(n-\left \lfloor \frac{n}{2} \right \rfloor\right)=2n-\left \lfloor \frac{n}{2} \right \rfloor$$

  • $\begingroup$ Your solution is correct $\endgroup$ – Matteo Aug 30 '19 at 14:00

If $n=2k+1$ (odd) then there will be $k$ even nos. and $k+1$ odd nos. between $1$ and $n$. So the required sum will be $$S(n)=(k+1)1+(k)2=3k+1=\frac{3}{2}(n-1)+1=\frac{3n-1}{2}.$$ Likewise you can get the answer when $n$ is even as $$S(n)=3k=\frac{3n}{2}.$$

  • 1
    $\begingroup$ What do you think of my solution I just re-posted that includes the ceiling "thing"? Would it do the job? $\endgroup$ – weno Aug 30 '19 at 13:50

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.