- All Contests
- ProjectEuler+
- Project Euler #103: Special subset sums: optimum

# Project Euler #103: Special subset sums: optimum

# Project Euler #103: Special subset sums: optimum

_{This problem is a programming version of Problem 103 from projecteuler.net}

Let represent the sum of elements in set of size . We shall call it a special sum set if for any two non-empty disjoint subsets, and , the following properties are true:

i. ; that is, sums of subsets cannot be equal.

ii. If contains more elements than then .

If is minimised for a given , we shall call it an optimum special sum set. The first five optimum special sum sets are given below.

It *seems* that for a given optimum set, , the next optimum set is of the form , where is the "middle" element on the previous row.

By applying this "rule" we would expect the optimum set for to be , with S(A) = 117. However, this is not the optimum set, as we have merely applied an algorithm to provide a near optimum set. The optimum set for is , with .

Let's call the sets obtained by the algorithm above continuously the near-optimal sets. What is the near-optimal set of the size ?

**Input Format**

The only line containing the number where

**Output Format**

The only line containing numbers separated by spaces which are the members of the set in ascending order. As the numbers could be huge output them modulo .

**Sample Input**

```
6
```

**Sample Output**

```
11 17 20 22 23 24
```