| The first few numbers are (a[10]=75) :
1, 1, 1, 1, 1, 1, 3, 5, 9, 23,
75,
421,
1103,
5047,
41783,
281527,
2534423,
14161887,
232663909,
3988834875,
45788778247,
805144998681,
14980361322965,
620933643034787,
16379818848380849,
369622905371172929,
20278641689337631649,
995586066665500470689,
72559962302147228286849,
3168992022738213982117009,
221854781474421326332728867,
34951475856493152962631211765,
3005008339620413915704574809401,
379699753474675720531626584024807,
42606783751977661765276440842589595,
10020113764332067086831900975461477669,
2805544254961009286582550261484547842687,
402004673245137783457597234268511135937943,
123986002848096487052630935704945650126513527,
45251164322973497752396978480914726081428497143,
22599166259222085350659654748156962100247034494647
|
| Well, here's a theory as to what *might* be going on, but I haven't
proved it yet...
An algebraic integer, x, is an algebraic number for which the minimal
polynomial, m(t), is of the following form:
t^n + a_1*t^(n-1) + ... + a_n
where: n >= 1
a_i are integers
The critical property is that m(t) is *monic*. This simply means to
say that the coefficient of t^n in m(t) is 1.
So, for instance, the only rational algebraic integers are the integers
themselves. You see why? The minimal poly of a rational p/q is qt-p, and
by monicity q = 1.
Now the useful thing is that the set of algebraic integers is closed
under sums and products. ie, if x & y are algebraic integers, then so are
x+y & xy. [I won't prove that here. It's a standard result given in
group representation theory, since all group characters are algebraic integers,
and in particular is used to prove Burnside's p-alpha-q-beta theorem on
the non-existence of simple groups with this order.]
How is this relevant to our problem? Well, by induction it's obvious
that each a[n] is rational. Suppose that we were able to find an explicit
formula for a[n] as for instance:
sum(j=1...J) c_j*(�_j)^n
where c_j & �_j are fixed algebraic integers. Then by the above, a[n] is
an algebraic integer; we know it's rational, so it's an integer. This idea
of expressing a[n] in such a way finds additional support from .1's
number-crunching. As .2 observed, the sequence does seem to be undergoing
exponential growth, at least.
So, can we find such a formula for a[n]? Our constraints are:
a[n]*a[n-6] - a[n-1]*a[n-5] - a[n-2]*a[n-4] * a[n-3]� (for n >= 6)
a[n] = 1, for n = 0,1,2,3,4,5.
We'll deal with the first one first, assuming that the second merely
enables us to fix the parameters. So, we want:
sum(j,j') c_j*c_j'*(�_j*�_j')^(n-3) * [x�-x�-x-1] = 0, for all n >= 6.
where x = x(j,j') = �_j/�_j'.
= -2*sum(j) c_j�*(�_j)^(2n-6)
+ sum(j>j') c_j*c_j'*(�_j*�_j')^(n-3) * [x�-x�-x-2 - 1/x - 1/x� + 1/x�]
I have taken this further, but I have not found the correct channel
yet. It's clearly a question of choosing combinations of �_j such that the
sum above vanishes, but one wants to do it in such a way that it leaves
enough flexibility for a[little] constraints to be satified.
Since there is a fair amount of choice, I think it's right that I post
this for criticism now, and others might find it useful.
Regards,
Andrew.
|
| > So what is the name of the curve swept out by the
> base ten representations in .-1? :-) :-)
Seriously, I think it's a quadratic. It's obvious from .1 that
a[n] grows faster than exponential, and if you try putting e^n in the
recurrence, you don't get anywhere. Note however, that if a[n] satisfies
the recurrence (but not the boundary conditions), then so does a[n]*k*e^(l*n)
for any constants k & l.
However, the recurrence *does* solve (again, forgetting the
boundary conditions) when a[n] = g^(�n�), where g is a solution of a certain
(monic) poly of degree 9. Four roots are easily seen to be the fourth
roots of -1, and this leaves us with a quintic:
t^5 - t - 1
This has a root, g, between 1 & 2, and I suggest that the long term
behaviour of a[n] is therefore:
e^(�n�*ln(g) + l*n + k)
for some k & l. Taking the log of this gives us the quadratic curve of .1.
Whilst looking for other solutions to the recurrence, I stumbled
across:
a[n] = �^n + (i�)^n - (-�)^n - (-i�)^n
which works fine for all complex �. However, it is only exponential, so
would not be enough to give us the growth we need.
A similar argument says that the formula I proposed in -.1, could
never do the job, because it's only exponential. And this tells us that
we have no hope that a linear function a[n] = sum(j=1...6)c_j*a[n-j] could
work, since that would give us at best an exponential growth (rate given
by the largest eigenvalue of the transformation matrix).
A priori, it wasn't obvious (to me, anyway) that there wasn't such
a linear recurrence available. For instance, the familiar Fibonacci is
linear, but has the initially unpromising recurrence:
f[n]*f[n-2] - f[n-1]� = �1
So, in summary, I haven't solved this problem yet.
|