[Solved]: How to compute the sum of this series involving golden ratio, efficiently?

Problem Detail: 

Definitions

1. Let $\tau$ be a function on natural numbers defined as $\tau(n)=\lceil n*\phi^2\rceil$ where $n$ is some natural number and $\phi=\frac{1+\sqrt{5}}{2}$ is the golden ratio. This series can also be looked up here : A004957, with first few terms being $3,6,8,11,14...$ .
2. Let $t$ be the largest natural number such that $\tau(t) \le 10^{16}$.
3. Let $S_i$ for $1 \le i \le t$ be defined as $S_i=-(10^{16}-\tau(i)+1)*i+ 2*\sum_{j=\tau(i)}^{j=10^{16}} j $.

Problem

How can I compute the sum $(S_1+S_2+...S_t)$ % $7^{10}$ efficiently ? I tried thinking by matrix exponentiation, but can't come up with a method due to the form of the $\tau$ function.

PS: This question is my way of trying to solve the problem : stone game II.

Asked By : sashas

Answered By : sashas

As D.W. pointed out there should be some kind of recurrence involving the $\tau$ function. Turn's out there is, let us again look at the $\tau$ function series, the first few terms are

$$3,6,8,11,14,16,19,21.... \; \;(1)$$

Now let us look at the difference between consecutive terms of the series,

$$3,2,3,3,2,3,2..... \; \; (2)$$

Turns out sequence $(2)$ is the infinite fibonacci word ( again some sort of strong correspondence between golden ratio and fibonacci sequences ) made up of $2's$ and $3's$. This fibonacci sequence is as follows, the first two terms are

$a_0 = 3$ , and $a_1=3,2$ and for $n\ge 2$, $a_n=a_{n-1}.a_{n-2}$, where "." represents string concatenation. First few terms of the fibonacci word are

$$a_0=3$$ $$a_1=3,2$$ $$a_2=3,2,3$$ $$a_3=3,2,3,3,2$$

and so on. With this construction the summation I mentioned can be calculated very quickly. Also I did not make any use of the fact that modulo was taken by $7^{10}$. It would be interesting if this fact could be used somehow as D.W. suggested.

PS: I solved the question using the same formula in my question. Above I provide only a hint as coming from a non-math background I found the question really interesting and won't ruin it for others.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/57955

3.2K people like this

 Download Related Notes/Documents