I need a way of constructing a finite series with N elements, such that:
element 1 has the value A
element N has the value B
the sum of elements 1 through N is Z
Obviously, I understand that this requires A + B < Z.
Can someone help me out?
I need a way of constructing a finite series with N elements, such that:
element 1 has the value A
element N has the value B
the sum of elements 1 through N is Z
Obviously, I understand that this requires A + B < Z.
Can someone help me out?
Presumably there is more to the problem than this, as this is really simple.
edit: sorry, posted early. Given A, B, N, and Z, such that A+B<Z, then your sequence is just A, B, 0, 0, …, Z-(A+B).
Do you mean A, Z-(A+B), 0, …, 0, B?
Almost certainly.
Okay, you’re right, I guess that was under-specified.
I would also like to minimize the largest difference between any two adjacent elements in the series - i.e. minimize(max_i(abs(N_i - N_i-1))).
Basically, I would like the N-element series to “smoothly” progress from A to B, while summing to Z.
Make it an arithmetic series, and use the formulas on that page to figure out the common difference.
By “progress” do you mean a monotonically nondecreasing series from A to B. If that’s the case, you need more conditions on N and Z. Otherwise the problem can be infeasible. Regardless, this is not as trivial a problem as it seems to be. But first you need to better specify the conditions.
It does not need to be non-decreasing - B could be smaller than A.
I do not have any more interesting conditions on N and Z. N is an integer. N and Z are both positive, as are A and B. Each element in the series must be positive as well.
It is trivial to construct a series like this that satisfies all but one requirement of the problem:
A, (Z-B-A)/(N-2), (Z-B-A)/(N-2), …, B
Then the sum is A + B + (N-2) * (Z-B-A)/(N-2) = A + B + Z - B - A = Z - and as long as A + B < Z, it works. However, I am at a loss as to how to achieve the minimax criteria - minimizing the largest difference between any two adjacent elements in the series.
Must each element be an integer? If not you can make each difference equal and still satisfy the requirement by using an arithmetic progression. This assumes that you can “fit” the required number of elements into the sequence. (E.g., you can’t start at 5 and stop at 10 using 3 more elements (5 total) and make the sequence less than 30 obviously.)
If each element must be an integer I’d start with an arithmetic sequence and then start rounding. That will probably get you the best solution.
In general if you want integers, this is an integer programing problem.
You won’t get a smooth answer. I suspect you’ll have a piecewise linear solution as a function of Z. I’ll assume B > A in the following:
If Z = A+B, obviously all the other values are 0, and max(difference) is B. If Z <= 2B, make element N-1 (the element before B) be Z - (A+B). In the case Z=2B, max(difference) = A. Then, you need to let elements 2 and N-1 both increase, to reduce the maximum difference below A. I think it will progress like this, with a lot of different solutions, each covering a small range of values of Z.
I think you’re asking for the infinite series formula that says the sum of an infinite series where the next element is the current element times a factor is
a / (1-r)
where a is the first element, and r is that multiplier.
For instance, 1 + 1/2 + 1/4 + 1/8 + 1/16 + 1/32 +… converges at 2.
In that case, the first element is 1, and the multiplier is .5.
1 / (1-.5) = 2.
What about something where the i-th element is given by:
f(i) = A + [(i - 1)/(N - 1)][sup]C[/sup] (B - A)
where C > 0
This satisfies:
f(1) = A
f(N) = B
and f(x) is a smooth function.
You could adjust the value of C to give the correct sum Z, at least if Z is between (N-1)A + B and A + (N-1) B.
OK, as stated it’s not a trivial problem. A simple arithmetic series won’t work because the sum and end point are prespecified. Besides, there’s the criterion of minimizing the max difference between consequence sequence elements. It is indeed a mathematical programming problem, but not linear or integer programming. To get a true optimal solution I believe the right technique is dynamic programming because of the sequential aspect of the problem.
**bup’s **infinite series is clearly off-track. tim314’s function is nice but does not work for general Z and ignores the optimization criterion.
Yeah, I glossed over the “minimize the difference between adjacent elements.”
But on re-reading post #5, it’s not totally clear to me if the OP really wants this, or if he just felt this was necessary to make things “smooth” (which it isn’t really).
Perhaps Absolute can clarify if he really wants this, or if any smooth function (such as a polynomial) will do.
Edit: Nevermind, looks like he reiterated the same condition in post #8, so it must be important. I agree that it doesn’t seem like a trivial problem.
Still, my answer is going to be much closer to minimizing the difference between adjacent points than the one given in post #8.
Doesn’t any series whatsoever meet the original criteria?
Well, it needs to have N elements, start with A, end with B, and sum up to Z, where N, A, B, and Z are particular values. Every series accomplishes this for some values of N, A, B, and Z, but the question is, given particular values of N, A, B, and Z, construct a corresponding series.
Granted, it’s still very easy, as demonstrated above, which is why the OP should be more specific about what exactly it is they’re doing. There was the clarification about minimizing the maximum distance between adjacent elements, but, as tim314 says, it’s not clear if this is really a fundamental consideration for the OP or just one hastily added, possibly spurious formalization of their actual concerns.
Given the values A and B, and calling Z the area underneath the function f(x) from x = 0 to x = N such that f(1) = A, f(N) = B, can you not construct a quadradic function f(x) that approximates the desired series for all integer x in the range [1, N]?
Let Z[sub]0[/sub] = (A+B)/2 * N
For Z = Z[sub]0[/sub], you get the minimum possible maximum difference, (B-A)/(N-1). In this case, all the values lie on a straight line between the two end values. If Z > Z[sub]0[/sub], the values of the sequence will vary linearly from A to some maximum value, then vary linearly back to B. If Z < Z[sub]0[/sub], the values of the sequence will vary linearly from A to some minimum value, then linearly back to B, unless that minum value would be less than zero. In that case, the values vary linearly from A down to zero, are zero for a number of points, then go linearly up to B.
This is to build a computational grid in a dynamics calculation. The cells at material boundaries must have the same mass in both materials (that’s where the A and B constraints come from), and each material is represented with a certain number of cells N (determined by accuracy requirements inside the material), spanning a width of Z meters.
The “minimize the maximum difference” criteria does not need to be met absolutely perfectly, but the closer the mass of adjacent cells, the better the simulation will perform. An approximation is adequate, but not ideal.
Most simulations of this type require the user to deal with all this crap himself to get the zoning set up correctly - this simulation is specialized enough that I should be able to automate the process, assuming I can figure out a reasonable way to solve this little problem…