cp's OEIS Frontend

A374056 a(n) = max_{i=0..n} S_4(i) + S_4(n-i) where S_4(x) = A053737(x) is the base-4 digit sum of x.

%I A374056 #30 Aug 02 2024 04:38:10
%S A374056 0,1,2,3,4,5,6,4,5,6,7,5,6,7,8,6,7,8,9,7,8,9,10,8,9,10,11,9,10,11,12,
%T A374056 7,8,9,10,8,9,10,11,9,10,11,12,10,11,12,13,8,9,10,11,9,10,11,12,10,11,
%U A374056 12,13,11,12,13,14,9,10,11,12,10,11,12,13,11,12,13,14
%N A374056 a(n) = max_{i=0..n} S_4(i) + S_4(n-i) where S_4(x) = A053737(x) is the base-4 digit sum of x.
%C A374056 As shown in the proof of [Gruber and Holzer, lemma 9], the maximum is attained by choosing i as the largest number not exceeding n whose ternary representation is (33...3)_4. Also by lemma 6, for this choice of i we have A053737(i) = 3*floor(log_4(n+1)) and A053737(n-i) = A053737(n+1)-1, giving the formula below.
%D A374056 Hermann Gruber and Markus Holzer, Optimal Regular Expressions for Palindromes of Given Length. Extended journal version, in preparation, 2024.
%H A374056 Paolo Xausa, <a href="/A374056/b374056.txt">Table of n, a(n) for n = 0..10000</a>
%H A374056 Hermann Gruber and Markus Holzer, <a href="https://doi.org/10.4230/LIPIcs.MFCS.2021.52">Optimal Regular Expressions for Palindromes of Given Length</a>, Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, Article No. 53, pp. 53:1-53:15, 2021.
%F A374056 a(n) = 3*floor(log_4(n+1)) + A053737(n+1) - 1 [Gruber and Holzer, lemma 9].
%e A374056 For n=74, the maximum is attained by 63 + 11 = (333)_4 + (23)_4. Using 75=(1023)_4, comparing with the formula above, A053737(63) = 3*floor(log_4(n+1)) = 9 and A053737(11) = A053737(74+1)-1 = 5. Notice that other pairs attain the maximum as well. Namely, 43 + 31 = (223)_4 + (133)_4, as well as 47 + 27 = (233)_4 + (123)_4, and 59 + 15 = (323)_4 + (33)_4.
%t A374056 Table[3*Floor[Log[4, k]] + DigitSum[k, 4] - 1, {k, 100}] (* _Paolo Xausa_, Aug 01 2024 *)
%o A374056 (PARI) a(n) = 3*logint(n+1, 4) + sumdigits(n+1, 4) - 1;
%Y A374056 Cf. A053737, A102572, A014701, A374054.
%K A374056 nonn,easy,base
%O A374056 0,3
%A A374056 _Hermann Gruber_, Jun 26 2024