The problem was to find
$$S_n = \sum_{k=1}^{n} [k \varphi]$$
where $\varphi$ is the golden ratio and $[x]$ is the integer part of $x$.
The challenge was to do it using polynomial in $\log n$ time.
Solution
If you look at the numbers of the form $a_k = [k \varphi]$ and *not* of the form $[k \varphi]$, you will notice a pattern.
The pattern is as follows:
If $a_k = [k \varphi]$ and $b_k = a_k + k$, then we have that $$\{a_1, a_2, \dots\} \cup \{b_1, b_2, \dots\} = \mathbb{N}$$
i.e, the numbers not of the form $[k \varphi]$, are precisely of the form $[k \varphi] + k$.
This observation can be proved using Beatty's theorem (and is not that difficult to prove).
Now, if you consider the numbers $\{1, 2, \dots, a_n\}$ then these can be split into two disjoint sets $\{a_1, a_2, \dots, a_n\}$ and $\{b_1, b_2, \dots, b_m\}$ for some $m$.
Thus we have that
$$1 + 2 + \dots + a_n = S_n + \sum_{k=1}^{m} b_m = S_n + S_m + m(m+1)/2$$
Thus
$$S_n = n(n+1)/2 - m(m+1)/2 - S_m$$
which is a recursive formula for $S_n$. It can be shown that $m = \theta(n)$, and thus this recursive formula gives us a polynomial in $\log n$ time algorithm to compute $S_n$.
All we need to do is compute $m$. I will leave that to you.
$$S_n = \sum_{k=1}^{n} [k \varphi]$$
where $\varphi$ is the golden ratio and $[x]$ is the integer part of $x$.
The challenge was to do it using polynomial in $\log n$ time.
Solution
If you look at the numbers of the form $a_k = [k \varphi]$ and *not* of the form $[k \varphi]$, you will notice a pattern.
The pattern is as follows:
If $a_k = [k \varphi]$ and $b_k = a_k + k$, then we have that $$\{a_1, a_2, \dots\} \cup \{b_1, b_2, \dots\} = \mathbb{N}$$
i.e, the numbers not of the form $[k \varphi]$, are precisely of the form $[k \varphi] + k$.
This observation can be proved using Beatty's theorem (and is not that difficult to prove).
Now, if you consider the numbers $\{1, 2, \dots, a_n\}$ then these can be split into two disjoint sets $\{a_1, a_2, \dots, a_n\}$ and $\{b_1, b_2, \dots, b_m\}$ for some $m$.
Thus we have that
$$1 + 2 + \dots + a_n = S_n + \sum_{k=1}^{m} b_m = S_n + S_m + m(m+1)/2$$
Thus
$$S_n = n(n+1)/2 - m(m+1)/2 - S_m$$
which is a recursive formula for $S_n$. It can be shown that $m = \theta(n)$, and thus this recursive formula gives us a polynomial in $\log n$ time algorithm to compute $S_n$.
All we need to do is compute $m$. I will leave that to you.
No comments:
Post a Comment