Generator Set Problem

[lord1319]

Hello. My teacher posted an interesting question for some extra credit:

In this project, you should write a code in c/c++ (in Linux) which solves the following problem and produces correct results.
For a natural number N, find a set of natural numbers in a way, that if you were only able to use subtraction
and summation, you could generate any natural number between 1 and N, by using each member of the
set at most one time. We call such a set a generator set of N.
Consider N=10. A possible generator set for this number could be GS = {1, 2, and 7}, because you can
produce any number from 1 to 10 using this numbers by applying -/+ operations:

So you want the lowest amount of numbers in the set, so ex:
1,2,3,4 is worse than 1,3,6
you also want the lowest maximum number so:
1,3,6 is better than 1,2,7.
My solution is to just half N and round up or down as needed, which works, but does not produce the lowest maximum number, for example for 30 mine produces
15,8,4,2,1 while 11,9,6,3,1 also works and is a better set.

Can someone set me on the right path to producing the lowest numbers possible? I am stumped. Thank you.

[dhayden]

First some notation. Let's say that if G is a generator set for N, then G(N,X) is the expression in G that generates X.

Here's a suggestion. If you have a generator set for N then I think you can make a generator set for 3N as follows
- For values X from 1 to N, use G(N,X)
- For values X from N to 2N, use 2N - G(N,X)
- For values from 2N to 3N, use 2N + G(N,X)

Unfortunately, I don't know if you can prove that this is a minimal set.

[Quillan13]

I'm currently working on this problem as well. I understand how you get 1,2,7 for 10 but can you explain what you do after you half N to find the numbers for the set. I don't see a fast way to check for this other than to run through every number and figure out which ones you need and dont need

[lord1319]

One solution, although not very fast, is to start with 6 and the numbers 1,2,3. To get the next number, add 1 to one of your current numbers. So for 7 you can use 1,2,4, for 8 and you can use 1,2,5, and so on. Just add 1 to the first number, check if the answer works. If it doesn't, try the next number. If none of them work, you need to add a fourth number in, which can be tricky. This becomes slow however because you constantly run the check to see if the set works.

[doug4]

Pardon my mathematical terminology. It's been a number of years since I wrote any formal proofs. Some of my logic may be a but fuzzy, but here goes.

EDIT: My algorithm doesn't work for v0 = 2. Back to the drawing board. I'm close, but no cigar.

A. Let A(x, y) = integer values {x,...,y}

B. Let G(V) = {g0,...gn} be the minimal set such that all values A{1, V} can be calculated using only elements g0 - gn and addition and subtraction.

C. Given G(V), determine the maximum set G obtained by adding a single element
G(3V + 1) = {G(V), (2V+1)}
A(1, V) obtained from G(V)
A(V+1, 2V) obtained from (2V+1) - G(V)
2V+1 obtained trivially
A(2V+2, 3V+1) obtained from (2V+1) + G(V)

========================================================================

Problem: Find G(x) for a given integer x (x >= 1)

Let G(x) = {G(v0), gn}

Step 1: Determine v0 such that the first terms of G(x) are G(v0)

v0 is the minimum value such that (3v0 + 1) >= x (from C)

v0 = ceil((x-1)/3)


Step 2: Now calculate the minimum value of gn, the last element of G(x)

Restating things
v0 is maximum value calculated from G(v0) (from B)

x = v0 + gn
gn = x - v0

We now have v0 and gn.

If gn > 1, go back to step 1, assigning v0 to x.