Which tuple of arithmetic progression sums does the given integer fall into? 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.
 A: 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.$
A: 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);
}

