A330222 - OEIS

%I #15 Dec 06 2019 07:08:13

%S 1,1,3,5,7,13,19,33,53,85,153,217,373,557,961,1717,2445

%N Maximum autocorrelation of the first 2^n terms of the Rudin-Shapiro sequence A020985.

%C The j-th autocorrelation of the first m terms of a sequence r taking values in {1, -1} is defined the absolute value of the Sum_{0 <= i < m-j} r(i)*r(i+j). The maximum autocorrelation is the maximum of the absolute value of this quantity over the range 1 <= j < m. In our case r(i) = A020985(i) and n = 2^m.

%H T. Høholdt, H. Elbrønd Jensen, and J. Justesen, <a href="https://pdfs.semanticscholar.org/7a61/c7dca6549210a8f90bcabd4710f037e8ec3c.pdf">Aperiodic Correlations and the Merit Factor of a Class of Binary Sequences</a>, IEEE Trans. Info. Theory IT-31 (1985), 549-552.

%F The paper of Høholdt et al. shows that a(n) = O( (2^n)^0.9 ).

%p b := (m,j) -> add(A020985(i)*A020985(i+j), i=0..m-j-1):

%p mb := m -> max(seq(abs(b(m,j)), j=1..m-1)):

%p a := n -> mb(2^n): seq(a(n), n=1..12); # _Peter Luschny_, Dec 06 2019

%K nonn,more

%O 1,3

%A _Jeffrey Shallit_, Dec 06 2019