2
$\begingroup$

Given a set of natural numbers $S_1$ , $S$ and a number N .

Specification of sets are as follow .

$$S = \{1,\dots N\}$$ $$S_1\subset S \;and \;S_1=\{b_1,b_2,\dots,b_m\}$$

And $$S' = S\setminus S_1$$

Find the smallest natural n that can not be written as a sum of elements of S'.

Note: A number can't be used more than once .

e.g. if $S=\{1,2,3\}$ and $S_1=\{3\}$ then $S' = \{1,2\}$ we can't form $4$ using $S'$, so answer is $4$.

Can we design an algorithm to solve this problem useing the knowledge of set $S_1$ and N?

$\endgroup$
18
  • $\begingroup$ This looks like an algorithm problem. Doubt if there is a number-theoretic way... $\endgroup$
    – Aryabhata
    Commented Jan 6, 2015 at 12:55
  • $\begingroup$ Yes it's like an algorithmic problem.But some how we have to come up with the solution using number theory . $\endgroup$ Commented Jan 6, 2015 at 12:57
  • $\begingroup$ Your notations are quite confusing. I suppose you mean, $S=\{1,\dots,n\}$ and $S_1\subset S$ (which is absolutely not what you have written). $\endgroup$
    – Tom-Tom
    Commented Jan 6, 2015 at 12:59
  • $\begingroup$ Yes i mean that . $\endgroup$ Commented Jan 6, 2015 at 13:00
  • 1
    $\begingroup$ @5xum Sorry for confusion . Question is updated with more information . $\endgroup$ Commented Jan 6, 2015 at 13:34

2 Answers 2

1
$\begingroup$

A possible rather stupid way to do it is to compute the sum $M$ of all elements of $S_1$. Form an array $a$ (filled with zeroes) with the numbers from $1$ to $M-1$. Then compute all the possible sums of elements of $S_1$ (there are $2^N-1$ such sums where $N=\text{Card}\, S_1$, the number of elements of $S_1$) and for each result $i$, put the value $a_i$ to $1$. Once you've done it, the smallest value $i$ such that $a_i=0$ is the searched result.

There are many ways to improve this algorithm, but that's a start.

If you want to improve, use polynomials and compute the product $$ P(X)=\prod_{p\in S_1}(1+X^p)$$ The coefficient of $X^k$ in $P(X)$ is actually the number of ways to form $k$ as a sum of elements of $S_1$. So you just have to look for the smallest $k$ such that the coefficient of $X^k$ is zero. This technique does not improve efficiency.

$\endgroup$
0
$\begingroup$

EDIT: I just realized how simple this problem is. Here's the solution in Lua:

S={1,1,1,1,5,7,10,25,50,75,100,250,500,1000} table.sort(S)

x=1 for i=1,#S do if S[i]<=x then x=x+S[i] end end

print(x)

Starting at x=1, go in ascending order increasing x if the number is less than or equal to x, and stop when it isn't (or when they all are).

ex.given the set {1,1,1,1,5,9,12,31,50,100,300} 1 = 1 2 = 1+1 3 = 1+1+1 4 = 1+1+1+1 5 = 5 ... 8 = 5+1+1+1 9 = 9 ... 12 = 9+1+1 ... 30 = 12+9+5+1+1+1+1 31 = 31 ... 49 = 31+12+5+1 50 = 50 ... 100 = 50+31+12+5+1+1 ... 211 = 100+50+31+12+9+5+1+1+1+1 212 = X (smallest value which cannot be made)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .