[seqfan] Re: Fun with subsequences

[franktaw at netscape.net]

In the theory of fractal sequences, the property of containing every 
positive integer infinitely often is called being "infinitive". 
Certainly this could be stretched to cover nonnegative integers and 
even all integers. Maybe we could say "nonnegative infinitive" and 
"integer infinitive".

Apropos of that, the fractal sequences that contain all positive 
integers (which is most of the ones that one encounters) are all 
infinitive.

There are a few obvious candidates for a canonical integer infinitive 
sequence:

0; -1,0,1; -2,-1,0,1,2; ...
0; 1,0,-1; 2,1,0,-1,-2; ...
0; 0,1,-1; 0,1,-1,2,-2; ...

None of these are currently in the OEIS. (All three of these are all 
fractal sequences.) I would probably vote for the first one: "Count 
from -n to n."

A065363 is another fairly basic one. Unlike A000319, A000209 is easily 
proved to have this property.

Franklin T. Adams-Watters

-----Original Message-----
From: Charles Greathouse <charles.greathouse at case.edu>

Just like set inclusion partially orders the space of sets, the
subsequence relation preorders the space of sequences*.  I noticed
that this relation has a(n equivalence class of) top element(s):
sequences which contain each integer infinitely many times.  For
nonnegative integers the canonical choice is clearly A002262.  I
wonder if there is a similar natural representative for all integer
sequences?

Can anyone find a reasonable list of these sequences?  I imagine there
are many sequences which are top elements in this sense but for which
the proof is hard.  For an example, an old favorite of mine, A000319,
is probably a member but the proof seems hopeless.

Amusingly, the keyword "nonn" can be interpreted in light of the above
as marking precisely those which are subsequences of A002262.  I
wonder which other keywords or properties can similarly be interpreted
in unusual ways?

Finally, I've pondered ways to efficiently find subsequences (say, in
the OEIS).  Of course even without preprocessing this can be done in
linear time in the length of the sequence data, but could that be
improved?  Say, a data structure generated off-line that partitions
the sequences such that only a small part need be searched directly?
Also some sequence properties (e.g., being monotonic) could be used if
known to the algorithm, but I don't suspect these are common enough to
help much.

* Integer sequences and subsets of Z, of course, for the pedants.

Charles Greathouse
Analyst/Programmer
Case Western Reserve University

_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/