A374054 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.

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, 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, 8, 9, 10, 9, 10, 11, 10, 11, 12, 9, 10, 11, 10, 11, 12, 11

Offset

0,3

Comments

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.

References

Hermann Gruber and Markus Holzer, Optimal Regular Expressions for Palindromes of Given Length. Extended journal version, in preparation, 2024.

Links

Paolo Xausa, Table of n, a(n) for n = 0..10000

Hermann Gruber and Markus Holzer, Optimal Regular Expressions for Palindromes of Given Length, Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, Article No. 53, pp. 53:1-53:15, 2021.

Formula

a(n) = 2*floor(log_3(n+1)) + A053735(n+1) - 1 [Gruber and Holzer, lemma 9].

Example

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.

Maple

f:= n -> 2 * ilog[3](n+1) + convert(convert(n+1, base, 3), `+`) - 1:
map(f, [$0..100]); # Robert Israel, Jun 27 2024

Mathematica

Table[2*Floor[Log[3, k]] + DigitSum[k, 3] - 1, {k, 100}] (* Paolo Xausa, Aug 01 2024 *)

Prog

(PARI) a(n) = 2*logint(n+1, 3) + sumdigits(n+1, 3) - 1; \\ Michel Marcus, Jul 05 2024

Crossrefs

Cf. A053735, A062153, A014701, A374056.

Sequence in context: A114524 A058033 A216197 * A307531 A125619 A349946

Adjacent sequences: A374051 A374052 A374053 * A374055 A374056 A374057

Keyword

nonn,easy,base

Author

Hermann Gruber, Jun 26 2024

Status

approved