Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #30 Aug 02 2024 04:38:10
%S 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 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 12,13,11,12,13,14,9,10,11,12,10,11,12,13,11,12,13,14
%N 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 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 Hermann Gruber and Markus Holzer, Optimal Regular Expressions for Palindromes of Given Length. Extended journal version, in preparation, 2024.
%H Paolo Xausa, <a href="/A374056/b374056.txt">Table of n, a(n) for n = 0..10000</a>
%H 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 a(n) = 3*floor(log_4(n+1)) + A053737(n+1) - 1 [Gruber and Holzer, lemma 9].
%e 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 Table[3*Floor[Log[4, k]] + DigitSum[k, 4] - 1, {k, 100}] (* _Paolo Xausa_, Aug 01 2024 *)
%o (PARI) a(n) = 3*logint(n+1, 4) + sumdigits(n+1, 4) - 1;
%Y Cf. A053737, A102572, A014701, A374054.
%K nonn,easy,base
%O 0,3
%A _Hermann Gruber_, Jun 26 2024