Geek Answers Handbook

Can I check if a given number can be the sum of any arithmetic progression with n members in it?

Is it possible for a given number s to simply verify that there is any possible arithmetic progression containing n members and the sum of these n-members leads to s.

where the initial element and the difference AP should not be equal to zero.

eg:

s = 24 and n = 4

yes, possibly where the AP is 3 5 7 9.

Note. I just want to check if this is possible or not. No need to find the actual array. 0 <n <10 ^ 9 and 0 <s <10 ^ 18.

My attempt:

we know that the sum of AP is s = n (first + last) / 2;

therefore first + last = 2 * s / n;

2 * s / n must be an integer.

we also know that last = first + (n-1) diff;

so my expression becomes 2 * first + (n-1) diff = 2 * s / n;

first = (2 * s / n - (n-1) diff) / 2; and it must be an integer for a specific diff value.

this is my approach to this, but its temporal complexity is too great to cover 10 ^ 18.

Please, help.:)

+5
source share
3 answers

Case 1: a and d are real numbers

Using s for the sum, n for the number of members, a for the first term and d for the difference between the members, you get the result

2 * s / n = 2 * a + (n - 1) * d

It gives you one degree of freedom. Thus, you can see that you can always choose an infinite set of values ​​a and d that satisfy this result.

Case 2: a and d are integers

My result shows that if a and d bounded by integers , then decomposition is possible only if the left side of this equation is also an integer; i.e. 2 * s is a multiple of n . (In your case, 2 * s is 48, which is a multiple of 4. So yes, in this case there is an integral a and d ).

+3
source

Let a be the initial term of the progression and d its total difference. You want to solve the linear diophantine equation

 n * a + (n*(n-1)/2) * d = s

A solution will exist if and only if s is a multiple of gcd(n, n*(n-1)/2) .

If n is odd, gcd(n, n*(n-1)/2) = n * gcd(1, (n-1)/2) = n .

If n even, gcd(n, n*(n-1)/2) = (n/2) * gcd(2, n-1) = n/2 .

In any case, a solution exists if and only if 2 * s is a multiple of n .

+1
source

I think this is not possible in every case, but if you can provide some more data, then it is possible. because there are many possibilities for the same amount of AP. so in case you give some hint, maybe

0
source

More articles:


All Articles