Index transform

The index transform is a sequence transform which yields the sequence of (least) indices at which appear the values in the given sequence for the first time:

INDEX(a) := ( inf {k ∈ D(a) | a(k) = n }; n ∈ R )

Here, D(a) is the domain of a, i.e., the set of indices for which a is defined; usually o + N = {o, o+1, o+2, ...}, where o is the offset of the sequence, i.e., the smallest index i for which a(i) is defined.

R is typically the range or image of the given sequence, R = im a. In that case, "inf" in the above could be replaced by "min".

Sequences with "holes" in their range

However, with R = im a, the INDEX transform would not be defined for indices n which are not in the range of a. Such sequences with "holes" are not allowed in the OEIS. Therefore we usually prefer to use

R = convex_hull (im a) = (inf a - 1, sup a + 1)

(= [min a, max a] if a is bounded).

Then, if some value n ∈ R does not occur in the sequence, the corresponding term in the INDEX transform would be inf {} = +oo. In the OEIS, this would usually be replaced with a term '-1', or maybe '0' which usually does not create an ambiguity, given that one can easily see the value of a(0). Thus, this "placeholder value" means that the corresponding term (i.e., the value equal to that index n) does not occur anywhere in the sequence.

Special cases

If a is a permutation of the positive or nonnegative integers, or of a finite set [o, o+1, o+2, ..., M], then its INDEX transform is the inverse permutation.

If the range of a is unbounded from below, the INDEX transform is a "doubly indexed" sequence, i.e., defined on the negative as well as positive integers. (How this would be "technically" encoded in the OEIS which only supports increasing indices, might vary depending on the specific case, but usually one would choose a (canonical) enumeration of the integers Z such as A001057 = (0, 1, -1, 2, -2, ...), for the indices.)

INDEX transform of RECORDS

The INDEX transform of the RECORDS transform yields the index of the n-th record within that list, which is usually not the same as the RECORD INDEX transform which gives the index where the records occurs in the original sequence:

INDEX ( RECORDS ( a ) ) ≠ RECORD_INDEX ( a ) = INDEX ( a ) o RECORDS ( a ) .

(The composition of the INDEX transform of a with the RECORDS transform of a does yield the indices where the records occur in a, which is exactly the RECORD_INDEX transform.

Programs

PARI/GP

find(x, a) = for(i=1, #a, a[i]==x && return(i))
INDEX(a, offset=1) = [if(n=find(x, a), n-1+offset) | x<-[vecmin(a)..vecmax(a)]]

Python

INDEX = lambda a: [a.index(x) if x in a else -1 for x in range(min(a), max(a)+1)]

The above code will only work when a is a (finite) list or sequence (tuple) or similar container. If a is an iterator yielding a possibly infinite sequence, one has use a different approach, for various reasons:

• min(a) and max(a) can't be computed for an infinite sequence, and either would "exhaust" the iterator a before we even can consider the element's positions
• similarly, a.index(x) and/or 'x in a' might not be defined in this case.

If it is known that increasingly large elements of the sequence appear in order, one can yield -1 for all indices until the next larger value occurs:

 def INDEX(a, o=0, i=0): # works for any iterable 'a', assuming the condition below
   """INDEX transform of sequence (iterable) 'a'; increasingly large terms must appear (for the first time) in order.
   o = offset of seq.(a); i = start of indices of the INDEX transform."""
   for k, ak in enumerate(a, o):
     if ak < i: continue
     while i < ak: yield -1; i += 1
     yield k; i += 1
 # example use:
 def peaks():  # generator of non-surjective, non monotonous sequence
   for m in range(99):
     for x in range(2*m): yield (x:=min(x,2*m-x))*(x+1)//2
 [a for a,_ in zip(INDEX(peaks()), range(30))]

Authorship

This page was created by M. F. Hasler on Feb. 1, 2025.

Cite this page as

M. F. Hasler, Index_transform. — From the On-Line Encyclopedia of Integer Sequences® (OEIS®) wiki.Available at https://oeis.org/wiki/Index_transform