Which tuple of arithmetic progression sums does the given integer fall into?

Question

Suppose I have an arithmetic progression, e.g. 3,7,11,15,19,.... The sums of the first n elements form tuples of increasing size. E.g. the sums are:

• S(n=1)=3
• S(n=2)=10
• S(n=3)=21
• S(n=4)=36
• S(n=5)=55

So the tuples are:

• T(1)=[3;10)
• T(2)=[10;21)
• T(3)=[21;36)
• T(4)=[36;55)

Is it possible to find a formula, that would tell which tuple the integer i (which is greater than the first element=3) is falling into? E.g. for i=50 the formula should give 4.

Answer 1

In this case $S(n)=2n(n+1)-n=2n^2+n$.

Given $M$, you want to find a positive root of $2x^2+x-M=0$ and then take the floor.

This is $$x=\frac{-1+\sqrt{1+8M}}{4} = \frac{-1}{4} + \sqrt{\frac{1}{16}+\frac{M}{2}}$$

Not sure if there is a "clever" way to find the floor of this. You always get that the floor is "near" $\sqrt{M/2}$.

In general, given the arithmentic sequence $a,a+d,\dots,a+(n-1)d,\dots$ the sum of the first $n$ terms is:

$$S(n)=na + d\frac{n(n-1)}{2}$$

so you are seeking a positive root of:

$$dx^2+(2a-d)x -2M=0$$

So the formula is:

$$x=\frac{d-2a + \sqrt{(2a-d)^2+8Md}}{2d}=\frac{1}{2}-\frac{a}{d} + \sqrt{\left(\frac{a}{d}-\frac{1}{2}\right)^2+\frac{2M}{d}}$$

You can take the floor of that to get your $n$.

Not pretty, but it does the trick.

For $M$ somewhat large, you can start with a good upper bound of:

$$\frac{2M}{a-\frac{d}{2}+\sqrt{2Md}}$$

That estimate gives $\frac{100}{21}$ which is between $4$ and $5$, when $a=3,d=4,$ and $M=50.$

Answer 2

If you have the arithmetic progression $a,a+d,a+2d\dots$ then the sum of the first $n$ terms is given by Gaussian summation.

It is:

$\frac{(2a+(d-1)n)(n)}{2}=\frac{2an+(d-1)n^2}{2}$

Now, you want to to find the maximum $n$ so that $\frac{2an+(d-1)n^2}{2}<x$. I suggest you use binary search.

Here is a working code in c++:

#include <cstdio>
long long a,d,x,ub=1e8,lb=0,mid;
long long sum (long long n){
    return((2*a*n+(d-1)*n*n)/2);
}
int main(){
    scanf("%lld %lld %lld",&a,&d,&x);
    while(sum(ub-1)>=x){
        mid=(lb+ub)/2;
        if(sum(mid)>=x){
            ub=mid;
        }
        else{
            lb=mid;
        }
        if(sum(ub-1)>=x){
            ub--;
        }
    }
    printf("%lld\n",ub);
}