Rational complexity of binary sequences, FQSRs, and pseudo-ultrametric continued fractions in R

We introduce rational complexity , a new complexity measure for binary sequences. The sequence s ∈ B ω is considered as binary expansion of a real fraction s ≡ ∑ k∈ Nsₖ2⁻ᵏ∈ [0,1] ⊂ R s ≡ ∑ k ∈ ℕ s k 2 − k ∈ [ 0 , 1 ] ⊂ ℝ . We compute its continued fraction expansion (CFE) by the Binary CFE Algorithm , a bitwise approximation of s by binary search in the encoding space of partial denominators, obtaining rational approximations r of s with r → s . We introduce Feedback in Q ℚ Shift Registers (F Q ℚ SRs) as the analogue of Linear Feedback Shift Registers (LFSRs) for the linear complexity L, and Feedback with Carry Shift Registers (FCSRs) for the 2-adic complexity A. We show that there is a substantial subset of prefixes with “typical” linear and 2-adic complexities, around n /2, but low rational complexity. Thus the three complexities sort out different sequences as non-random.