This surely has been done, maybe I googled the wrong adjective...
Define a raggedness measure $r$ of a sequence $S$ in this way:

  • Two members $S_i,S_j$ of the sequence (who don't have to be adjacent!) are called neighbors if $\not\exists_{k\in]i,j[}|S_k\in]S_i,S_j[$.
  • Example: $S=(1,4,3,2,5)$. 4 and 5 are neighbors (3 and 2 are outside of their size interval), 4 and 2 are not (3 falls inbetween), 1 and 4 are, 4 and 3 are (up or down doesn't matter).
  • $r=card(neighbor-pairs(S))/n$ ($r=8/5$ for the example)
  • WLOG for $S$ we can limit ourselves to permutations of $\{1,\dots,n\}$. (Some series below are noninteger, we can simply "stretch" them to integer.)

$r$ is at minimum $O(1)$ (obvious, all adjacent members of $S$ are also neighbors) and at maximum $O(\log n)$ (this follows from a seminal result of E.Demaine on binary search trees). Some further examples that I tried:

  • $S=id, r=1$ (trivial)
  • $S$ is the bitwise permutation, $r=O(\log n)$ (well known)
  • $S$ is the Gray code permutation, $r=185/48$ if I could compute and sequence-guess correctly :-)
  • $S$ is the Farey series sorted by denominator and then by nominator, $r=O(\log n)$ (says the experiment - can you verify?)
  • $S$ is the Stern-Bacrot series, my best guess is $r=O(\log n)$ again (ditto?)

My questions:

  • Do you have a reference for sequence raggedness in general?
  • Do you have a reference for this measure in particular?
  • Do you have an idea for some (not too convoluted :-) $S$ with $O(1)<r<O(\log n)$?

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.