# Sum of Distinct Positive Integers Different from Sum of Any Combination of The Same Integers

Let $\|\vec{x}\|_1$ represent the sum of the components (the L1 norm) of $\vec{x}$. Define $$A_n = \{\vec{x}:\vec{x}\in\mathbb{\mathbb{N}}^n, x_i\ne x_j \textrm{ for } i\ne j,\|\vec{x}\|_1\notin B(\vec{x})\},$$ where $$B(\vec{x}) = \left\{\sum_{i=1}^{n} a_ix_i: (a_1,\ldots,a_n)\in\mathbb{Z}^{n}_{\ge 0}-(1, 1, \ldots, 1)\right\}.$$ Furthermore, let $$C_n=\{\vec{c}\in A_n:\|\vec{c}\|_1=\min_{A_n} \|\vec{a}\|_1\}.$$

Can we determine $C_n$?

Forgive me if my notation is off, this seems to be a bit of a complicated problem.

To explain in words, $A_n$ is the set of all vectors $\vec{x}$ with $n$ components where each component is a distinct positive integer satisfying the property that the sum of the components of each $\vec{x}$ cannot be formed by summing the components of any combination (with repetition) of the components of $\vec{x}$, excluding $\vec{x}$ itself, of course. Hence, $C_n$ is set of vectors in $A_n$ having the smallest L1 norm.

Through a brute force approach in Python, I found for $n=1, 2, 3, 4$:

$C_1 = \{(1)\}$

$C_2 = \{(2, 3)\}$

$C_3 = \{(4, 6, 7)\}$

$C_4 = \{(8, 12, 14, 15)\}$

And I think the pattern that emerges is clear. But can you mathematically prove that this pattern continues?

Here's the Python code, for reference: https://www.onlinegdb.com/Sk9-TaQ8Q

I do not have a full answer, but at the very least one can prove that the vector $\vec{v}_n\in \mathbb{N}^{n}$ with components $v_{i,n} = 2^{n}-2^{n - i}$ for $i=1, \ldots, n$ satisfies the condition. This is actually quite easy by induction. Let us consider $\vec{v}_{n+1}$ in $\mathbb{N}^{n+1}$ and suppose that $$\sum_{i=1}^{n+1} v_{i,n+1} = (n+1)\cdot 2^{n+1} - \sum_{i=1}^{n+1} 2^{n+1-i} = n\cdot2^{n+1} + 1 = \sum_{i=1}^{n+1} a_i v_{i,n+1}$$ for some integers $a_i\ge 0.$
Note that $\sum_{i=1}^{n+1} a_i \ge n+1,$ since otherwise the right-hand side of the above equation is at most $n\cdot v_{n+1} = n\cdot(2^{n+1}-1).$ Now subtract $2^{n}$ from each term on the LHS and from $(n+1)$ terms on the RHS to reduce to the case with $n$ components. If the RHS has extra terms, you can simply write them as $2^{n} + (v_{i,n+1} - 2^{n}) = 2\cdot v_{1,n} + v_{i-1, n}.$ In the case $i=1, v_{0,n} = 0.$ In any case, the induction hypothesis implies $a_i = 1$ for all $i.$
I want to add that for any such vector, the smallest component must be at least $2^{n-1}.$ This is because if any two subsets of the remaining $n-1$ component are congruent modulo $v_1,$ then the vector fails. Hence $v_1\ge 2^{n-1}.$