Subset problem

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:

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 + [itex]\sum[/itex][itex]^{6}_{i=1}[/itex]k[itex]_{i}[/itex]λ[itex]^{n}_{i}[/itex] = (2^(n-1))*14/9 + [itex]\sum[/itex][itex]^{6}_{i=1}[/itex]k[itex]_{i}[/itex]λ[itex]^{n}_{i}[/itex]
where the λ[itex]^{i}[/itex] are the roots of λ^3 +/- λ - 1 = 0
So G(n) = [itex]\sum[/itex]{(2^(n-1))*5/9 + 1 + [itex]\sum[/itex][itex]^{6}_{i=1}[/itex]k[itex]_{i}[/itex]λ[itex]^{n}_{i}[/itex]}
= ((2^n)-1))*5/9 + n + [itex]\sum[/itex][itex]^{6}_{i=1}[/itex]g[itex]_{i}[/itex]λ[itex]^{n}_{i}[/itex] + some constant
where the g[itex]_{i}[/itex] are related to the k[itex]_{i}[/itex] by g[itex]_{i}[/itex] = k[itex]_{i}[/itex]*λ[itex]_{i}[/itex]/(λ[itex]_{i}[/itex]-1)

It remains to figure out the λ[itex]_{i}[/itex] (two sets of roots will be complex pairs) and use the first so many values of G(N) to find the g[itex]_{i}[/itex]. The constant should be
-[itex]\sum[/itex][itex]^{6}_{i=1}[/itex]g[itex]_{i}[/itex]/λ[itex]_{i}[/itex]
Of course, the g[itex]_{i}[/itex] 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/Fibonac...orm_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 any one 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

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.


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.