[seqfan] Re: [math-fun] Divisibility sequences in OEIS.

[rwg at sdf.lonestar.org]

This is my second attempt to reply from laughably flaky Squirrelmail.
Sorry for any repetitions.
> AhA!!  Well done Bill!  At last someone is begining to
> see the light.  But one doesn't need to be so esoteric
> as to go into elliptic divisibility (= Somos??) sequences.
> You can get all second order linear recurrences (which are
> divisibility sequences if you take a(0)=0) by tipping up
> Omar Khayyam's triangle (see A011973 in OEIS):
>                                              (0)
>                                               1
>                                            1
>                                         1     1
>                                      1     2
>                                   1     3     1
>                                1     4     3
>                             1     5     6     1
>                          1     6    10     4
>                       1     7    15    10     1
>                    1     8    21    20     5
>                 1     9    28    35    15     1
>              1    10    36    56    35     6
>           1    11    45    84    70    21     1
>        ..   ..    ..    ..    ..    ..    ..
>
> and then get a TWO-parameter family by multiplying
> the columns from right to left by a^0, a^1, a^2, ...
> and the left-falling diagonals downwards by
> b^0, b^1, b^2, ..., giving the sequence, which
> I'll call S(a,b), of polynomials
>
> 0, 1, a, a^2 + b, a^3 + 2ab, a^4 + 3a^2* b + b^2,
> a^5 + 4a^3*b + b^2, a^6 + 5a^4*b + 6a^2*b^2 + b^3,
> a^7 + 6a^5*b + 10a^3*b^2 + 4b^3, ...
>
> which factor into algebraic & primitive parts,
> just like Bill's.  I believe that  S(2x,-1)  are
> (one sort of) Chebyshev polynomials.
>
> The lists that I gave earlier were for  S(k,1)
> and  S(k,-1).  All the sequences for all  a & b
> have almost all of the properties mentioned in
> my checklist, and people are beginning to add
> more.
>
> Every second term of the sequence is  S(a^2+2b,-b^2),
> every third term is  S(a^3+3ab,b^3), etc.
>
> Note that  S(-a,b) = (-1)^(n+1) * S(a,b).
>
> Everyone knows that  S(1,1)  is the Fibs, but
> it may not be so well known that  S(4,1)  is
> F(3n)/2, for example.  Can anyone state the
> theorem behind item 13 in the checklist?
>
> Just in case there's anyone rueing having deleted
> my earlier message, I'd be happy to resend to them
> personally.  I don't want to bother the whole list,
> but I would like to enlist help from a few keen
> types to do the enormous amount of spring cleaning
> that needs to be done.
>
> As another example, here is a list of the rather
> motley collection of present titles of  S(k,-2):
>
> ......
> k=-3 missing  (-1)^(n+1) * S(3,-2)
> k=-2 A108520  see  k=2  below.
> k=-1 A001607  a(n)=-a(n-1)-2a(n-2)
> k=0  missing  0,1,0,-2,0,4,0,-8,0,16,0,...
> k=1  A107920  Lucas & Lehmer numbers ...
> k=2  missing, though is (-1)^(n+1) * A108520,
>       which is Expansion of 1/(1+2x+2x^2)
> k=3) A000225  Mersenne numbers, repeated as
> k=3) A168604  No. of ways of partitioning the
>       multiset ...
> k=4  A007070  a(n)=4a(n-1)-2a(n-2)
> k=5  A107839  a(n)=5a(n-1)-2a(n-2),a(0)=1,a(1)=5
>       (though these initial values are ``wrong'')
>       [cf. A005824 and A109165 which each
>       interweave this seq with another.  Also
>       A159289, which has curious initial values.]
> k=6  A154244  a(n)=((3+sqrt7)^n-(3-sqrt7)^n)/2*sqrt7
> k=7  missing from here on.
> ...........
>
> Thankyou again for your patience, if you got this
> far.    R.
>
> On Sun, 13 Dec 2009, rwg at sdf.lonestar.org wrote:
>
>> NJAS> Here is the preface to a file:
>>>
>>> This is a list, in OEIS numerical order, of
>>> divisibility sequences.
>>
>> I confess to having looked up only a few of the 60-odd sequences, but it
>> may come as news to some that there are elliptic divisibility sequences
>> of polynomials.  E.g.
>> s[1]:s[2]:1,s[3]:-1,s[4]:x,s[n+4] :=(s[n+3]*s[n+1] + s[n+2]^2)/s[n]
>> gives
>> 1 1
>> 2 1
>> 3 - 1
>> 4 x
>> 5 x + 1
>>   2
>> 6 x  - x - 1
>>      3
>> 7 - (x  + x + 1)
>> 8 - x (3 x + 2)
>>   5    4      2
>> 9 x  - x  + 3 x  + 3 x + 1
>>               5    4      3      2
>> 10 - (x + 1) (x  - x  + 3 x  + 2 x  - 2 x - 1)
>>       7      6      5      4      3      2
>> 11 - (x  - 2 x  + 3 x  + 9 x  + 5 x  + 3 x  + 3 x + 1)
>>         2            6      4      3      2
>> 12 - x (x  - x - 1) (x  + 2 x  + 5 x  + 9 x  + 9 x + 3)
>> . . .
>> where s[<prime>] is irreducible, etc.
>> --rwg

(Sorry about ascribing your words to Neil.)
Note that these polynomials satisfy a stronger condition than
gcd(s[a],s[b]) = s[gcd(a,b)], namely a|n -> s[a]|s[n].  E.g.,

     2            5    4      2
18 (x  - x - 1) (x  - x  + 3 x  + 3 x + 1)

   13    12      11       10       9       8        7        6       5
 (x   + x   + 7 x   + 19 x   + 25 x  + 78 x  + 133 x  + 108 x  + 79 x

       4       3      2
 + 65 x  + 24 x  - 6 x  - 6 x - 1)
       22      21       20      19       18        17        16
19 - (x   - 5 x   + 15 x   + 4 x   - 20 x   + 108 x   + 162 x

       15        14        13        12        11        10        9
 + 89 x   + 294 x   + 580 x   + 614 x   + 378 x   - 179 x   - 255 x

        8         7         6         5        4        3       2
 + 870 x  + 2011 x  + 1897 x  + 1044 x  + 405 x  + 140 x  + 45 x

 + 10 x + 1)
               5    4      3      2
20 x (x + 1) (x  - x  + 3 x  + 2 x  - 2 x - 1)

   18      17      16      15    14       13       12       11
 (x   - 3 x   + 4 x   + 3 x   + x   - 26 x   - 12 x   + 71 x

        10        9        8        7        6        5        4
 - 118 x   - 469 x  - 481 x  - 382 x  - 554 x  - 753 x  - 688 x

        3        2
 - 430 x  - 180 x  - 45 x - 5).

I have been calling these "strong divisibility sequences".  What's the
accepted term?

The degree of these polynomials,
0,0,0,1,1,2,3,2,5,6,7,9,10,12,14,14,18,..., grows nonlinearly, in fact as
eight interlaced quadratic progressions.  This offers a good OEIS signature,
but how to tabulate the actual, jagged, nontriangular coefficient array?
--rwg