Summation involving floor of irrational numbers. I need to compute the following sum for large $N$, i.e. $N = 10^{16}$.
$$ S(N) = \sum_{x=2}^{x=N-1} \left(\sum_{y=x+1}^{y=min(N, \lfloor \phi \times x \rfloor)} x + y\right) $$
where $\phi = \frac{1 + \sqrt{5}}{2}$, $x$ and $y$ are positive integers.
My first step is to break the sum at $x = x_0$ such that $(x_0 \times \phi) \leq N$ and $((x_0 + 1) \times \phi) > N$. So, we now have two sums,
$$ S_1(N) = \sum_{x=2}^{x=x_0} \left(\sum_{y=x+1}^{y=\lfloor \phi \times x \rfloor} x + y\right) $$
$$ S_2(N) = \sum_{x=x_0+1}^{x=N-1} \left(\sum_{y=x+1}^{y=N} x + y\right) $$
Now, note that $S_2(N)$ has a closed form and can be computed very quickly. My question is,
is there a way to compute $S_1(N)$ quickly, any sub-linear time algorithm would be great.
Here are some values of $(N, S(N))$ for small values of $N$, $[(2,0),(3,5),(4,12),(5,21),(6,42),(7,67),(8,109),(9,157),(10,211),(11,289),(12,375)]$.
 A: 
I would like to know/learn how to compute such summations.

In this case, we can use $\phi$'s connection to Fibonacci recurrences, as well as the fact that $x+y$ is linear. Start with a plot of the summands:

Then, the problem is to find the (weighted) area. You've already noticed that the $\min(N,\cdot)$ limit is not interesting, so let's get rid of it. While we're at it, let's fill the triangle to the axis:

To find the total weight in this plot, split it recursively into smaller pieces. There is a Fibonacci-like recurrence:

(You could also derive the recurrence from the continued fraction representation $\phi = [1;1,1,\dots]$. It's not as picturesque though.)
It's not quite that simple, because these similar pieces have different weights $\sum_{x,y} x+y$. However, $x+y$ is linear, so when you shift a $k$-term piece by $(\Delta x, \Delta y)$, its weight changes by $k (\Delta x + \Delta y)$. Modulo this adjustment there are only $\mathcal{O}(\log N)$ distinct pieces, so $S(N)$ can be calculated in $\mathcal{O}(\log N)$ operations.
A: Here's a partial solution:
The best rational approximations to $\phi$ are ratios of successive Fibonacci numbers $\phi \approx F_{n+1} / F_n$.  Take the first Fibonacci number $F_n >= 2 x_0$.  We have $|\phi - F_{n+1} / F_n| < 1/ F_n^2 <= 1/2x_0 F_n$.
So $|\phi * x - x * F_{n+1} / F_n| < 1/2F_n$, and $\lfloor \phi * x \rfloor = \lfloor x * F_{n+1} / F_n \rfloor$.
We now have 
\begin{equation}
S_1(N) = \sum_{x=2}^{x_0} \big( \sum_{y=x+1}^{\lfloor x * F_{n+1} / F_n \rfloor } x+y \big)
\end{equation}
The inner sum can be expressed as a quasi-polynomial in $x$ with period $F_n$.  I suspect there is a nice closed form for sums of the form $\sum_{y=x+1}^{x + \lfloor x * p / q \rfloor } x+y$ with $p,q$ prime in terms of the Dirichlet characters mod $q$, but that's as far as I got.
