### PROBLEM LINK:

**Author:** Gaoyuan Chen

**Editorialist:** Tiny Wong

### DIFFICULTY:

HARD.

### PREREQUISITES:

Beatty sequence,

Continued fractions.

### PROBLEM:

Given n \leq 10^{4000}, calculate the sum

where \mathrm{e} = 2.718\dots is Euler’s number.

### QUICK EXPLANATION:

Let S(n, \alpha) = \sum\limits_{k=1}^n \left\lfloor k \alpha \right\rfloor. If 1 < \alpha < 2, we can get that

where n' = \left\lfloor (\alpha-1)n \right\rfloor and \beta = \dfrac \alpha {\alpha-1}.

### EXPLANATION:

#1. Universal Solution

Let \alpha > 0 be an irrational number. Then the sequence B_\alpha = \{ \left\rfloor \alpha \right\rfloor, \left\rfloor 2\alpha \right\rfloor, \dots, \left\rfloor n\alpha \right\rfloor, \dots \} is a Beatty sequence, whose prefix sum is denoted as

If \alpha > 2, let \beta = \alpha-1, then

If \alpha < 1, let \beta = \alpha+1, then

Then we can assume that 1 < \alpha < 2.

Here is an important theorem for solving this problem.

**Theorem** (Rayleigh). Let \alpha and \beta be two irrational numbers with \dfrac 1 \alpha + \dfrac 1 \beta = 1, then B_\alpha and B_\beta partition the set of positive numbers, i.e. B_\alpha \cup B_\beta = \mathbb{N}^+ and B_\alpha \cap B_\beta = \emptyset.

By Rayleigh Theorem, if 1 < \alpha < 2, let \beta = \dfrac \alpha {\alpha - 1}, m = \left\lfloor{n \alpha}\right\rfloor and n' = \left\lfloor{\dfrac m \beta}\right\rfloor, then

Note that

Then

If 1 < \alpha < 2, n' = \left\lfloor{(\alpha-1)n}\right\rfloor < (\alpha-1)n < n, we can calculate S(n, \alpha) by (*).

#2. Continued Fractions

A positive irrational number \alpha can be written as a continued fraction

where \{ a_0, a_1, a_2, \dots \} is an infinite sequence and a_1, a_2, \dots \in \mathbb{N}^+. We can use the shorthand

Note that the integer part of a is [\alpha] = a_0, and the fraction part is

And

In the former analysis, we assume that 1 < \alpha < 2, as a result a_0 = 1, and

#3. Complexity Analysis

Now we describe the algorithm formally. Let \alpha^{(0)} = \alpha and n^{(0)} = n. Now for each k, consider

the calculation of S(n^{(k)}, \alpha^{(k)}). Let \alpha^{(k)} = [a_0^{(k)}; a_1^{(k)}, a_2^{(k)}, a_3^{(k)}, \dots].

Let $n^{(k+1)} = \left\lfloor{ {\alpha^{(k)}} n^{(k)}}\right\rfloor$，$\beta^{(k)} = 1+\dfrac 1 {{\alpha^{(k)}}}, by (*)$,

Notice that

And then

If we let \alpha^{(k+1)} = \beta^{(k)}-a_1^{(k)} = [1; a_2^{(k)}, a_3^{(k)}, \dots], then a_1^{(k+1)} = a_2^{(k)} = \dots = a_{k+1}^{(0)}, and we get that

Note that

and that

Let \gamma^{(k)} = \dfrac 1 {\{\alpha^{(k)}\}} = [a_1^{(k)}; a_2^{(k)}, a_3^{(k)}, \dots] = [a_{k+1}^{(0)}; a_{k+2}^{(0)}, a_{k+3}^{(0)}, \dots], then

Note that

i.e.

Here we have \gamma^{(1)} \gamma^{(0)} = a_1^{(0)} \gamma^{(1)} + 1. We may assume that \gamma^{(k)} \gamma^{(k-1)} \dots \gamma^{(0)} = p^{(k)} \gamma^{(k)} + q^{(k)}, and then

As a result, p^{(k+1)} = p^{(k)}a_{k+1}^{(0)}+q^{(k)} and q^{(k+1)} = p^{(k)}, and then

Note that p^{(0)} = 1 and p^{(1)} = a_1^{(0)} \geq 1, then p^{(k)} \geq f_k, where \{ f_k \} is the Fibonacci sequence, which is f_0 = f_1 = 1, and f_k = f_{k-1}+f_{k-2} for all $k \geq 2$。

Again we have

Then

where \phi = \dfrac {1+\sqrt5} 2.

As a result, the number of iterations of (*) is $O(\log n)$。

#4. Details

In practice, we need only two values, which are n^{(k)} and \{ \alpha^{(k)} \} and can be calculate by the followings.

**Algorithm** 1. Calculate all floating numbers after dealing the errors.

**Algorithm** 2. Use continued fractions instead of painful floatings.

An irration number \alpha can be approximated by a sequence of continued fractions

whose each term is an approximate representaion of \alpha and the precision is increasing.

Suppose the k-th term of the above sequence is \dfrac {P_k} {Q_k}, then

What we are facing is to calculate n^{(k+1)} = \left\lfloor{ \{ \alpha^{(k)} \} n^{(k)} }\right\rfloor. If \{ \alpha^{(k)} \} \approx \dfrac P Q with Q > n, then we can just calculate it forward

No matter which algorithm you choose, the overall time complexity is O(\log^2 n \log \log n). That is because O(\log n) for iterations, O(\log n \log \log n) for big integer multiplications and divisions (More precisely, multiplication is O(\log n) and division is O(\log n \log \log n)).

### ALTERNATIVE SOLUTION:

There may be other ways to solve the problem, please share!

### EDITORIALIST’S SOLUTIONS:

Editorialist’s solution can be found here.