[seqfan] Re: [math-fun] Divisibility sequences in OEIS.
rwg at sdf.lonestar.org
rwg at sdf.lonestar.org
Tue Dec 15 02:58:04 CET 2009
This is my fifth attempt to reply from laughably flaky Squirrelmail. (Each
time with loss of draft and recipient list, and several minutes of unresponsiveness.)
Apologies for any duplication.
> 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
More information about the SeqFan
mailing list