# How to compute the sum of this series involving golden ratio, efficiently?

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.

• 1. Can you find a simple recurrence for $\tau(n)$? e.g., $\tau(n) = c_1 \tau(n-1) + c_2 \tau(n-2) + \dots + c_k \tau(n-k)$ for some small constant $k$. 2. Anytime someone asks you to compute something modulo $7^{10}$, you should be thinking: try Hensel lifting. In other words, try computing it modulo $7$, then computing it modulo $7^2$ (using your knowledge of its value modulo $7$), then computing it modulo $7^3$, and so on. Sometimes if you know it mod $7^k$ then computing it mod $7^{k+1}$ is surprisingly easy (due to linearity or somesuch). – D.W. May 29 '16 at 21:27
• 3. Have you tried looking up the sequence $S_1,S_2,S_3,S_4,\dots$ in OEIS? Or, more likely to succeed: looking up the sequence $S_t,S_{t-1},S_{t-2},S_{t-3},\dots$? You might just get lucky. – D.W. May 29 '16 at 21:28

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.