4
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$
    – D.W. ♦
    Commented May 29, 2016 at 21:27
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Commented May 29, 2016 at 21:28

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.