parity of integer sequences

[David Wilson]

----- Original Message -----
From: <jeremy.gardiner at btinternet.com>
To: <seqfan at ext.jussieu.fr>
Sent: Wednesday, July 31, 2002 5:36 AM
Subject: parity of integer sequences


> I was thinking about how to categorise integer sequences and I wonder how
useful it would be if the on-line encyclopaedia were to contain a reference
to the parity representation for each sequence?
>
> Many of the entries would be all odd, all even or simply alternating
parity but there are also many more interesting examples such as 1010010001
... (A023531), however there is no easy way of data mining these without
calculating parity for each sequence.
>
> Of course parity is not the only way to categorise integer sequences but
it is an important property.
>
> Perhaps other people have a view on this?

I agree that parity searches would be useful, however, I disagree with
adding additional parity sequence fields to the EIS.

The EIS already has two potential sets of sequence fields for each entry,
the unsigned sequence (%STU) and the signed sequence (%VWX).  Adding
a parity sequence would create additional fields, bloating the database
further.
The logical extreme, adding a new set of fields to each EIS entry for each
search criterion, is clearly silly.

I would incline in the other direction, that of decreasing the bulk of the
EIS
database and increasing its search capabilities.  Optimally, each EIS entry
would contain only the signed sequence.  The search criteria would consist
of a lookup sequence and a transform function.

The lookup sequence would be an extended version of the current lookup
sequence. I would recommend adding

   ? to match a single unknown element
   * to match zero or more unknown elements
   + to match one or more unknown elments
   ^ to match the beginning of sequence

Thus

   13,125 matches sequences containing adjacent elements 13,125
   ^13,125 matches sequences starting with 13,125
   13,?,125 matches sequences containing 13 followed by 125 with one
intervening element.
   13,*,125 matches sequence in which 13 occurs prior to 125.

The transform function is a function in the variable "n" applied prior to
matching the lookup.
Thus, if the transform function were "n mod 2", and the lookup sequence were
0,1,1,0,0,1,1,0,0,1,1,0 we might would match the triangular numbers.  I
leave the
expression syntax undefined, but MMa expressions (for their math
capabilities) and
Perl expressions (for their pattern matching capabilities) spring to mind.

This mechanism would provide fairly flexible search capabilities.  We could
use %STU
to store the signed sequence, eliminate %VWX, and use "abs(n)" function to
search the
unsigned sequences.  I would recommend generating indexes for searches on
various
common transform functions such as "n", "abs(n)", "n mod 2", etc.  Searches
on less
common transform functions would necessarily be slower, but possible.