Sequences of radius K: How to fetch many huge objects into small memory for pairwise computations

Let a₁, a₂,..., a_m be a sequence over [n] = {1,... n}. We say that a sequence a₁, a₂,... a _m has the k-radius property if every pair of different elements in [n] occurs at least once within distance at most k; the distance d(a _i, a_j) = |i-j|. We demonstrate lower and (asymptotically) matching upper bounds for sequences with the k-radius property. Such sequences are applicable, for example, in computations of two-argument functions for all (₂ⁿ) pairs of large objects such as medical images, bitmaps or matrices, when processing occurs in a memory of size capable of storing k + 1 objects, k < n. We focus on the model when elements are read into the memory in a FIFO fashion that correspond to streaming the data or a special type of caching. We present asymptotically optimal constructions; they are based on the Euler totient theorem and recursion.