A094943 / A sequence generated from a semi-magic square

[Gottfried Helms]

Hi Alec -

Am 25.08.05 22:32 schrieb Alec Mihailovs:

> "Alec Mihailovs" <alec at mihailovs.com> wrote,
> 
>>It is easier to use recurrences,
>>
>>{a(n+3)=3*a(n+2)+15*a(n+1)+18*a(n), a(0) = 1, a(1) = 13, a(2) = 72}
>>
>>for A094943 and
>>
>>{a(n+4)=4*a(n+3)+44*a(n+2)+144*a(n+1)+160*a(n), a(0) = 1, a(1) = 26, a(2) 
>>= 256, a(3) = 2472}
>>
>>for the 4x4 matrix generated sequence.
> 
Yes, I knew that there are recurrences of this type: that was
the intention of my matrices. It is a more complex form
of the fibonacci-like-recurrences, and the values are no more
multiplicative with n; what I'm trying to see is, how one could
put up an analoguous table of factors (and primitive factors)
as it is done in the fibonacci/lucas-sequences and see, what
rules are there concerning occurences of prime-factors.

My problem was to find the coefficients of the nominators, but...
> 
> By the way, the coefficients of the recurrences are the coefficients of the 
> characteristic polynomials of the matrices,
> 
> They also appear in the denominators of the generating functions,
>                                         2
>                          1 + 10 x + 18 x
>                    - ------------------------,
>                           2                 3
>                      -15 x  + 1 - 3 x - 18 x
> 
>                                     2        3
>                     1 + 22 x + 108 x  + 160 x
>                ---------------------------------- .
>                      2                  4        3
>                 -44 x  + 1 - 4 x - 160 x  - 144 x
> 
... in your second post you gave already a useful hint - thanks!
Unfortunately I never got a clue how to deal with generating functions,
although I often read hymns about the versatility of such functions ;-)
Well - I should look at this subject more seriously...


Meanwhile I got some other simplifications:
let t be the rotation, which rotates the matrix A
of order 3 (it works analoguous with other orders)
      A:
     	|        1         3         2 |
     	|        2         1         3 |
     	|        3         2         1 |

to the principal-axis-position, then I get with the orthogonal
similarity transformation t -

    A1 = t'*A*t

      A1 :
     	|        6         0         0 |
     	|        0        -2         1 |
     	|        0        -1        -2 |

this to the power of 3:

      A1^3
     	|      216         0         0 |
     	|        0         0         5 |
     	|        0        -5         0 |

which is one 4'th root of the diagonal matrix:

      A1^(3*4) :
     	| 2176782336         0         0 |
     	|        0       729         0 |
     	|        0         0       729 |

and this is the (3*2)'th-power of

      R2 :
     	|       36         0         0 |
     	|        0         3         0 |
     	|        0         0         3 |

The similarity-re-transformation leads to
      A2 = t * R2 * t'
     	|       14        11        11 |
     	|       11        14        11 |
     	|       11        11        14 |

Don't know currently, for what this is worth; your hint to the
direction of generating functions and the characteristic
polynomials may be of more value here.

Some observations in the matrices of other orders:
for order n:
 *  there seems to be some exploitable periodicity of period
    4*n, possibly a multiplicative table of factors can be
    created on that basis,

 *       A2[1,1]  is sum(i^2)    (i = 1..n)

 * rowsum(A2[1])  is (sum(i))^2  (i = 1..n)

 * primes n need A1^(4*n) to diagonalize, composite n seem to need
   lower powers, so for such numbers an exploitable periodicity
   for the table of factors may be less, as it is nicely in that
   of the order 2.


Gottfried Helms