This is a math oriented algorithms puzzle.
Let $\varphi$ be the golden ratio: $\dfrac{1+\sqrt{5}}{2}$.
Consider the following sum
$$S_n = [\varphi] + [2 \varphi] + \dots + [n\varphi]$$
i.e
$$ S_n = \sum_{k=1}^{n} [k \varphi]$$
where $[x]$ is the integer part of $x$.
Can you give an algorithm to compute $S_n$ that takes a polynomial in $\log n$ time?
[Solution]
Let $\varphi$ be the golden ratio: $\dfrac{1+\sqrt{5}}{2}$.
Consider the following sum
$$S_n = [\varphi] + [2 \varphi] + \dots + [n\varphi]$$
i.e
$$ S_n = \sum_{k=1}^{n} [k \varphi]$$
where $[x]$ is the integer part of $x$.
Can you give an algorithm to compute $S_n$ that takes a polynomial in $\log n$ time?
[Solution]
No comments:
Post a Comment