[seqfan] Remarks on lists and offsets

[Peter Luschny]

The recently asked question from John shows some of the
confusion that keeps cropping up in the context of the choice
of the offset. The wiki entry [1] is the official description
of the term 'offset' in the context of the OEIS. Here I would
like to give a more personal view. It might help to understand
this quantity better but I cannot rule out that it will have
precisely the opposite effect.

---

    The setup:
    Data:      a,     b,     c,     d,   ...
    Indices: (0+o), (1+o), (2+o), (3+o), ...
    where o denotes the offset.

How to choose the right offset? As a first approach, ask
the question:

   Is the sequence described by a simple formula (function)
   or by some description (predicate)?

* Case formula/function:

The offset is determined by taking the minimum of the formula's
maximal range of validity restricted to nonnegative integers.
Corner cases should be given special attention. The validity
of the argument '0' for the function should be checked and
added to the range if valid. The convention that an empty sum
is 0 should be taken into account.

* Case description/predicate:

The offset is 1. By OEIS convention. The sequence is then
called a list. What often confuses people in this case is
that they believe that the predicate's argument range is
{1,2, ...}. This is wrong. There is nothing implied about
the range of the predicate by the offset in this case.

---

A typical case which induces some kind of confusion is when
the offset = 1 and the first term = 0. Let's trace this more
formally (with Maple). The predicate 'is_a' determines if 'n'
is an element of 'a' and returns accordingly 'true' or 'false':

    a := [seq(`if`(is_a(n), n, NULL), n = 0..100)];
    a[1]; a[2]; a[3]; a[4]; ...

This feels like a kind of cognitive dissonance. The evaluation
of the predicate starts at n = 0 but the list starts with a[1]!
But this magic works -- in Maple! Because Maple's lists are
1-based. It does not necessarily work in other computer languages.
For instance a list in Sage/Python is 0-based and here you
have to work around this difference if you really wish to
comply with the OEIS convention.

(I have long suspected that the list-offset=1 convention in
the OEIS might be influenced by Neil's preferred use of Maple.)

---

Don't expect the above hints to be without exceptions. There is
this famous sequence where the inventor of the taxonomy writes:
"Although this is a list, and lists normally have offset 1,
it seems better to make an exception in this case."

More general, a sequence can have both a simple formula and
be described by a simple predicate. In such cases, expect
eternal strife and discord. I know sequences where the offset
has been changed many times between 0 and 1 for this reason.
Which in consequence introduced errors in the related formulas.

---

Here is an example that I recently discussed with Michel
Dekking [2] in the editor's room:

The predicate is: 'k is a nonnegative integer with an even
number of 1's in the binary expansion.'

Maple: is_a := n -> add(k, k in convert(n, base, 2))::even:

Two of the following sequences have offset 0 and two have
offset 1. Homework: Explain which ones and why. [4]

seq(`if`(is_a(n), n, NULL), n=0..20); 0, 3, 5, 6, 9, 10, 12,  ...
seq(`if`(is_a(n), NULL, n), n=0..20); 1, 2, 4, 7, 8, 11, 13,  ...
seq(`if`(is_a(n), 1,    0), n=0..20); 1, 0, 0, 1, 0, 1, 1, 0, ...
seq(`if`(is_a(n), 0,    1), n=0..20); 0, 1, 1, 0, 1, 0, 0, 1, ...

Bonus points: Add the first two sequences termwise. Which
offset has this compound sequence? The same as the individual
ones? And if not, is this justified?

---

One might say that you don't have to like conventions, it's
enough to stick to them. But they make little sense if they
can't be followed consistently. How does the list convention
interact with mathematical operations? Can you add lists
(termwise) like you can you add sequences? Or is this like
counting apples and pears together? Assuming the result makes
sense (as in the example above), is it again a list, or (as
in the example above) rather a sequence?

    << We see with concern: the curtain is falling
          and all questions remain unanswered ... >>

Cheers, Peter

[1] https://oeis.org/wiki/Offsets
[2] https://cs.uwaterloo.ca/journals/JIS/VOL19/Dekking/dekk4.html
[3] https://arxiv.org/abs/1405.6214
[4]
https://oeis.org/search?q=id:A000069|id:A001969|id:A010059|id:A010060|id:A016813&fmt=short