1
$\begingroup$

Let N be a larger integer (e.g. N=1000). Let m be a smaller integer (e.g. m=20). Let X be the space of all strictly increasing sequences of m integers {x_1,…,x_m} such that 1<= x_i < x_(i+1) <=N.

I am trying to define an invertible function x(j) from the positive integers j=1,2,3,…. to X with the property that each sequence x(j) has the smallest possible overlap with any prior x(i) with i=1,2,...,j-1.

For example: 1) The first grouping of sequences would have 0-entry overlap with prior sequences. There are (N/m)=50 sequences in this grouping defined by: x(i)={m*(i-1)+1, m*(i-1)+2, …, m*(i-1)+20} for i=1 to 50.

2) The next grouping of sequences would have less than or equal to 1-entry overlap with prior sequences.

3) The next grouping of sequences would have less than or equal to 2-entry overlap with prior sequences.

4) Etc.

Does anyone know of (and/or can you figure out) a mapping with this property?

I could relax the property that x(j) has the smallest possible overlap (implying that we have to list all the sequences with 1-entry overlap, 2-entry overlap, etc.), and instead be satisfied with a mapping that has exponentially larger numbers of sequences in each bounded overlap grouping (but does not necessarily have all of them).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.