login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

a(n) = max_{i=0..n} S_3(i) + S_3(n-i) where S_3(x) = A053735(x) is the base-3 digit sum of x.
2

%I #37 Aug 01 2024 11:07:40

%S 0,1,2,3,4,3,4,5,4,5,6,5,6,7,6,7,8,5,6,7,6,7,8,7,8,9,6,7,8,7,8,9,8,9,

%T 10,7,8,9,8,9,10,9,10,11,8,9,10,9,10,11,10,11,12,7,8,9,8,9,10,9,10,11,

%U 8,9,10,9,10,11,10,11,12,9,10,11,10,11,12,11

%N a(n) = max_{i=0..n} S_3(i) + S_3(n-i) where S_3(x) = A053735(x) is the base-3 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 (22...2)_3. By [Gruber and Holzer, lemma 6], for this choice of i we have S_3(i) = 2*floor(log_3(n+1)) and S_3(n-i) = S_3(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="/A374054/b374054.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) = 2*floor(log_3(n+1)) + A053735(n+1) - 1 [Gruber and Holzer, lemma 9].

%e For n=31, the maximum is attained by 26 + 5 = (222)_3 + (12)_3. Using 32=(1021)_3, comparing with the formula above, S_3(26) = 2*floor(log_3(n+1)) = 6 and S_3(5) = S_3(31+1)-1 = 3. Notice that other pairs attain the maximum as well, namely 23 + 8 = (22)_3 + (212)_3, as well as 20 + 11 = (202)_3 + (102)_3.

%p f:= n -> 2 * ilog[3](n+1) + convert(convert(n+1,base,3),`+`) - 1:

%p map(f, [$0..100]); # _Robert Israel_, Jun 27 2024

%t Table[2*Floor[Log[3, k]] + DigitSum[k, 3] - 1, {k, 100}] (* _Paolo Xausa_, Aug 01 2024 *)

%o (PARI) a(n) = 2*logint(n+1, 3) + sumdigits(n+1, 3) - 1; \\ _Michel Marcus_, Jul 05 2024

%Y Cf. A053735, A062153, A014701, A374056.

%K nonn,easy,base

%O 0,3

%A _Hermann Gruber_, Jun 26 2024