[seqfan] Fwd: Re: A new sequence

[Robert Munafo]

Thanks everyone for the clarifications and help with terminology.

I had already written a lot about the Horadam sequences [1], (and
thus 2nd-order Lucas sequences without calling them such), and cataloged
many of them. [2]

I've just added tags to my sequence catalog indicating which ones are Lucas
sequences, and I've also extended the range of parameters P and Q to allow
a few more into my catalog.

I've started manually checking them against the OEIS to add links to OEIS
where possible. I generate recurrence sequences in order of increasing
"Kolmogorov complexity", and that's the order in which I'm checking them
against OEIS.

Of the "simplest" 33 Lucas sequences, 27 are in OEIS (the 6 "missing" ones
have a zero or negative P coefficient, but the converse isn't true). Those
27
are: A077957, A108520, A000032, A087204, A009545, A007395, A002203,
A000027/A001477, A000045, A000079, A000129, A002605, A039834, A001045,
A001906, A001607,
A181983, A077925, A006190, A077966, A199572, A006130,
A182228, A214733, A107920, A077985, and A106852.

I have another set of 50 or so with somewhat larger P and Q values, that
I'll try to look at soon.

On Wed, Feb 6, 2013 at 6:50 PM, Richard Guy <rkg at cpsc.ucalgary.ca> wrote:

> [...]
> The thousand or so divisibility sequences that I
> mentioned are any number of second order Lucas
> sequences,


If we look at 2nd order Lucas sequences, and if we take the 1000 or so with
the smallest P and Q coefficients, then P and Q could each range from about
-10 to 10. I'm including the Lucas V sequences, which do not have the
divisibility property, because it only seems fair (-:

Instead of limiting parameters separately, I prefer to limit the aggregate
complexity, so in this case I'd limit |P+Q|, which is the absolute value of
P plus Q. For example we could include U(12,-5) at the expense of
U(10,-10). I'm not sure how many of these are not interesting enough to add
to OEIS, but let's say maybe half, so that brings it down to 500 or so
sequences, using up half our target of 1000.

To check that many sequences I'll have to automatically search my local
copy of the OEIS. It's an old version from 2010, but I'm sure that'll be
good enough for this project.


> together with the fourth order ones generated by
>
> x^4 - Px^3 + (2Q+R)x^2 - PQx + Q^2

 [...]

The first few terms are  a(0) = 0, 1, P, P^2 - 3Q - R, ...


Once we add the third parameter, the three coefficients would need to be
more constrained to keep it around 1000 total. Using your example
polynomial:

   x^4 - 40x^3 + 206x^2 - 40x + 1

I get the values P=40, Q=1, R=204; and the discriminant is 22198616064
(with D=776, E=36864).

If the P,Q, and R are going to be as large in magnitude as this R, then
we'd have millions of candidate sequences. So clearly some more constraints
are required to get it down to about 1000.

[1] mrob.com/pub/math/seq-linrec2.html#lucas

[2] mrob.com/pub/math/MCS.html

On Wed, Feb 6, 2013 at 6:50 PM, Richard Guy <rkg at cpsc.ucalgary.ca> wrote:

> [...]
> 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.
>

-- 
  Robert Munafo  --  mrob.com
  Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 -
mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com