Page 1 of 1

sum of squared Beatty sequence

Posted: Thu Jul 15, 2021 7:00 pm
by marijan
Hello,

S(r, n)=sum(k=1 .. n) floor(r*k) is Beatty sequence.

S(sqrt(2), 10) sequence is 1, 2, 4, 5, 7, 8, 9, 11, 12, 14, and sum is 73.

I implemented this as a recursive function which has O(log n) complexity.

Is it possible to find sum of partitions where every element of sequence is
a square or another function of above elements. Square for every element gives 701.

I tried to use use n*(n + 1)*(2*n + 1)/6 instead of triangle formula, no success.

Re: sum of squared Beatty sequence

Posted: Tue Jul 20, 2021 4:07 am
by j123
It is possible, in fact there is a Project Euler problem that boils down to doing something of the sort you are asking about, so I'm loathe to provide a complete solution here. Most solutions in its thread use a generalization of the the recursion you've implemented, but there's another way too.

The sum of a Beatty sequence is the count of lattice points strictly inside the triangle T with sides y=0, x=n, and y=rx, or equivalently the count inside the convex hull C(r, n) of those lattice points (less the n+1 points on the x-axis). This convex hull C(r, n) is a polygon with O(log n) vertices, for the same reason there's an O(log n) algorithm for computing the sum. Then there is a general theory (by Barvinok and others) that says that the sum of any given polynomial P(x, y) over C(r, n) is then also computable in O(log n). In fact there is a pretty explicit algorithm, using the continued fraction expansion of r, for computing such things. Using an appropriate poiynomial will give the squared sum you want.

I hope it's not giving too much away that problem 401 can be thought of as calculating the sum of a polynomial over the lattice points in some large region -- my solution in the thread there gives some details.