Skip to main content
3 of 3
added 13 characters in body
advocateofnone
  • 3k
  • 1
  • 26
  • 44

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.

advocateofnone
  • 3k
  • 1
  • 26
  • 44