[News]

News: Welcome to The Oktave Forum.

[sanket]

sanket

sanket

Show sanket's last posts.

Show general stats for sanket.

• 
• Global Moderator
• Full Member
• Karma: 4
• Posts: 104

I thought of the following problem today and found a rather interesting solution. Apologies if the problem and/or solution are already well known.

As you would know, a partition of a number is a way of expressing the number in terms of a sum of positive numbers. Ex: Partitions of 4 are 1+1+1+1, 2+2, 3+1, 2+1+1.

Now, given a number 'n', find a partition set 'Pmin' such that all numbers 1 through n can be constructed using the set of numbers in Pmin and the operators + and -. For example, when n = 10, Pmin = {1, 3, 6} => [1, 3-1, 3, 3+1, 6-1, 6, 6+1, 6+3-1, 6+3, 6+3+1]

(1) Can you find a minimal covering partition for every n?
(2) If yes, give a general expression with explanation
(3) Also, a general expression for Pmin (Update: I mean an expression for the size of Pmin)
(4) Is there a unique Pmin for a given n?

I also have an application in mind based on this which I shall talk about later.

[sri]

sri

sri

Show sri's last posts.

Show general stats for sri.

• 
• Administrator
• Sr. Member
• Karma: 7
• Posts: 264

Can you use a number multiple times in an expression: (say 5 = 3+1+1 instead of 3+2)?

I'm interested to know the application you have in mind as well.

[mandar]

mandar

mandar

Show mandar's last posts.

Show general stats for mandar.

• 
• Global Moderator
• Newbie
• Karma: 2
• Posts: 36

Can you use a number multiple times in an expression: (say 5 = 3+1+1 instead of 3+2)?

I guess not. If that's allowed, then Pmin always consists of just one number -- 1.

[sri]

sri

sri

Show sri's last posts.

Show general stats for sri.

• 
• Administrator
• Sr. Member
• Karma: 7
• Posts: 264

Not if the 'min' in Pmin means that the expressions should be minimal as well..

In any case, assuming the above contention, here is a first cut solution.

If n is a power of 2, i.e. if n = 2^k, then all the numbers from 2⁰ ... 2^k-1 will form P_min.

Generalizing on this a little, if n can be written as b^k, then think of n as the number 1 followed by k 0s in base b notation. Then all numbers of the form m0000.. in base b, where m = 1..b and number of 0s between 0 to k-1 would form the P_min.

(Not too sure about the generalization step though. And since this involves only addition, it is more like an upper bound for P_min.)

[mandar]

mandar

mandar

Show mandar's last posts.

Show general stats for mandar.

• 
• Global Moderator
• Newbie
• Karma: 2
• Posts: 36

[Update:]

(4) Is there a unique Pmin for a given n?

No.

For example, let n=3

Pmin={1, 2} => [1, 2, 1+2]

Pmin={1, 3} => [1, 3-1, 3]

Update:

Another example of multiple Pmins for a number. Take the example n=10 itself. One of the Pmins is {1, 3, 6}. Another is {1, 2, 7}.

{1, 2, 7} => [1, 2, 1+2, 7-2-1, 7-2, 7-2+1, 7, 7+1, 7+2, 7+2+1]

[sanket]

sanket

sanket

Show sanket's last posts.

Show general stats for sanket.

• 
• Global Moderator
• Full Member
• Karma: 4
• Posts: 104

Sri said:

Can you use a number multiple times in an expression: (say 5 = 3+1+1 instead of 3+2)?

Yes, but each of the repeated entries should be counted. So, the size of Pmin above is 3 and not 2.

Mandar said:

I guess not. If that's allowed, then Pmin always consists of just one number -- 1.

This is not feasible as a result of the above constraint.

[sanket]

sanket

sanket

Show sanket's last posts.

Show general stats for sanket.

• 
• Global Moderator
• Full Member
• Karma: 4
• Posts: 104

Mandar said:

For example, let n=3

Pmin={1, 2} => [1, 2, 1+2]

Pmin={1, 3} => [1, 3-1, 3]

When n = 3, Pmin = {1, 3} is not a partition (1 + 3 = 4)

But you are right on the other one.

[sanket]

sanket

sanket

Show sanket's last posts.

Show general stats for sanket.

• 
• Global Moderator
• Full Member
• Karma: 4
• Posts: 104

Also, regarding the following...

Can you use a number multiple times in an expression: (say 5 = 3+1+1 instead of 3+2)

You cannot guarantee a covering partition for a given n unless this is allowed. The first example is of course 5.
---

Looking at the problem again, I feel what I found may not be the only solution, or even the best solution (in terms of achieving the minimal) for that matter. Perhaps it is a simple/convenient way. It's interesting though.

[mandar]

mandar

mandar

Show mandar's last posts.

Show general stats for mandar.

• 
• Global Moderator
• Newbie
• Karma: 2
• Posts: 36

For example, let n=3

Pmin={1, 2} => [1, 2, 1+2]

Pmin={1, 3} => [1, 3-1, 3]

When n = 3, Pmin = {1, 3} is not a partition (1 + 3 = 4)

Oh... Didn't realize that. Thanks.

I had been making this mistake the whole time. I'll have to rethink now.

[sanket]

sanket

sanket

Show sanket's last posts.

Show general stats for sanket.

• 
• Global Moderator
• Full Member
• Karma: 4
• Posts: 104

One more clarification lest there is some ambiguity about the term 'minimal'. When I say minimal, I am referring only to the cardinality of the set Pmin and not to the members of Pmin.

[sanket]

sanket

sanket

Show sanket's last posts.

Show general stats for sanket.

• 
• Global Moderator
• Full Member
• Karma: 4
• Posts: 104

Sri said:

I'm interested to know the application you have in mind as well.

Ok, I'll briefly explain the application. These are rough ideas still. The application is a network design cum routing algorithm. The numbers 1 through n are labels of nodes in a network. And the set Pmin is a "skip-list" that the nodes use to connect to a set of other nodes. So, "constructing every number up to n using elements of Pmin and the operators + and -" would mean the ability for every node to reach every other node by using only the skip-list (and + and -). (Of course, you can use an element of Pmin only once when constructing a number. And repeated elements are considered to be distinct.)

Now, this topology is a circular skip-list because every Pmin has 1 as one of its elements (a conjecture, but seems to hold); every node connects to a neighbour. (So, the + and - are modulo operators.) Let us assume undirected edges. Apart from connecting to a "successor", every node uses the other elements in Pmin as skips to connect to a bunch of other nodes. If the size of Pmin is 'k', then every node will have a maximum degree of 2k.

My conjecture right now is that the upper bound on the diameter of a network constructed using this idea is k, the size of Pmin. It seems to be working for the small networks that I tried. Further, I seem to know how to get Pmin for an n and also the relation between n and k. But let me wait for some more replies (and also, possibly, some refutations.)

[Nirav]

Nirav

Nirav

Show Nirav's last posts.

Show general stats for Nirav.

• 
• Newbie
• Karma: 2
• Posts: 6

Let me put it this way.. If we are allowed to use +/-, with what minimal set we can generate sequence of numbers, i.e. 1,2,3,4,5...

Say, at any point of time, there are p numbers in Pmin and we can generate upto N numbers using these Pmin, i.e, from 1,2,.. through N. Then the next number we should include in Pmin should be 2N+1. Suppose we have got a set of expressions which are generating 1 through N for us using Pmin. Then, last expression in this set would have given us N. So, subtracting that expression from 2N+1 would give us N+1, subtracting second last expression from 2N+1 would give us N+2 and so on we can reach to 2N by subtracting the first expression (essentially that would be 1) from 2N+1. 2N+1 it self is the next number. Now, adding expressions from the set in original order (which had given us 1 through N) will give us numbers from 2N+2 through 3N+1. And this can be repeated again with N = 3N+1, add 2(3N+1)+1 to Pmin and generate upto 3(3N+1)+1.

e.g.
to generate 1 we need 1. (No way out)
Now, Pmin = {1} & N = 1
We can add 2N+1 = 3 to Pmin and generate numbers upto 3N+1 = 4
Pmin = {1,3} => 1,3-1,3,3+1

Now Pmin = {1,3} & N = 4
We can add 2N+1 = 9 to Pmin and generate numbers upto 3N+1 = 13
Pmin = {1,3,9} => 1,3-1,3,3+1 , 9-(3+1),9-(3),9-(3-1),9-(1), 9 ,9+(1),9+(3-1),9+(3),9+(3+1)

Finally, one assertion....
This is the best way to generate sequence of numbers as,
1. All the numbers are generated
2. No number could have been generated in any other way.

[Nirav]

Nirav

Nirav

Show Nirav's last posts.

Show general stats for Nirav.

• 
• Newbie
• Karma: 2
• Posts: 6

Damn... Why did I think in such a complicated manner... 

It's turning out to be the series 3ⁿ

Pmin = {1,3,9,27,81...} and max number that can be generated would be simply sum of all the elements of Pmin.

[sanket]

sanket

sanket

Show sanket's last posts.

Show general stats for sanket.

• 
• Global Moderator
• Full Member
• Karma: 4
• Posts: 104

t's turning out to be the series 3n

Pmin = {1,3,9,27,81...} and max number that can be generated would be simply sum of all the elements of Pmin.

That's right! For a given n, the k elements of Pmin are, P1 = 3⁰, P2 = 3¹, ..., Pk = n - summation(P1 through Pk-1) (Or Pk = 3^k-1, if n is the biggest number for a given k).

So, the biggest number that can be covered for a given k, n = 3⁰ + ... + 3^k-1

And the size of Pmin for any n is, k = \ceil(log3 n) or \ceil(log3 n) + 1 [That is, log of n to the base 3]

[sri]

sri

sri

Show sri's last posts.

Show general stats for sri.

• 
• Administrator
• Sr. Member
• Karma: 7
• Posts: 264

3ⁿ series as the answer is interesting! But is it possible to explain this P_min property of the 3^x series in itself?

So, "constructing every number up to n using elements of Pmin and the operators + and -" would mean the ability for every node to reach every other node by using only the skip-list (and + and -). (Of course, you can use an element of Pmin only once when constructing a number. And repeated elements are considered to be distinct.)

Am afraid I don't get this either. What are '+' and '-' in terms of network operations?