Solving the Subset Problem: Finding the Count of Valid Sets from 1 to N

[haruspex]

So you found all the roots and coefficients? I haven't tried to do that. Could you post them? Or did you just run through the logic recurrence to see if it gave the right answer?

 

[SeventhSigma]

No I mean I tried to take the general logic of your explanation and see if I could remap it by changing the way I handle targets and inclusions

[1, 2, 3, 4, 6] = S for N=5
so if summation target = 6 that means we would have (4, 6) but the rest of the subset S only works if we take at least 2 elements because (1, 4, 6) would not work, and so on.

Otherwise yes I just went through the recurrence to see if it returned the right answer (wrote a program)

 

[haruspex]

I put my recurrence relation, plus the mapping to your problem, into a spreadsheet and it gave 501 for N=10. You have to be careful where you start the recurrence. C(3) = D(4) = 3, D(3) = 1. If you start too soon you pick up the fictitious value A(0) = 1.
(This is a bit confusing because C(n) is in spreadsheet col D, D(n) in col E.)
n A 2^ C D APN AP
1 1 1 0 0 0
2 2 2 1 0 0 0
3 3 4 3 1 0 0
4 4 8 9 3 2 2
5 6 16 20 9 5 7
6 9 32 43 21 12 19
7 13 64 91 46 28 47
8 19 128 188 100 61 108
9 28 256 383 209 128 236
10 41 512 776 429 265 501
The formulae, starting with N=5, look like:
D5 =C5-1+C3+D2+E2 (i.e. C(n), col D)
E5 =D4+E2
F5 =D5-C5+1
G5 =G4+F5

 

[haruspex]

As I said, the double use of A, C, D for variables and spreadsheet columns is confusing.
In the spreadsheet:
col A is N
col B is A(N)
col C is 2^(N-1)
col D is my C(N)
col E is my D(N)
col F is what I've previously referred to as APN(N)
col G should be the number you're after

The formulae at the end of my previous post refer to spreadsheet columns.
The array starts (N=1) in row 2 of the spreadsheet, row 1 being headings.
I've given the formulae that go in row 5. Above row 5 these don't apply in all columns so you need to plug in the hard numbers.

APN(N) is ClifDavis (mis)reading of the problem, i.e. it takes the target to beat as being A(N), rather than the highest number in the subset. I've kept that in because it is a useful step along the way to the numbers you want.

 

[SeventhSigma]

I am trying to find another way to simplify everything so I can solve this for large n mod m eventually

using your notation:

c(n) = 2^(n-1) - 1 + 2^(n-3) + c(n-3) + d(n-3)
c(1) = 0, c(2) = 1, c(3) = 3

d(n) = c(n-1) + d(n-3)
d(1) = 0, d(2) = 0, d(3) = 1

g(n) = c(n) - 2^(n-1) + 1 + g(n-1)
g(1) = 0

where g(n) is the answer function

but I can rewrite g(n) as
g(n) = n - 2^n + 1 + X
Where X is c(2) + ... + c(n)

What might be a good way to quickly find sums of c(n) sequences? I tried listing everything out longhand:

c(1) = 0
c(2) = 1
c(3) = 3
c(4) = 2^(3) - 1 + 2^(1)
c(5) = 2^(4) - 1 + 2^(2) + 1
c(6) = 2^(5) - 1 + 2^(3) + 3 + 1
c(7) = 2^(6) - 1 + 2^(4) + 2^(3) - 1 + 2^(1) + 3
c(8) = 2^(7) - 1 + 2^(5) + 2^(4) - 1 + 2^(2) + 1 + 2^(3) - 1 + 2^(1)
c(9) = 2^(8) - 1 + 2^(6) + 2^(5) - 1 + 2^(3) + 3 + 1 + 2^(4) - 1 + 2^(2) + 1 + 1
c(10) = 2^(9) - 1 + 2^(7) + 2^(6) - 1 + 2^(4) + 2^(3) - 1 + 2^(1) + 3 + 2^(5) - 1 + 2^(3) + 3 + 1 + 3

d(1) = 0
d(2) = 0
d(3) = 1
d(4) = 3 
d(5) = 2^(3) - 1 + 2^(1)
d(6) = 2^(4) - 1 + 2^(2) + 1 + 1
d(7) = 2^(5) - 1 + 2^(3) + 3 + 1 + 3

so g(10) here would be g(10) = 10 - 2^10 + 1 + c(2) + c(3) + c(4) + c(5) + c(6) + c(7) + c(8) + c(9) + c(10) = 501

 

[haruspex]

Recall that I arrived at:
C(n) = (2^n)*7/9 + \sum^{6}_{i=1}k_{i}λ^{n}_{i} = (2^(n-1))*14/9 + \sum^{6}_{i=1}k_{i}λ^{n}_{i}
where the λ^{i} are the roots of λ^3 +/- λ - 1 = 0
So G(n) = \sum{(2^(n-1))*5/9 + 1 + \sum^{6}_{i=1}k_{i}λ^{n}_{i}}
= ((2^n)-1))*5/9 + n + \sum^{6}_{i=1}g_{i}λ^{n}_{i} + some constant
where the g_{i} are related to the k_{i} by g_{i} = k_{i}*λ_{i}/(λ_{i}-1)

It remains to figure out the λ_{i} (two sets of roots will be complex pairs) and use the first so many values of G(N) to find the g_{i}. The constant should be
-\sum^{6}_{i=1}g_{i}/λ_{i}
Of course, the g_{i} will be such that all the imaginary terms cancel.

 

[SeventhSigma]

I don't really understand that method at all... there's no other shortcut?

 

[Mandlebra]

Some times a generating function approach*is*the short cut

 

[SeventhSigma]

I guess I am just not understanding how generating functions work here because I am trying to solve this for a very large n with modulus, and I worry that using roots will result at in decimal values that will lack precision (assuming that I even figure out how that approach works)

 

[haruspex]

It's not a generating function. Generating functions have the values of interest as coefficients in an infinite power series. It is a closed form expression which, once the constants have been figured out, will produce the answer for any n in a fixed number of steps. You can do the same for all sorts of series. E.g. http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression.
Although the computation involves irrationals, the answer, if calculated precisely, always produces an integer. So you only have to calculate it precisely enough to get the error less than 0.5. The snag is that how accurately the constants need to be calculated probably depends on n.
When I get time I'll have a go at finding the constants.

 

[Mandlebra]

Ah are correct, I misread. Good thread though with a nice topic

 

[SeventhSigma]

I don't understand how this lambda equation was arrived at or how you solve it. Where does the k term come from? Are all lambdas the same since we're looking at the same equation here (λ^3 +/- λ - 1 = 0)? Trying to piece it together but I am not sure what I'm doing.

 

[haruspex]

The lambdas are roots of a 6th order polynomial, so there are in principle 6 of them.
The polynomial is (λ^3 + λ - 1)(λ^3 - λ - 1), so the roots are those of the two cubics (λ^3 + λ - 1) and (λ^3 - λ - 1). Each has one real root and a complex pair.
The importance of these numbers is that if C(n) is a solution of the recurrence relation then C(n) + λ^n is also, but only for these 6 values of λ. This means that we can generate all possible solutions for C(n) by starting with anyone solution and adding combinations of terms like λ^n. Then we plug in the boundary conditions (the first few values) to find the right combination of these terms.
The real roots are 0.6823.., 1.3247.. The complex roots are -.3412+/-i*1.1615, -.6624+/-i*0.5623.
I'm not sure how the cancellation of the imaginary parts will happen. I'm going to assume that it happens separately within each pair, i.e. the imaginary parts of λ^n will cancel with the contribution from its conjugate root. This means the coefficients will be the same for both members of the pair. That gets us down to only 4 terms to worry about.
The easiest way to extract the real components is to write the complex roots in r.e^iθ form. Then the real part of λ^n is r^n.cos(n*θ).
The table of lambda powers therefore starts:
n 1 2 4 5
0 1 1 1 1
1 1.32 1.32 0.68 0.68
2 1.75 1.44 0.47 -0.88
3 2.32 1.07 0.32 -2.44
4 3.08 -0.15 0.22 -1.73
5 4.08 -2.61 0.15 2.07
6 5.4 -6.6 0.1 5.97
7 7.16 -12.09 0.07 4.39
8 9.48 -18.35 0.05 -4.85
9 12.56 -23.59 0.03 -14.58
10 16.64 -24.5 0.02 -11.1
It remains to find four constant coefficients to multiply each column by, and one more additive constant. Adding up those 5 terms for each row, plus ((2^n)-1))*5/9 + n, should then give the required answers. We need to use the known values for G(1) to G(5) to find these. So that's an exercise is simultaneous linear equations with 5 unknowns. (As I mentioned, the additive constant can actually be calculated from the four coefficients and the lambdas, so we can reduce it to four unknowns.)
I can have a go at that later if you like.

 

[SeventhSigma]

Would this method be workable for solutions where n>10^18, modulo 1 billion? I ask because I am wondering how precise the roots would need to be?

 

[ClifDavis]

Fwiw, I had a go at this simpler problem:
Sn = {A(1), .. , A(n)}, where the A(n) satisfy the recurrence relation A(n) = A(n-1) + A(n-3), etc.
How many subsets of Sn sum to A(n) exactly?

The value of the question isn't in obtaining the actual value of of the number of such subsets of Sn, but rather in the fact that in order to do so, you have to be able to characterize the subsets that Sn counts and it's what you have to do to accomplish that which gives you the tools to answer the original question.

I can't even solve that yet. The problem is that some such subsets cannot be obtained by repeated application of the recurrence relation to break down the target sum. E.g. A(1)+A(2) = A(3).

And you put your finger on the significant question. Can all such subsets be obtained by repeated application of the recurrence relation? And as you correctly point out, the answer is no, as a(1)+a(2)=a(3) which certainly cannot be obtained by repeated application of the recurrence relation. Nor is this a lone exception. For example a(1)+a(2)+a(5)=a(6) cannot be obtained by repeated use of a(n)=a(n-1)+a(n-3). But we can go a(6)=a(6-1)+a(6-3)=a(5)+a(3)=a(5)+a(2)+a(1).

So this leads to a new question. Can all such subsets be obtained by repeated application of the recurrence relation combined with the possible substitution of a(1)+a(2) for a(3)?

In order to answer the question we need 4 facts.

(1) The a(i) are positive. Or another words if n>0 then a(n)>0.

(2) The a(i) are increasing, a(1)<a(2)<a(3)<a(4)<... Or in other words if n>1 then a(n-1)<a(n).

(3) For n>0, the sum of the first n values, a(1)+...+a(n) is less than a(n+3).

[[If n=1, the expression on the left is intended to have only one term as a(n) is a(1). I would use summation notation to be clearer, but have no appropriate tool to do that.
Notice that this third item can also be stated as:
For n>3, the sum of the first n-3 values, a(1)+...+a(n-3) < a(n).]]

(4) for n>0, a(1)+...+a(n) <a(n+1)+a(n+2)

[[or for n>2 a(1)+...+a(n-2)<a(n-1)+a(n)]]

 

[ClifDavis]

The a(n) are positive, ie. For n>0, a(n)>0.

Our definition of the a function is:
a(1)=1
a(2)=2
a(3)=3
and for n>3, a(n)=a(n-1)+a(n-3).

Notice that a(0) and a(-1) etc. are not defined. We might be able to use the recurrence relationship to define them, but we don't. There is also the assumption that n is an integer. We don't define a(1.5).

Suppose the a(n) are not all positive. If for some integer we have a zero or negative result, ie. a value of a(n) which is not positive, then since they are integers, there is a smallest value, let's call it k, for which a(k)>0 is not true.

Now k is not 1 or 2 or 3 as
a(1)=1>0
a(2)=2>0
a(3)=3>0
and so k>3.

But this means a(k)=a(k-1)+a(k-3).

Since k>3 then k-1>3-1=2>0 (or k-1>0 ) and k-3>3-3=0 (k-3>0). So a(k-1) and a(k-3) are defined. But since -1<0 k-1<k. And likewise k-3<k. Now k was the smallest integer for which a(k)>0 is false so we know that a(k-1)>0 and a(k-3)>0. But this means that a(k-1)+a(k-3)>0+0=0. But from the recurrence relationship a(k) is a(k-1)+a(k-1), and so a(k)>0 contrary to our assumption. And this means that a(k) is not the smallest value of k that isn't positive, and so there is no smallest integer k such that a(k) is not positive and so there aren't any. Which is to say they are all positive.

 

[ClifDavis]

The a(i) are increasing, if n>1 then a(n-1)<a(n).

Well for n=2 then 1<2 or a(1)<a(2 or a(2-1)<a(2) or a(n-1)<a(n) is true for n=2.
For n=3 we know 2<3 so a(2)<a(3) or a(3-1)<a(3) or a(n-1)<a(n) for n=3.

Assume there is an integer n>1 for which a(n-1)<a(n) is not true. Let i be the smallest such that i>1 but a(n-1)<a(n) is false.
We have already seen that i is not 2 or 3 because it would be true for them. So i>3. This means that i-1>2>0 and i-3>0. Which means a(i-1) and a(i-3) are defined and a(i-1)>0 and a(i)-3>0. Or as I prefer, 0<a(i-3). So a(i-1)+0<a(i-1)+a(i-3). But a(i-1)+0=a(i-1) and as we all know since i>3, a(i-1)+a(i-3)=a(i), which gives us a(i-1)<a(i), contrary to our assumption. So there no such smallest i, which means there is no such n and the a(i) are strictly increasing.

 

[ClifDavis]

For n>0, the sum of the first n values of a(i) is less than a(n+3).

I like to state it that way, though when I use it, its usually in the form, if n>3 then the sum of the first n-3 values of a(i) is less than a(n).

For n=1 the first 1 values of a(i) is a(1) and it's sum is a(1)=1. a(1+3)=a(4)=4. It's certainly the case that 1<4, and so it's true for n=1.

Let's assume that it's true for some integer k>0, ie. the sum of the first k values of a(k) is less than a(k+3). Or as I prefer to write it, a(1)+...+a(k)<a(k+3). Since k>0 then k+1 >0 and so a(k+1) is defined and we can add it to both sides of our inequality to get a(1)+...+a(k)+a(k+1)<a(k+3)+a(k+1). Since k>0, k+4>4>3, and so from our recurrence relationship we know that a(k+3)+a(k+1)=a(k+4).
And so we have the sum of the first k+1 values of a(i), a(1)+...+a(k+1)<a(k+3)+a(k+1)=a(k+3+1).

So we know it's true for k=1 and if its true for k, then it's true for k+1, so by induction it's true for all integer k>0 or if you prefer, for all integer n>0.

 

[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]

SeventhSigma, Sorry, I forgot to point out that this is not quite the problem as you stated it, but that it should be mappable to it fairly easily.
First, if you exclude the use in the sum of the top term in the set, that just subtracts 2^(n-1)-1 possibilities. That gets us to the version ClifDavis considered. (I probably could have got straight to that by modifying the argument a little. You might care to try that.) Now you have to sum the counts for n = 1 to N to get the solution to the correct version.

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]

I guess I am just not understanding how generating functions work here because I am trying to solve this for a very large n with modulus, and I worry that using roots will result at in decimal values that will lack precision (assuming that I even figure out how that approach works)

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: https://www.physicsforums.com/showpost.php?p=3922972&postcount=55

 

[ClifDavis]

OK, here's my attempt at the actual problem. Methods and results largely the same.

Let C(n) be the number of subsets of Sn that sum to more than A(n).
Let D(n) be the number of subsets of Sn that sum to more than A(n)+A(n-1).

Starting with a summation target of A(n)+1 (or higher):
1. Suppose we use A(n). We now only have to use one other, i.e. any of 2^(n-1)-1 subsets. OTOH,
2. if we don't use A(n) we know we must use either A(n-1) or A(n-2) or both.
2a. If we use both then we can use any combination of A(1) to A(n-3), 2^(n-3) subsets.
2b. If we use A(n-1) but not A(n-2) then we have a remaining target of A(n)+1-A(n-1) = A(n-3)+1, for which there are C(n-3) possibilities.
2c. If we use neither A(n) nor A(n-1) then we have a target of A(n)+1 = A(n-2)+A(n-3)+A(n-4)+1. We must use A(n-2). That leaves a target of A(n-3)+A(n-4)+1, for which there are D(n-3) possibilities.
Putting this together:
C(n) = 2^(n-1)-1 + 2^(n-3) + C(n-3) + D(n-3)

Similarly, with D(n), we can use A(n), leaving a target of A(n-1)+1; or not use A(n), leaving a target of A(n)+1 = A(n-2) + A(n-3) + A(n-4) + 1.
D(n) = C(n-1) + D(n-3)

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]

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: https://www.physicsforums.com/showpost.php?p=3922972&postcount=55

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]

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

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]

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)

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]

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

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.

 

[haruspex]

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)

OK. In that case, the polynomials should be solved modulo 1 billion. I'll havde a go at that.

 

[ClifDavis]

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

You multiplied the matrix times the transpose of the row vector? Okay, that's the problem then. I wrote the vector and matrix intending to multiply the row vector times the matrix, not the matrix times a column vector. If you are going to transpose the row vector into a column vector and put it on the right then you need to use the transpose of M as well.

So yeah, if you do that then the 512 will be multiplied by 2 and added to a bunch of zeros giving you 1024 which is what I expected to see.

 

[SeventhSigma]

I think I understand better now, but how does one go about creating M in the first place? How do you know what values are 0, 1, etc?

 

[haruspex]

OK. In that case, the polynomials should be solved modulo 1 billion. I'll have a go at that.

Hmmm.. the polynomials have no roots modulo 1 billion, not even complex ones. Don't know what this implies. Thinking...

 

[ClifDavis]

I think I understand better now, but how does one go about creating M in the first place? How do you know what values are 0, 1, etc?

I'm going to assume now that you are using the transpose of M and multiplying by a column vector. To write a column vector as a row vector I'm going to use the ^T to indicate transpose as in vectors V and V^T

We want to use the functions defined by:

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

Count(1) = 0
Count(2) = 0
Count(3) = 0.
Count(n)=Count(n-1)+C(n-3)+D(n-3)+2^(n-3) for n>3

That last one, you will note, looks pretty similar to the formula for C(n) except that we are subtracting back off the 2^(n-1)-1 that it overcounts and adding in the old value of count.

We want to write M so that it changes the vector
(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),1)^T
to
(count(i+1),count(i+2),count(i+3),c(i+1),c(i+2),c(i+3) ,d(i+1),d(i+2),d(i+3),2^(i+2),1)^T

Since we have 3 values of the c,d, and count functions we can safely assume that i+3>3.

When we do the matrix multiplication with the old column vector, the first value of the new column vector will be the result of multiplying (dot-product) the first row of M by the old vector. We want the result to be count(i+1). count(i+1) is in the second position of the old vector. So to get that value, we can have the first row of M be the vector
(0,1,0,0,0,0,0,0,0,0,0). When we multiply it by the old vector we get 0*count(i)+1*count(i+1)+0*count(i+2)+0*c(i)+0*c(i+1)+0*c(i+2)+0*d(i)+0*d(i+1)+
0*d(i+2)+0*2^i+0*1=count(i+1) which is exactly what we wanted.

If you look back at what I gave you as M, but which is now M^T you will see (0,1,0,0,0,0,0,0,0,0,0)^T is exactly the first column.

The second row of M is what gets multiplied by the old column vector to give the second element of the new column vector. We want the second element of the new vector to be count(i+3). The third element of the old vector is count(i+3). I trust it will be no surprise to say that we write the second row of M as
(0,0,1,0,0,0,0,0,0,0,0).

The third row of M is a little trickier. We want Count(i+4) there. But there is no count(i+4) entry in the old vector. But we want our multiplication to produce it. We have the relationship Count(n)=Count(n-1)+C(n-3)+D(n-3)+2^(n-3) for n>3. Back four paragraphs we noted that we could safely assume i+4>3 and so we use the equation with n=i+4. This gives us Count(i+4)=Count(i+4-1)+C(i+4-3)+D(i+4-3)+2^(i+4-3)
=count(i+3)+c(i+1)+d(i+1)+2^(i+1).

Now in the old column vector, count(i+3) is in the 3rd place, c(i+1) is the 4th element, d(i+1) is the seventh element and 2^(i+1) is the next to last element. So we write the third row of M as (0,0,1,1,0,0,1,0,0,1,0) with 1's in the 3rd,4th,7th and next to last positions and 0 elsewhere.

The next two rows of M will be to shuffle the old values of c(i+2) and c(i+3) into their new positions. And then our sixth row of M will implement the formula for c(i+4), c(i+4)= c(i+1)+d(i+1)+5(2^(i+1))-1

The new wrinkle is that we don't have an entry for 5*2^(i+1) or -1 but we do have an entry for 2^(i+1) in the 10th position and 1 in the 11th. And so we echo the formula in the sixth row of M as (0,0,0,1,0,0,1,0,0,5,-1) and note that the multiplication of 2^(i+1) and 1 is accomplished by placing 5 in the 10th position and -1 in the 11th.

Similarly the next three rows of M will update the d values. This leaves two rows. The first has the responsibility of updating the power of 2 by doubling it, which we accomplish by
(0,0,0,0,0,0,0,0,0,2,0).

And finally we take note of the last row and last element. Sticking an extra value of 1 at the end of your vectors is an old trick to allow additions of constant by matrix multiplication. It's a good trick, but to preserve those constant 1's at the end of your vectors we need a last row of M which does just that. (0,0,0,0,0,0,0,0,0,0,1).

And that's our M, an exact implementation of our recursive definitions.

Can we be more efficient. Why yes. Our vectors have three successive values of the the C, D, and Count functions. The simplest and most productive change is to precompute M^3 and use it to update three values of Count at a time as we did with our matrix for obtaining A(n).

But we can also cut down from a 11x11 matrix to a 9x9 matrix and calculate the values 7 at a time.

More later.

 

[SeventhSigma]

thank you for the explanation, it was very helpful!

 

[ClifDavis]

thank you for the explanation, it was very helpful!

Thanks, I never know when my explanations are adequate and when they are as clear as mud.

 

[ClifDavis]

Yay! It's Thursday. And of course other things have come up, but we'll see how it goes.

My original approach to this was a bit different than haruspex's clever approach to the problem where he works with C(n) and D(n). Instead I worked at building a recurrence formula for Count(n) directly. But in doing so at one point I needed a function we can call R4(n) which for n>4 was defined to be the number of subsets of Sn which totaled more than A(n)+A(n-1)+A(n-2)+A(n-3).
But I never needed to work out what the full formula for R4(n) was because I was able to use an algebraic trick to Compare Count(i) to Count(i-3) and make R4 disappear to give me the final recurrence formula.

But in the derivation I had to use R4(n-8) which meant that the validity of the final recurrence formula depended on n-8>4 or n>12. While I derived a algebraically simplified form of the general recurrence formula for Count(n) with various terms of Count(n)and a final correction of a multiple of a power of 2 and a constant, I also kept around the unsimplified form of the formula because starting with Count(4) and going up, I knew for which values of n the different parts of the formula would start kicking in, and so this made calculating Count(4) through Count(12) relatively easy without having to actually create the relevant subsets of Sn.

As I say, I think heruspex's approach with C(n) and D(n) is a lot cooler and it occurred to me to see if I could work out the recurrence formula for Count(n) directly from them. And it is possible. Unsurprisingly it produces the very same recurrence formula as my simplified form but now we only have to assume that n>7.

In other words we can give the 1st 7 values and the recurrence formula and we're in business. We still need powers of 2 and a constant though. This means that we can set up a 9 element vector starting with 7 consecutive values of Count(n) and the an appropriate power of 2 and finally a 1 and create a matrix M to transform it to one with the values of Count(n) shifted to the left and then a new value created from the recurrence relationship followed by the next power of 2 and of course the value 1.

We can of course precalculate M^7 to give us 7 new values at a time, and the use of a 9 element vector instead of an 11 element vector also represents a savings.

So at this point I would say that we're pretty well motivated to look at the general recurrence formula for Count(n).

 

[haruspex]

I've been working on convergent lines with you ClifD.
My 7-term recurrence formula is surely the same as yours. In homogeneous form, the coefficients for G(n-1) down to G(n-7) to generate G(n) are:
1, 0, +2, -1, -1, -1, +1.
But what about the inhomogeneous term (25*2^(n-7)-1)?
I claim that if we generate a sequence H(n) with suitable starting values H1 to H7 from the above relation all we need to do to get G(n) is add:
n + 5*(2^n)/9
The 7 starting values for H(n) are simply those needed to make G(1) to G(7) right; and it works!
H[1, 7] = -19/9 -38/9 -67/9 -98/9 -142/9 -203/9 -280/9
Applying the homogeneous recurrence relation for the next 7 gives:
H[8, 14] = -380/9 -517/9 -701/9 -934/9 -1247/9 -1675/9 -2225/9
Adding in n + 5*(2^n)/9 to each we get
G[1, 7] = 0 0 0 2 7 19 47
as arranged, and beyond that:
G[8, 14] = 108 236 501 1045 2149 4378 8869

The nice thing about having a homogeneous relation is that we can accelerate the matrix multiplication. The matrix is now constant, so we can form high powers of it quickly by squaring repeatedly (applying modulo 1E9 as we go). If you want a power of M other than a power of 2 then just form a product of selected generated powers along the way, according to the binary bit pattern of the target power.

For the purposes of taking the result modulo 1E9, note that 5/9 mod 1E9 is 444444445.
I'm sure something clever can be done with 2^n mod 1E9 (for n >= 9).

 

[ClifDavis]

The last time around, in order to develop the M matrix we've been using, I got rid of the Countnew function and expressed Count solely in terms of older values. But for what we are about to do, I want to drop back to a slightly more transparent version.

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(0)=0
Count(n)=Count(n-1)+Countnew(n) for n>0.

Functionally Countnew(n) is applying the overcount correction to C(n) and Count is accumulating the count of smaller subsets of Sn.

Now I want to start by calculating the general formula for C(n-3) and D(n-3).
For n-3>3, which is to say for n>6, we can just apply the formulas directly.

C(n)= C(n-3)+D(n-3)+5(2^(n-3))-1
C(n-3)= C(n-3-3)+D(n-3-3)+5(2^(n-3-3))-1
or more succinctly
(1) C(n-3)= C(n-6)+D(n-6)+5(2^(n-6))-1 for n>6

and for D(n-3) we take
D(n)=C(n-1)+D(n-3)
and substitute to get
D(n-3)=C(n-4)+D(n-6) for n>6.

But as we recall C(n)= C(n-3)+D(n-3)+5(2^(n-3))-1
and if we substitute in for the D(n-3) term we get
(2) C(n)= C(n-3)+C(n-4)+D(n-6)+5(2^(n-3))-1 for n>6

Now equation (2) gives us an equation for C(n) while equation (3) gives us an equation for C(n-3). The fact that both equations contain a single identical occurrence of the D function, D(n-6) motivates me to look at C(n)-C(n-3) by substituting from equations (1) and (2).

C(n)-C(n-3)=(C(n-3)+C(n-4)+D(n-6)+5(2^(n-3))-1)-( C(n-6)+D(n-6)+5(2^(n-6))-1)
C(n)-C(n-3)=C(n-3)+C(n-4)+D(n-6)+5(2^(n-3))-1-C(n-6)-D(n-6)-5(2^(n-6))+1

We reorganize to put like terms with like terms

C(n)-C(n-3)=C(n-3)+C(n-4)-C(n-6)+(D(n-6)-D(n-6))+5(2^(n-3))-5(2^(n-6)+(1-1)
or
C(n)-C(n-3)=C(n-3)+C(n-4)-C(n-6)+(0)+5(2^(n-3))-5(2^(n-6)+(0)
but 2^(n-3)=8(2^(n-6))
so 5(2^(n-3))-5(2^(n-6) = 40(2^(n-6))-5(2^(n-6))=35(2^(n-6)).
Substituting we get
C(n)-C(n-3)=C(n-3)+C(n-4)-C(n-6)+35(2^(n-6))
and adding C(n-3) to both sides
(3) C(n)=2C(n-3)+C(n-4)-C(n-6)+35(2^(n-6))
all under the condition that n>6.

The recurrence relationship in (3) will let us define C(n) without the use of D(anything) provided we are willing to start with the first 6 values of C(n).

Our definition of Countnew was
Countnew(1)=0
Countnew(n)=C(n)-2^(n-1)+1 for n>1

If n>6 then certainly n>1 and so we must have
Countnew(n)=C(n)-2^(n-1)+1 or conversely
C(n)=Countnew(n)+2^(n-1)-1 for n>1

Trying this out for some other values of n we have
C(n-3)=Countnew(n-3)+2^(n-4)-1 if n-3>1 or n>4.
C(n-4)=Countnew(n-4)+2^(n-5)-1 if n-4>1 or n>5
C(n-6)=Countnew(n-6)+2^(n-7)-1 if n-6>1 or n>7.

If n>7 each of these last three holds as does equation (3). And so we can substitute in (3)
C(n)=2C(n-3)+C(n-4)-C(n-6)+35(2^(n-6))
=2(Countnew(n-3)+2^(n-4)-1)+Countnew(n-4)+2^(n-5)-1
-(Countnew(n-6)+2^(n-7)-1)+35(2^(n-6))
Simplifying
C(n)=2Countnew(n-3)+Countnew(n-4)-Countnew(n-6)+(16+4-1+70)(2^n-7)+(-2-1+1)
C(n)=2Countnew(n-3)+Countnew(n-4)-Countnew(n-6)+89(2^n-7)-2
Now if n>7 then n>1 and we said Countnew(n)=C(n)-2^(n-1)+1. So
Countnew(n)=(2Countnew(n-3)+Countnew(n-4)-Countnew(n-6)+89(2^n-7)-2)- 2^(n-1)+1
which gives us
(4) Countnew(n)=2Countnew(n-3)+Countnew(n-4)-Countnew(n-6)+25(2^n-7)-1 for n>7

which gives us a recurrence formula purely in terms of Countnew.

The remaining step is obtaining a recurrence for Count.

For n>0 we had Count(n)=Count(n-1)+Countnew(n) which means
Countnew(n)=Count(n)-Count(n-1)
Since n>7 then it's clear n-3>0, n-4>0, and n-6>0 and so
Countnew(n-3)=Count(n-3)-Count(n-4)
Countnew(n-4)=Count(n-4)-Count(n-5)
Countnew(n-6)=Count(n-6)-Count(n-7)

We make these substitutions in (4) to get
Countnew(n)=2(Count(n-3)-Count(n-4))+Count(n-4)-Count(n-5)-(Count(n-6)-Count(n-7))+25(2^n-7)-1 for n>7.
Simplifying,
Countnew(n)=2Count(n-3)-Count(n-4)-Count(n-5)-Count(n-6)+Count(n-7)+25(2^n-7)-1 for n>7.
And now Count(n)=Count(n-1)+Countnew(n) with n>7>0 gives us
Count(n)=Count(n-1)+2Count(n-3)-Count(n-4)-Count(n-5)-Count(n-6)+Count(n-7)+25(2^n-7)-1 for n>7.

We have a pure recurrence relation for Count(n) to which we only need add the first 7 values of Count to have it defined.

We still have powers of two and a constant in our recurrence so this give rise to an initial 9 element vector and an update matrix. But I'm out of time now.

(haruspex - just saw your last message, no time to think about it now but will do so later)

(edited to remove a typo and a spurious 1st line)

 

[SeventhSigma]

Is there a general strategy to finding recurrence relationships? Or is it more of an art than science?

 

[ClifDavis]

Is there a general strategy to finding recurrence relationships? Or is it more of an art than science?

Yes, but I don't know what it is. :-|

There is an advanced study of recurrence relationships and solving difference equations in general. Some of which is then used in solving certain types of differential equations.

I think that haruspex may be more familiar with some of the general theory than I am.

 

[ClifDavis]

I've been working on convergent lines with you ClifD.
My 7-term recurrence formula is surely the same as yours. In homogeneous form, the coefficients for G(n-1) down to G(n-7) to generate G(n) are:
1, 0, +2, -1, -1, -1, +1.
But what about the inhomogeneous term (25*2^(n-7)-1)?
I claim that if we generate a sequence H(n) with suitable starting values H1 to H7 from the above relation all we need to do to get G(n) is add:
n + 5*(2^n)/9
The 7 starting values for H(n) are simply those needed to make G(1) to G(7) right; and it works!
H[1, 7] = -19/9 -38/9 -67/9 -98/9 -142/9 -203/9 -280/9
Applying the homogeneous recurrence relation for the next 7 gives:
H[8, 14] = -380/9 -517/9 -701/9 -934/9 -1247/9 -1675/9 -2225/9
Adding in n + 5*(2^n)/9 to each we get
G[1, 7] = 0 0 0 2 7 19 47
as arranged, and beyond that:
G[8, 14] = 108 236 501 1045 2149 4378 8869

The nice thing about having a homogeneous relation is that we can accelerate the matrix multiplication. The matrix is now constant, so we can form high powers of it quickly by squaring repeatedly (applying modulo 1E9 as we go). If you want a power of M other than a power of 2 then just form a product of selected generated powers along the way, according to the binary bit pattern of the target power.

For the purposes of taking the result modulo 1E9, note that 5/9 mod 1E9 is 444444445.
I'm sure something clever can be done with 2^n mod 1E9 (for n >= 9).

Dammit, I had a free hour and just tried to post a longish comparison of our two suggestions and then when I went to submit it claimed I wasn't logged in. though it let me answer SeventhSigma just before. And the post seems to be irretrievable. :-(

Very aggravating

And now I don't have a spare hour.

 

[ClifDavis]

I've been working on convergent lines with you ClifD.
My 7-term recurrence formula is surely the same as yours. In homogeneous form, the coefficients for G(n-1) down to G(n-7) to generate G(n) are:
1, 0, +2, -1, -1, -1, +1.
But what about the inhomogeneous term (25*2^(n-7)-1)?
I claim that if we generate a sequence H(n) with suitable starting values H1 to H7 from the above relation all we need to do to get G(n) is add:
n + 5*(2^n)/9
The 7 starting values for H(n) are simply those needed to make G(1) to G(7) right; and it works!
H[1, 7] = -19/9 -38/9 -67/9 -98/9 -142/9 -203/9 -280/9
Applying the homogeneous recurrence relation for the next 7 gives:
H[8, 14] = -380/9 -517/9 -701/9 -934/9 -1247/9 -1675/9 -2225/9
Adding in n + 5*(2^n)/9 to each we get
G[1, 7] = 0 0 0 2 7 19 47
as arranged, and beyond that:
G[8, 14] = 108 236 501 1045 2149 4378 8869

The nice thing about having a homogeneous relation is that we can accelerate the matrix multiplication. The matrix is now constant, so we can form high powers of it quickly by squaring repeatedly (applying modulo 1E9 as we go). If you want a power of M other than a power of 2 then just form a product of selected generated powers along the way, according to the binary bit pattern of the target power.

For the purposes of taking the result modulo 1E9, note that 5/9 mod 1E9 is 444444445.
I'm sure something clever can be done with 2^n mod 1E9 (for n >= 9).

Okay, try #2 and I'll try to be a bit shorter this time.

SeventhSigma, just in case it isn't clear, haruspex is looking at the family of functions that have the same recurrence formula as Count except that they are missing the final two terms 25*2^(n-7)-1. Based on some of that theory I mentioned, he has determined that there should be such a function H(n) so that H(n)=Count(n)-n-5/9(2^n) and
H(n)=H(n-1)+2H(n-3)-H(n-4)-H(n-5)-H(n-6)+H(n-7). He used the known first seven values of Count(n) to get the first seven values of H(n).

Cutting the exposition short this time, my approach sets up a 9 element vector, (0,0,0,2,7,19,47,2,1)^T and use powers of M^7 to update it, where

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

is a 9x9 matrix and I think you can see where M comes from.

His procedure is more compact starting with the vector (-19/9,-38/9,-67/9,-98/9,-142/9,-203/9,-280/9)^T and using powers of M^7 to update it where now M is a 7x7 matrix

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

Obviously his procedure should take only about half as long as mine all else being equal, though of course all is not perfectly equal, but close. His does require adding n + 5/9*(2^n) back on at the end, but still his approach retains a substantial advantage. My suggestion is simple to implement in mod(1000000000) or indeed mod(anything) as you just perform the multiplication and addition mod(1000000000). No other arithmetic is involved. If you are using his technique it's handy to know that 1/9=888888889(mod 1000000000) as
9*888888889=8000000001=1(mod 1000000000).

 

[SeventhSigma]

I do believe that works... really awesome. I feel like I've been exposed to some sort of mathematical wizardry here! thank you guys... I have much to learn