[seqfan] Re: A new sequence
Richard Guy
rkg at cpsc.ucalgary.ca
Thu Feb 7 00:50:49 CET 2013
Dear all,
Many thanks to several who replied.
To clarify my earlier message, and answer some questions
I first say that all the sequences I sent or mentioned are
divisibility sequences, that is, if m divides n, then
a(m) divides a(n). The exceptions are the sequence (in which
a(2) = 20 was misprinted as 2)
(-1), 0, 1, 20, 595, 19720, 667029, 22642620, 769085031,
26125682960, 887500839785, ...
and the derived sequence of gcds of three consecutive terms:
1, 1, 5, 17, 29, 33, 169, 577, 985, ..., which I don't yet
understand.
Of the other sequences, the ones starting
(-1), 0, 1, 6, ... and (-1), 0, 1, 34, ... ARE in OEIS.
They are divisibility sequences with a SECOND ORDER linear
recurrence. I had omitted to notice that the polynomial
x^4 - 40x^3 + 206x^2 - 40x + 1 factors as
(x^2 - 6x + 1)(x^2 -34x + 1) so that these two sequences are
Lucas sequences, with recurrence relations
a(n) = 6a(n-1) - a(n-2) and a(n) = 34a(n-1) - a(n-2).
Their roots are 3 +/- 2*sqrt(2) and 17 +/- 12*sqrt(2)
so that there are `Binet-type' formulas (though such
formulas were know to Euler and de Moivre).
Note that OEIS has a good deal to say about these, but
doesn't say that they are divisibility sequences. Note
that A029547 and A091761 are the same sequence. I never
did understand `offset', but the second sequence is
really an `odd' sequence
..., -1155, -34, -1, 0, 1, 34, 1155, 39236, 1332869, ...
The thousand or so divisibility sequences that I
mentioned are any number of second order Lucas
sequences, together with the fourth order ones generated by
x^4 - Px^3 + (2Q+R)x^2 - PQx + Q^2 whose discriminant
is E * D^2 * Q^2 where D = P^2 - 4R and E = (4Q + R)^2 - 4QP^2
The first few terms are a(0) = 0, 1, P, P^2 - 3Q - R, ...
a(-n) = a(n)/Q^n. Incidentally, these include the numbers of points
on elliptic curves over the finite fields of order q^n, n > 0. I
believe that there is just one such specimen in OEIS, though I
forget whether elliptic curves are mentioned.
(see Williams & Guy, Some fourth order linear divisibility
sequences, Internat. J. Number Theory, 7, No.~5 (2011) 1255--1277.
That's more than enough, though much more coule be said! R.
On Tue, 5 Feb 2013, Maximilian Hasler wrote:
>> Wikipedia says a "characteristic polynomial" is connected to a matrix.
>> Do you use the matrix to generate the sequence (and of so, how)?
>
> Here, that one is meant:
>
> http://en.wikipedia.org/wiki/Recurrence_relation#Linear_homogeneous_recurrence_relations_with_constant_coefficients
>
> although both notions can be linked...
>
>> I guess the more general question is: Do you have software that can
>> automatically generate the 1000 or so divisibility sequences?
>
> Here, a script which appends n values to
> the r initial values of a lin.rec. of order r,
> already helps:
>
> (PARI)
> {linrec(c,a,n=10)=for(k=1,n,a=concat(a,-vecextract(a,Str(-#c,".."))*c~));a}
>
> linrec([1,-40,206,-40],[1,0,1,48])
>
> => [1, 0, 1, 48, 1713, 58672, 1995921, 67818880, 2303940641,
> 78266714528, 2658767568353, 90319849348112, 3068216219484241,...]
> \\ NOT IN OEIS ;
> but since highly composite, it is quite probable that it is the
> product of two or more sequences in the OEIS
>
> gp > linrec([1,-40,206,-40],[-1,0,1,6])
> =>
> -1, 0, 1, 6, 35, 204, 1189, 6930, 40391, 235416, 1372105, 7997214,
> 46611179, 271669860,...
> \\ this is A001109
>
> gp > linrec([1,-40,206,-40],[-1,0,1,34])
> =>
> -1, 0, 1, 34, 1155, 39236, 1332869, 45278310, 1538129671, 52251130504,
> 1775000307465, 60297759323306, ...
>
> \\this is A091761 (from the 0 on) resp. A029547 (from the 1 on)
>
> gp > linrec([1,-40,206,-40],[-1,0,1,48])
> ms.
> -1, 0, 1, 48, 1715, 58752, 1998709, 67914000, 2307174311, 78376578048,
> 2662499775145, 90446634986352,
>
> \\ NOT in the OEIS, but same remark as above.
>
> Maximilian
>
More information about the SeqFan
mailing list