[seqfan] F Numbers

[franktaw at netscape.net]

I would like to propose a major enhancement to the OEIS.
This is intended to deal with discrete functions that do not
fit neatly into the OEIS format.  This includes functions
whose domain and/or range consists of rational numbers,
Gaussian (complex) integers, sequences (including
partitions), polynomials, and perhaps other similar objects.
It would also include sequences whose domain is integers,
but not all consecutive integers starting at a specified value.

These functions would be entered in a fashion similar to
the way OEIS entries are now entered, but they would
not have any values or offsets entered.  Instead, they
would have a definition line.  The values would be
computed by the system (either as requested or in
advance; this is an implementation issue).

I propose that these function be given F numbers
(starting with F000001) instead of the A numbers used
for the main body of the OEIS.  When appropriate, the
system would generate the equivalent of b-files for them
(call these f-files), reading the source b-files/f-files as
needed.

Possible definition lines would include:

A#B

(Here and in the following, A and B are other sequence/
function references.  Note that when referencing signed
OEIS sequences, it is always the signed values that are
referenced.)  In this case, B must be a sequence of
non-negative integers from the OEIS; A must be a
sequence, but its values might be either integers or
other discrete values.  Typically, A will have the "tabf"
keyword.  The result will be a sequence of finite
sequences (enclosed, perhaps, in square brackets), each
representing one row of the table; B gives the row
lengths.  The resulting offset will be the offset of B.

A/B

A and B should here be integer-valued, usually with the
"frac" keyword; the result is a sequence of rational
numbers with sequence A as numerators and B as
denominators.  A and B should have the same offset.

A+Bi

Similar to the previous case, although rational values
would also be allowed.  The result is a sequence of
complex numbers (always rational).

A:B

A and B should both be indexed by integers, with
the same offset.  The result is a function, with the
A values forming the domain, and the B values the
range.  Entries of this type would not have values
directly in the entry; instead, an f-file would always
be generated, and the values placed there.

Ax^k

Here k is an integer, usually zero or one.  A must be
a function whose values are sequences of numbers.
The result is a sequence of polynomials, with k being
the exponent corresponding to the first term in each
sequence.  If A  is a sequence, the result will be a
sequence with the same offset.

A|B

A and B must be sequences, normally with the same
kind of values.  The result is a function with
f(n) = A(n) and f(-n) = B(n).  The values are stored
in the f-file in the order 0,1,-1,2,-2,3,-3,....  Note
that it is quite legal for the offset of A to be 1 (or
even larger; likewise for the offset of B to be
greater than 1), in which case the function will be
undefined at 0 (and perhaps some adjacent values).

A_1,A_2,...,A_k

Each value is a k-tuple (k>1), with the values taken
from the inputs.  These must all have the same domain.

-----
Searching

Searching the function database should be fully
integrated with searching the OEIS.  Sequences
with non-integer values should be searchable in the
usual way, so that one might search for
"2+i,3+4i" or "1/2,2/3,1/2,4/5,1/3".

To  handle functions that are not sequential, an
enhancement to the search syntax is proposed:
allow searching for targets in the form key->value
(or possibly key:value).  This is applicable to existing
sequences, so that a search for "5->1024" would
match all sequences with a(5)=1024.  Supporting
this would require the search setup program to
take into account the offset of the sequence, as
well as to scan the b-file, when one exists.

-----
Transforms

In order to avoid having to add trivial variants of
existing sequences to the database, a few simple
transforms should be specifiable when referencing
sequences in the definition lines of functions.  I
would propose specifying these with prefixes to
the sequence.  In particular, I would support:

D

Drop a value from the front of the sequence, and
increment the offset (so that the offsets of the
remaining values stay the same.  For example,
DA001477 would be synonymous with A000027.

I(v)

The inverse of the previous operation; add a new
initial value and decrement the offset.  Thus
I(0)A000027 is equivalent to A001477.

This could perhaps be extended to allow
I(x->y), to add one specific value to a function.

L

Left shift: decrement the offset.

R

Right shift: increment the offset.

I don't think any but these completely trivial
transforms should be supported.  Even a bisection
ought to be done with a separate sequence.

-----
Issues

I have debated whether a distinction should be
made between functions whose codomain is
finite sequences, and those where it is finite
sets.  One problem with making such a distinction
is that it is not always clear cut: should every
function whose values are always strictly increasing
(or decreasing) sequences be considered to be
a function to sets?  How would you know which
to search for?

Sequence in context: I don't see any way to
do this for these functions, with the sole
exception of sequences of rationals.  I don't
think it would hurt to simply exclude this
functionality from these functions.  This implies
that the offset for sequences in this portion of
the database will be a single integer; and for
more general functions, there will be no offset.

For rational number sequences, must the source
sequences be relatively prime?  Or do we let
the system reduce them?  A related issue: is the
fraction 1/0 to be allowed?  (There is at least
one sequence in the database with the "frac"
keyword, intended as denominators, which
contains a zero.)

More definition types can obviously be added,
although this should be minimized to keep
things simple for the implementation.  One
possibility is A+Bsqrt(k), with k a constant.

It would be useful to support graphing for
functions that have both domain and codomain
real numbers (integers or rationals).

-----
Examples

A000040:A001918 Function from primes to their
least primitive roots.

A036036[A036043] List of partitions in
Abramowitz and Stegun order.

A076512/A109395 Fraction of numbers less than
n that are relatively prime to n.

A001477|A000027 The absolute value function
on the integers.

-----
Errors

There are a number of errors possible in entering
these functions.  The following is not intended
as a complete list:

Invalid definition: the definition entered cannot
be recognized as any of the legal types.

Wrong type of sequence: the above definition
types state certain constraints on the referenced
sequences.  The input process must check these
conditions and report an error if violated.

Duplicate values: for the A:B definition type, the
values of sequence A must all be distinct.  An
error must be reported if they are not.  (Of
course, only the entered values can be checked;
there is no way to verify that duplication does not
occur later in the sequence.)

Circular reference: when an existing function is
being changed, it is possible to set up a circular
reference, where the sequence directly or
indirectly references itself.  This must be
prevented.

-----
Implementation

If it is agreed that this is a useful direction for the
OEIS, the next question becomes how to get it
implemented.  I don't know what resources might
be available for this, nor when they might be
available.

I am sure that if never proposed, it will never be
implemented.

Franklin T. Adams-Watters