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

[Richard Guy]

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
> _______________________________________________
> math-fun mailing list
> math-fun at mailman.xmission.com
> http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun