# Sorting the number sequence

I have

• $4$ variables $n_1, n_2, n_3, n_4 \in \mathbb N$ that sum to $N$.

• $4$ positive real constants $c_1 < c_2 < c_3 < c_4$.

Given a particular tuple $(k_1,k_2,k_3,k_4)$, how do I find the partial sum of the ordered (w.r.t. the sum $c_1 n_1 + c_2 n_2 + c_3 n_3 + c_4 n_4$ in an increasing manner) sequence

$$\sum_{n}^{(k_1,k_2,k_3,k_4)} (c_1 n_1 + c_2 n_2 + c_3 n_3 + c_4 n_4)$$

from the minimum to the given $(k_1,k_2,k_3,k_4)$?

I think this problem involves some sorting algorithm. This should already be studied in some linear programming problem but I am just not aware of how to do this efficiently (e.g. using Python).

• What does the notation $\sum_{n}^{(k1,k2,k3,k4)} (c1n1+c2n2+c3n3+c4n4)$ mean? What are the variables, and what are their lower and upper bounds? Perhaps the sum is over $n=(n_1,n_2,n_3,n_4)$, but what are the lower and upper bounds for this sum? What do you mean by "the ordered sequence $\sum \cdots$"? It's hard for me to understand what you are asking. – D.W. Jul 25 '17 at 16:05
• @D.W. the summand is c1n1+c2n2+c3n3+c4n4, the lower bound is the min{c1n1+c2n2+c3n3+c4n4} and the upper bound is (k1,k2,k3,k4), the sum is starting from smallest possible (c1n1+c2n2+c3n3+c4n4) in an increasing manner, thus ordered. – Shadumu Jul 25 '17 at 20:18

There's a simple $O(N^3 \log N)$ algorithm, though you might be able to do much better. First, compute all $N^3$ quadruples, and the corresponding linear combinations $\sum_i c_i n_i$. Then sort them. Then find the location of the given quadruple. Then compute the running sum.