[seqfan] Re: A new sequence

[Richard Guy]

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
>