Subset problem

ClifDavis

For n>0, a(1)+...+a(n) <a(n+1)+a(n+2). For n=1 this is true as a(1)< a(1+1)+a(1+2) or another words 1<2+3. This is another case where a(1)+...+a(n) is intended to show one term when n=1. I apologize for not using summation notation and can see that I'm going to have to learn MathXML.

For n>1 then n+2>3 and so a(1)+...+a(n-1)<a(a+2). But since the a(i) are strictly increasing, a(n)<a(n+1). All of which means a(1)+...+a(n-1)+a(n)<a(n+1). And so it's true for all n>0,

ClifDavis

Let Sn={a(1),...,a(n)} for any n>0. How do we characterize the subsets of Sn that add up to a(n)? Can we get a subset of Sn for any n, such that the elements of the subset add up to a(n) but the elements cannot be derived from the recurrence relationship and a(3)=a(2)+a(1) [substituting a(2)+a(1) for a(3)]?

Let i be the smallest integer such that Si has a subset where all the elements of the subset add up to a(n) but the set is not {a(n)} and cannot be derived from {a(n)} by repeated application of the recurrence relationship [that for n>3, a(n-3)+a(n-1)=a(n)] and the fact that a(1)+a(2)=a(3). Then i<6.

Assume that i>5 and i is the smallest integer so that there is a subset S'i of Si such that the elements of S'i add up to a(n), but S'i is not {a(n)} and cannot be derived from {a(n)} with repeated applications of the recurrence relationship and a(1)+a(2)=a(3).

(1) It is not the case that a(n) is an element of S'i.
If a(n) were an element then either a(n) is the only element and S'i={a(n)} contrary to assumption or there are other elements a(r1),...,a(rj), but each of the elements of Si is positive and so a(r1)+...+a(r2) >0 and adding a(n) to both sides of the inequality give us a(r1)+...a(rj)+a(n)>a(n) contrary to the assumption that the elements add up to a(n).

(2) At least one of a(i-1) and a(i-2) is an element of S'i.
Since i>5 then a(i-1) and a(i-2) exist. Assume that neither a(i-1) nor a(i-2) is in S'i. But since a(i) is not in S'i, we see that all the elements of S'i are in S(i-3). (S(i-3) exists since i>5>3.) But even if all the elements of S(i-3) were added up, a(1)+...+a(i-3), since i>3 a(1)+...+a(i-3)<a(i) and so as the elements of S(i-3) are all positive, the elements of S'i cannot add up to a(i). Therefor at least one of a(i-1) or a(i-2) is an element of S'i.

(3) a(i-1) and a(i-2) are not both elements of S'i.
Since i>5, i>3 and so a(i)=a(i-1)+a(i-3). Since i>3, i-2>1 and so a(i-3)<a(i-2). Or the same thing, a(i-2)>a(i-3). Adding a(i-1) to both sides give us a(i-1)+a(i-2)>a(i-1)+a(i-3)=a(i). Since a(i-1) and a(i-2) add up to more than a(i) and all elements of S'i must be positive, if both a(i-1) and a(i-2) were elements of S'i then the sum of its elements must be more than a(i) contrary to assumption. Therefor a(i-1) and a(i-2) are not both elements of S'i.

(4) S'i is not {a(i-3),a(i-1)}.
While this would add up to a(i), it can be derived from {a(i)} with a single application of the recurrence relationship, contrary to assumption.

(5) a(i-1) is not in S'i.
Assume a(i-1) is in S'i and a(i-2) is not. Then as a(i-1)<a(i), it must be the case that there are other elements of S'i, a(r1),...,a(rj) such that a(r1)+...+a(rj)+a(i-1)=a(i). But a(i)=a(i-1)+a(i-3) so a(r1)+...+a(rj)+a(i-1)=a(i-1)+a(i-3) and subtracting a(i-1) from both sides,a(r1)+...+a(rj)=a(i-3). Since neither a(i-2) nor a(i) are in S'i , they're also not in {a(r1),...,a(rj)} and so {a(r1),...,a(rj)} is a subset of S(i-3)={a(1),...,a(i-3)}. Notably it's a subset of S(i-3) whose elements sum to a(i-3). Furthermore {a(r1),...,a(rj)} cannot be derived from {a(i-3)} by the use of the recurrence relationship and the substitution of a(2)+a(1) for a(3), since if it could then {a(r1),...,a(rj),a(i-1)} could be derived in the same way from {a(i-3),a(i-1)}. But S'i={a(r1),...,a(rj),a(i-1)} and {a(i-3),a(i-1)} can be derived from {a(i)} using the recurrence relationship, and so S'i could be derived from {a(i)} contrary to our definition of S'i. So, i-3<i and S(i-3) has a subset {a(r1),...,a(rj)} which cannot be derived from {a(i-3)} using the recurrence relation and possibly substituting a(2)+a(1) for a(3). But this contradicts our assumption that i is the smallest integer with that property, so if we are to preserve that assumption we must conclude that in fact a(i-1) is not in S'i.

(6) a(i-2) is in S'i.
This is straightforward. By (2) a(i-1) or a(i-2) is in S'i. By (5), a(i-1) is not in S'i. And so a(i-2) is in S'i.

(7) {a(i-4),a(i-3),a(i-2)} is not S'i.
Since i>5 a(i-4),a(i-3),and a(i-2) all exist and {a(i-4),a(i-3),a(i-2)} is a subset of Si. It's elements do add up to a(i) [see the derivation that follows immediately]. However from {a(i)} we can derive {a(i-3),a(i-1)} by applying the recurrence relationship to a(i), and then by applying it to a(i-1), we get {a(i-4),a(i-3),a(i-2)} and since it is derivable from {a(i)} it cannot be S'i.

(8) Both a(i-4) and a(i-3) cannot be in S'i.
By (6), a(i-2) is in S'i. If a(i-3) and a(i-4) are as well then either there are no additional elements in S'i which contradicts (7) or there are and since they are positive, the elements of S'i will add up to more than a(i-4)+a(i-3)+a(i-2) = a(i), contrary to the definition of S'i.

(9) a(i-4) and a(i-3) cannot both be absent from S'i.
At this point we know from (1) that a(i) cannot be in S'i. We know from (5) that a(i-1) cannot be in S'i. We know from (6) that a(i-2) is in S'(i). Assume that a(i-4) and a(i-3) are both absent from S'i. Since S'i is a subset of Si the the largest value that S'i could sum to under our assumptions is a(1)+...a(i-5)+a(i-2). But i>5 and so i-3>2 and so a(1)+...a(i-5)<a(i-4)+a(i-3). Adding a(i-2) to both sides we see that a(1)+...a(i-5)+a(i-2)<a(i-4)+a(i-3)+a(i-2)=a(i) and the elements of S'i cannot add up to a(i). But this violates our definition of S'i and so either a(i-4) or a(i-3) must be an element of S'i.

(10) a(i-4) is not an element of S'i.
Assume a(i-4) is in S'i and a(i-3) is not. Then it must be the case that there are other elements of S'i, a(r1),...,a(rj) such that a(r1)+...+a(rj)+a(i-4)+a(i-2)=a(i). But a(i)=a(i-4)+a(i-3)+a(i-2) so a(r1)+...+a(rj)+a(i-4)+a(i-2)=a(i-4)+a(i-3)+a(i-2) or subtracting a(i-4)+a(i-2) from both sides,a(r1)+...+a(rj)=a(i-3). Since neither a(i-2) nor a(i) are in S'i , their also not in {a(r1),...,a(rj)} and so {a(r1),...,a(rj)} is a subset of S(i-3). Once again it's a subset of S(i-3) whose elements sum to a(i-3). Furthermore {a(r1),...,a(rj)} cannot be derived from {a(i-3)} by the use of the recurrence relationship (and/or a(3)=a(2)+a(1)) since if it could then {a(r1),...,a(rj),a(i-1)} could be derived in the same way from {a(i-3),a(i-1)}. But S'i={a(r1),...,a(rj),a(i-1)} and {a(i-3),a(i-1)} can be derived from {a(i)} using the recurrence relationship, and so S'i could be derived from {a(i)} contrary to our definition of S'i. So, i-3<i and S(i-3) has a subset {a(r1),...,a(rj)} which cannot be derived from {a(i-3)} using the recurrence relation and a(3)=a(2)+a(1). But this contradicts our assumption that i is the smallest integer with that property, so if we are to preserve that assumption we must conclude that in fact a(i-4) is not in S'i.

(11) The big contradiction. a(i-3) cannot be an element of S'i either.
Assume a(i-3) is in S'i and a(i-4) is not. Then as we also know a(i-2) is in S'i and a(i-1) and a(i) are not, there must be other elements of S'I, a(r1),...,a(rj) such that a(r1)+...+a(rj)+a(i-3)+a(i-2)=a(i). But a(i)=a(i-4)+a(i-3)+a(i-2) so a(r1)+...+a(rj)+a(i-3)+a(i-2)=a(i-4)+a(i-3)+a(i-2). This time we subtract a(i-3)+a(i-2) from both sides to obtain a(r1)+...+a(rj)=a(i-4). The elements on the left side of the equation all came from S'i and since they were not a(i-3) or a(i-2) and could not be a(i-1) and a(i) because those elements weren't in S'i then {a(r1),...,a(rj)} is a subset of S(i-4) which has elements that add to a(i-4). {a(r1),...,a(rj)} cannot be derived from {a(i-4)} by the use of the recurrence relationship and the substitution of a(1)+a(2) for a(3) since if it could then S'i={a(r1),...a(rj),a(i-3),a(i-2)} could be similarly derived from {a(i-4),a(i-3),a(i-2)} which can be derived from {a(i-3),a(i-1)} by the recurrence relationship and can in turn be derived from {a(i)} by the same relationship. This would violate our definition of S'i and so no such derivation of {a(r1),...,a(rj)} is possible. But now since i-4<i, we have a violation of our assumption that i is the smallest such value and so our assumption that a(i-3) is in S'i must be wrong.

(12) The big finish.
We assumed that i was the smallest integer for which there was a subset, S'i of Si, such that the elements of S'i added up to a(i) but S'i was distinct from {a(i)} and could not be derived from {a(i)} using some combination of the recurrence relationship a(n-3)+a(n-1)=a(n) for n>3 and a(3)=a(1)+a(2) and that i>5.
We deduced that:
(8) a(i-4) and a(i-3) cannot both be in S'i.
(9) Either a(i-4) or a(i-3) must be an element of S'i.
(10) a(i-4) is not an element of S'i.
(11) a(i-3) is not an element of S'i.
Our only possible conclusion? If such an i exists then it is not the case that i>5 and so i<6.

ClifDavis

We want to characterize the subsets of Sn that add up to a(n). One possible useful way of characterizing them is as the subsets that can be derived from {a(n)} by the recurrence relationship used in defining a, (for n>3, a(n)=a(n-1)+a(n-3) and the substitution of a(1)+a(2) for a(3) based on the fact that a(1)+a(2)=a(3).

Is this characterization correct. Or is there some value of n with a subset of Sn we will designate as S'n whose elements add to a(n) but cannot be derived from {a(n)} in that way. If there is any such integer n, then there is a smallest such integer i. We have shown that if such an i exists then i<6.

By the examination of those possible subsets, no such i exists.

The examination is left as an exercise for the reader. :-D
No, really.

Well okay, not really. We can run through the possible combinations looking for surprises fairly quickly. The five values we have to worry about are a(1),a(2),a(3),a(4),a(5) which happen to be 1,2,3,4,6.
1+2=3 or a(1)+a(2)=a(3). This would be the big surprise if we were depending totally on the recurrence relationship, but we're not.
1+3=4 or a(1)+a(3)=a(4) which comes directly from the recurrence applied to a(4).
1+4=5 which isn't in S1, S2, S3, S4 or S5.
1+6=7 which isn't in our Si's
2+3=5 which isn't in our Si's
2+4=6 or a(2)+a(4)=a(5) which comes from the recurrence applied to a(5).
2+6=8 which isn't in our Si's
and the rest of the pairs aren't in our Si's
1+2+3=6 or a(1)+a(2)+a(3)=a(5) which comes from applying the recurrence twice, once to a(5) and then to a(4).
And all the other possibilities give us totals not in our Si's.

So no surprises and there is no such smallest i with the property Si contains a subset distinct from {a(i)} that adds to a(i) but the subset cannot be derived from {a(i)} using the recurrence relationship and a(3)=a(2)+a(1).

But since there is no smallest value i for which it is true, it is also not true for any integer n. In short we have successfully categorized the subsets of Sn that add up to a(n) and so we can use haruspex's type of approach to count the number of subsets of Sn which total a(n).

But doing so is of minimal help in solving the problem we're interested in. What is very useful and the reason for suggesting looking at this problem first is that it has forced us to develop the machinery that we need to tackle the actual problem.

ClifDavis

I took a look at haruspex's latest solution. Looking at C(n) and D(n) is much more clever and compact that what I did. I like it.

But I have two comments. The first is that for the actual problem C(n) overcounts the new subsets whose totals exceed A(n) we are actually interested in. We are not actually interested in the subsets where A(n) is added in, rather we want those without A(n) whose total exceeds A(n) and then we will toss A(n) to be the largest element. This is not a problem because we can leave the definition of C(n) alone and then subtract 2^(n-1)-1 back off. The other thing is that what we want all the values not just the newest ones, but as haruspex pointed out sometime back this is easy to get around. We just carry forward the older results.

We have the function Count(n) that give the answer we're looking for. We have Countnew(n) that gives the new subsets from increasing n by 1.

Then for n>1, Count(n)=Count(n-1)+Countnew(n).
And to start it off we will say Count(1)=0.

For Countnew we have Countnew(n)=C(n)-2^(n-1)+1 for n>1 and Countnew(1)=0.


And now for the second comment. The derivation of the relationships from the initial definition of what C(n) and D(n) means is wonderful. But those relationships only work once n has a sufficient size. Does C(2)= 2^(2-1)-1+2^(2-3)+C(-1)+D(-1) = 2-1+1/2 + C(-1) + D(-1) = 1.5+undefined stuff? I'm pretty sure that the 1.5 isn't very relevant to the logic you used to obtain the relationship.

Instead we need definitions for C(1), C(2), C(3) and maybe more before n gets big enough for the full relationship to kick in. Similarly for D(n). But in finding the solutions on the bottom you assumed that the relationships were true everywhere which is not the case and is why it gives you C(2)=4*7/9 = 3 1/9 instead of C(2)= 1, the number of subsets of S2 with a total over a(2)=2.

Notice that Countnew(2)=C(2)-2(n-1)+1=1-2+1=0.
Count(2)=Count(1)+Countnew(2)=0+0=0 which is correct.

Now what I did was work out the recurrence relation for Count(n) directly but it's ugly looking and I wind up having to assume that n>12, so I have to give 12 values of Count before the full relationship kicks in. On the other hand, the process of developing the recurrence relationship makes coming up with the 12 values fairly easy. But I'm now out of time and it will be Thursday before I can start typing on this again. :-(

Clif

ClifDavis

And there were some messages I missed reading. I see you already pointed this out. Well, I was going to go to bed, but who needs sleep?

ClifDavis

Okay. If you are trying to solve this for a very large n with modulus m then a single recursively defined function is the way to go. The reason is that you can then set up your recurrence relationship as a matrix operation and take powers of the matrix mod m fairly easily.

Let's do it with the A(n) recurrence relationship as an example.

We start with our initial values as a vector (A(1),A(2),A(3)) and then set up a matrix M which when we multiply by to get the next three values (A(4),A(5),A(6)) and that in general if we have any successive 3 values (A(i),A(i+1),A(i+2)) multiplication by M will give us a vector with the next three values (A(i+3),A(i+4),A(i+5)). The recurrence relationship is captured by the following 3x3 matrix.

1 1 1

0 1 1 = M

1 1 2


Perform the matrix multiplication of the vector (1 2 3) by the Matrix and you will see that you get (4,6,9).

Where did this matrix come from? Well you will notice that multiplication by the first column of M performs the recurrence formula directly by adding the first and third term of the vector. The next row add the previous term as given by the previous column vector to two terms before which is given by a column vector with 1 in the second term and 0 elsewhere and the sum is the 2nd column vector of M. The last column vector of M is derived by taking the column vector of the previous term and adding a column vector with zeros except for the 3rd entry, giving us the last column of M. In other words M is derived from the recurrence formula in a fairly straightforward way.

Now suppose we are interested in A(100). We start with (A(1),A(2),A(3)) in our vector and after k multiplication by M obtain (A(3k+1),A(3k+2),A(3k+3)). Since 100 is 3*33+1, we want the first element of the vector after 33 multiplications by M. But I am not going to multiply by M 33 times. Instead I am going to multiply the Matrix M by itself to get M^2. Multiplying a vector times M^2 gives the same result as multiplying by M twice. I multiply M^2 by itself to get M^4, and multiply that by itself to get M^8. Then I get M^16 and then M^32. So to find the result I want I multiply (1 2 3) by M^32 and then that vector one more time by M to give the same result as multiplying by M 33 times.

Or actually I would really multiply by M to start with and then again by M^32 after calculating it, using the binary representation of 33 = 100001 to guide me when to multiply the vector as I calculate the ever larger powers of M. In general to take M to a k power will take me log(k) matrix multiplication and a worst case of log(k) vector multiplications, where we are taking the log base 2.

Unfortunately the numbers get very large very quickly when dealing with large n and hence with large k. But if we are doing all our matrix arithmetic mod m, then it really isn't a problem.

SeventhSigma

I know that finding the modular exponentiation of a matrix can find solutions to recurrences, but in this case I was not sure how to do it when there were multiple, interlaced recurrences involved, since c(n) and d(n) meld into each other and g(n) relies on c(n). It didn't seem as simple as just raising a singular matrix to higher powers, taking the modulus each step.

The recurrences I refer to: http://www.physicsforums.com/showpos...2&postcount=55

ClifDavis

Okay, I have now convinced myself that your general equations for C(n) and D(n) work for n>3.

I prefer to express C(n)= C(n-3)+D(n-3)+5(2^(n-3))-1 but that's a matter of taste.

So we have:
C(1)=0
C(2)=1
C(3)=3
C(n)= C(n-3)+D(n-3)+5(2^(n-3))-1 for n>3
D(1)=0
D(2)=0
D(3)=1
D(n)=C(n-1)+D(n-3) for n>3

Countnew(1)=0
Countnew(n)=C(n)-2^(n-1)+1 for n>1

Count(1)=0
Count(n)=Count(n-1)+Countnew(n) for n>1

Now that I look at it, the definition of Countnew could be incorporated directly into Count and Countnew could go away. Additionally it would make better sense if Countnew was defined by old values and not current values.

Okay, kill the previous definition of Countnew and Count and we will redefine Count as
Count(1) = 0
Count(2) = 0
Count(3) = 0.
Count(n)=Count(n-1)+C(n-3)+D(n-3)+2^(n-3)

Ok let's give it a try and construct a table and then maybe see if we can construct a suitable matrix version.

n 2^(n-3) C(n) D(n) Count(n)
1 0.25 0

Arg. Falling asleep at the keyboard. Time to quit. Back Thursday.

ClifDavis

Well I may go back and give the derivation of just Count as a single recurrence, but now I think on it a single vector should be able to to show all the different values, and the Matrix update them all.

But I really have to get some sleep before it's time to get up.
Sorry.

ClifDavis

As I was going to bed, it hit me that the matrix doesn't have to update 3 values at once. The big savings is in being able to take the powers of the Matrix and skipping all the internal multiplications.

We start with an original vector of

(0,0,0,0,1,3,0,0,1,2,1) where the first element of our vector is count(1). To find count(n) we multiply by M^(n-1) and take the first element of our vector.

0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0
0 0 1 0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 1 0 0 = M
0 0 1 0 0 1 0 0 1 0 0
0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0
0 0 1 0 0 5 0 0 0 2 0
0 0 0 0 0 -1 0 0 0 0 1

I'm 3/4 asleep and won't swear I didn't make a mistake.

At any point the vector should be (count(i).count(i+1),count(i+2),c(i),c(i+1),c(i+2),d(i),d(i+1),d(i+2),2 ^i,1) and our initial vector is for i=1.

- Clif

haruspex

You mean, to the nearest billion?
All the roots of absolute value less than 1 will become completely irrelevant, leaving only the 1.3247 root. So once we have the coefficient for that it will be straightforward. But I think it would be a good idea to extract all the coefficients so that the correctness of the formula can be demonstrated for n up to 10.

haruspex

SeventhSigma, please clarify before I go any further: do you only want these values for large N modulo 1 billion (which would seem an odd thing to want to know), or did you mean want an answer to the nearest billion?

SeventhSigma

What I mean is that I am trying to find the last 9 digits (and so this is the same as the result modulo 1 billion) of g(large N). It is easy to see that the result explodes into huge numbers very quickly (even in your Excel output you can drag it all down and watch the last column erupt)

SeventhSigma

Just pointing out that this didn't seem to work either, testing it for N=10 the resulting vector is (0, 0, 0, 10, 13, 5, 12, 21, 10, 7424, -41) using a program I wrote a while back to find final vector = initial vector*(matrix^power) modulo m. Wondering how you go about making such a matrix/vector (I tried doing this approach from the very beginning)

ClifDavis

I believe you have a problem in your matrix multiplication routine then. Each time the vector is multiplied by M the 10th (next to last) element should double and 7424 is not a power of 2.

When I have more than a few seconds we can go over where M comes from.

Check your matrix multiplication.

SeventhSigma

I've used my matrix multiplication procedure many other times and it hasn't failed yet, but it is still possible that something is wrong on my end. I too noticed that 7424 was not a power of 2 but this may be because I am multiplying the vector by M, so perhaps 7424 is 2^1 * some other value = 7424.

When I output the matrix after raising it to power 10-1=9, I get

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
4, 7, 8, 1, 3, 1, 0, 3, 4, 0, 0,
3, 4, 7, 0, 1, 3, 1, 0, 3, 0, 0,
6, 7, 8, 3, 1, 1, 3, 4, 1, 0, 0,
7, 11, 12, 3, 4, 1, 1, 6, 5, 0, 0,
4, 7, 11, 0, 3, 4, 1, 1, 6, 0, 0,
4, 4, 7, 1, 0, 3, 3, 1, 1, 0, 0,
242, 515, 1066, 385, 785, 1575, 210, 435, 890, 512, 0,
-8, -14, -21, -4, -7, -8, -4, -7, -11, 0, 1

I do see 2^9 = 512 in there. Does this match you?

My procedure would then take that matrix and multiply it by (0,0,0,0,1,3,0,0,1,2,1) as a column

I just tried inputting the matrix above and the vector in the site http://www.bluebit.gr/matrix-calculator/multiply.aspx
http://i.imgur.com/sPtLd.jpg
Please let me know if I've misunderstood you

haruspex

The recurrence relation gave the right numbers all the way to n=10 (as far as I went). See post #53 and SeventhSigma's earlier post mentioning 501.