[seqfan] Divisibility sequences in OEIS.

[Richard Guy]

Apologies for multiple copies of this
rather long message, but I'm keen to find
a few potential editors for the following
scheme.  If you are able to help, send to
me personally, not to bother the rest
of the lists.  I can then send you
attachments of even longer files, and
we can divvy up the work so that there
is only enough duplication to ensure
checking.

Here is the preface to a file:

This is a list, in OEIS numerical order, of
divisibility sequences.  The suggestion
is that these should be given the codeword ``div''
(or ``divi'' if codewords all have four letters).
Where this is not already done, it should be remarked
that they are divisibility sequences.  Many are
values of Chebyshev polynomials: for these the polynomial
should be quoted.  Those which satisfy recurrence relations
should include the recurrence and the generating function.
A `closed' formula is also always possible.

Divisibility sequences satisfying recurrence relations
of order 4 or higher may contain prime divisors with more
than one rank of apparition.  At least the first few examples
of this should be noted.  Many higher order sequences
factor into ones of lower order: this should be noted.

Check list for div seqs in (and not yet in) OEIS:

1.  Is it stated that it's a divisibility seq ?
Should there be a keyword, say `divi' ?

2.  Check the offset. The ``right'' offset is
$a(0)=0$, but there may be a good reason for
having two entries with different offsets.
For example, the Fibonacci sequence would normally
be given as $a(0)=0$, 1, 1, 2, 3, 5, \ldots,
but it often manifests itself as $a(0)=1$,
1, 2, 3, 5, \ldots, e.g., the number of ways
of packing $n$ dominoes in a $2\times n$ box.

3.  If a divisibility sequence is multiplied or
divided through by an integer, it remains a
divisibility sequence, so, in order to be sure
of locating all manifestations, if a (the)
``natural'' occurrence of the sequence has $a(1)=k$,
then the division by $k$, starting $a(0)=0$,
$a(1)=1$ should also be given, and often the
versions with $a(1)=2$, 3, etc., up to a point,
should be given as well.

4.  Is there a recurrence relation ?  Note that,
paradoxically, there may be more than one, and
of different orders, because of factorization.

5.  Is the generating function given ?

6.  Is there a ``closed'' formula of type
$A\alpha^n+B\beta^n+C\gamma^n+\cdots$ ?

7.  Does the sequence factor into recurring
sequences of lower order (which are not
necessarily divisibility sequences) over the
integers ?  over other number fields ?

8.  Are the terms values of one or more
Chebyshev polynomials ?

9.  Note that every second term forms a divisibility
sequence which may be worthy of mention in its
own right.  Similarly for every third term, every
fourth term, \ldots .

10.  Numbertheoretic properties, e.g., the rank(s)
of apparition of primes, may be worthy of note.  In
sequences of order $2^k$ a prime may have as many
as $k$ ranks of apparition.  Second order linear
recurrences are often numerators or denominators
of convergents to continued fractions of quadratic
irrationals.  Many 2nd order sequences are related
to solutions of Bramahgupta-Bhaskara-Pell equations

11.  Cross-references to other sequences, especially
those arising from 2., 3., 6., 8., \& 9.\ above.

12.  Does the sequence arise ``in real life'' as
the number of points on an elliptic curve; or the
number of perfect matchings in a family of graphs;
or the numer of spanning trees (sometimes called
the `complexity') thereof, or in other
ways?  Note that perfect matchings are also called
dimer problems or domino tilings or packings.

13.  If it's a second order sequence, then I
believe that $a_n=F_{rn}/s$ for some $(r,s)$,
where $F_n$ is the $n$\,th Fibonacci number.
If so, then $r$ and $s$ should be given.

14.  Other things that I've missed.

For a start, compare and contrast the descriptions of
A010892, A000027, A001906, A001353, A004254, A001109,
A004187, A001090, A018913, A004189, A004190, A004191,
A078362, A007655, A078364, A077412, A078366, A049660,
A078368, A075843, A092449, A077421, A097778, A077423,
A097780, A097309, A097781, A097311, A097782, A097313,
and note that the varied properties that are
mentioned are in fact shared by ALL of them, though
rarely are more than one or two mentioned.

When, as with the above examples, a sequence belongs to
a family, it would be good to give the family a name,
and say which member it is.

The companion sequence of sequences is
A000045, A000129, A006190, A001076, A052918, A005668,
A054413, A041025, A099371, A041041, A049666, A041061,
A140455, A041085, A154597, A041113, missing, A041145,
missing, A041181, missing, A041221, missing, A041265,
missing, A041313, missing, A041365, A049667, A041421,
missing, A041481, missing, A041545, missing, A041613,
missing, A041685, missing, A041761, missing, A041841,
missing, A041925, missing, A042013, missing, A042105,
missing, A042201, missing, A042301, missing, A042405,
missing, A042513, missing, A042625, missing, A042741,

[perhaps itself a more interesting sequence than many
that are submitted?]

The major interest of divisibility sequences is the
factorization of the terms.  It would be good to have
this, perhaps on a separate page.  In this sense, all
of the 'Cunningham project' should be accessible
via OEIS.

Thankyou for your patience, if you've got as
far as this.      R.