cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

User: Hermann Gruber

Hermann Gruber's wiki page.

Hermann Gruber has authored 28 sequences. Here are the ten most recent ones:

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.

Original entry on oeis.org

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, 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, 12, 13, 11, 12, 13, 14, 9, 10, 11, 12, 10, 11, 12, 13, 11, 12, 13, 14
Offset: 0

Views

Author

Hermann Gruber, Jun 26 2024

Keywords

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

Examples

			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.

References

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

Links

Crossrefs

Cf. A053737, A102572, A014701, A374054.

Programs

  • Mathematica
    Table[3*Floor[Log[4, k]] + DigitSum[k, 4] - 1, {k, 100}] (* Paolo Xausa, Aug 01 2024 *)
  • PARI
    a(n) = 3*logint(n+1, 4) + sumdigits(n+1, 4) - 1;

Formula

a(n) = 3*floor(log_4(n+1)) + A053737(n+1) - 1 [Gruber and Holzer, lemma 9].

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.

Original entry on oeis.org

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

Views

Author

Hermann Gruber, Jun 26 2024

Keywords

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.

Examples

			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.

References

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

Links

Crossrefs

Cf. A053735, A062153, A014701, A374056.

Programs

  • 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 *)
  • PARI
    a(n) = 2*logint(n+1, 3) + sumdigits(n+1, 3) - 1; \\ Michel Marcus, Jul 05 2024

Formula

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

A351491 Irregular triangle read by rows: T(n,k) is the minimum number of alphabetic symbols in a regular expression for the k lexicographically first palindromes of length 2*n over a ternary alphabet, n >= 0, 1 <= k <= 3^n.

Original entry on oeis.org

0, 2, 4, 6, 4, 6, 8, 12, 14, 16, 20, 22, 24, 6, 8, 10, 14, 16, 18, 22, 24, 26, 32, 34, 36, 40, 42, 44, 48, 50, 52, 58, 60, 62, 66, 68, 70, 74, 76, 78, 8, 10, 12, 16, 18, 20, 24, 26, 28, 34, 36, 38, 42, 44, 46, 50, 52, 54, 60, 62, 64, 68, 70, 72, 76, 78, 80, 88
Offset: 0

Views

Author

Hermann Gruber, Feb 13 2022

Keywords

Comments

Analogous to A351489 (which is the corresponding sequence for palindromes over binary alphabet).

Examples

			Triangle T(n,k) begins:
      k=1  2   3   4   5   6 ...
  n=0:  0,
  n=1:  2, 4,  6;
  n=2:  4, 6,  8, 12, 14, 16, 20, 22, 24;
  n=3:  6, 8, 10, 14, 16, 20, 22, 24, 26, 32, 34, 36, 40, 42, 44, 48, 50, 52, 58, 60, 62, 66, 68, 70, 74, 76, 78;
  ...

References

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

Links

Crossrefs

Cf. A053735 (ternary sum of digits), A351489 (for binary alphabet).

Formula

Let SumOfDigitsInBase(m,b) denote the digit sum of nonnegative integer m in base b. Then the general formula for alphabet size q reads as
T(n,k) = 2*n + (2*q*(k-1))/(q-1) - (2*SumOfDigitsInBase(k-1,q))/(q-1). [Gruber and Holzer 2022 theorem 27]

A351490 Irregular triangle read by rows: T(n,k) is the minimum number of alphabetic symbols in a regular expression for the k lexicographically first palindromes of odd length 2*n-1 over a binary alphabet, n >= 1, 1 <= k <= 2^n.

Original entry on oeis.org

1, 2, 3, 4, 7, 8, 5, 6, 9, 10, 15, 16, 19, 20, 7, 8, 11, 12, 17, 18, 21, 22, 29, 30, 33, 34, 39, 40, 43, 44, 9, 10, 13, 14, 19, 20, 23, 24, 31, 32, 35, 36, 41, 42, 45, 46, 55, 56, 59, 60, 65, 66, 69, 70, 77, 78, 81, 82, 87, 88, 91, 92, 11, 12, 15, 16, 21, 22, 25, 26, 33, 34, 37, 38, 43, 44, 47, 48, 57, 58, 61, 62
Offset: 1

Views

Author

Hermann Gruber, Feb 12 2022

Keywords

Comments

Following the notation in Gruber/Holzer (2021), for n >= 1 and 1 <= k <= 2^n, let P'{n,k} denote the set containing the lexicographically first k palindromes of odd length 2n-1 over the binary alphabet {a,b}. T(n,k) is the minimum number of alphabetic symbols in any regular expression describing the set P'{n,k}.

Examples

			Triangle T(n,k) begins:
  1, 2;
  3, 4,  7,  8;
  5, 6,  9, 10, 15, 16, 19, 20;
  7, 8, 11, 12, 17, 18, 21, 22, 29, 30, 33, 34, 39, 40, 43, 44;
  ...

Links

Crossrefs

Cf. A351489 gives the corresponding irregular triangle for even length 2*n.

Programs

  • Mathematica
    Flatten[Table[2n+3(k-1)-2Total[IntegerDigits[k-1,2]]-1,{n,6},{k,2^n}]] (* Stefano Spezia, Feb 13 2022 *)
  • PARI
    T(n,k) = 2*n + 3*(k-1) - 2*hammingweight(k-1) - 1 \\ Andrew Howroyd, Feb 12 2022

Formula

T(n,k) = 2*n + 3*(k-1) - 2*hamming_weight(k-1)-1. See theorem 20 in Gruber/Holzer (2021).

A351489 Irregular triangle read by rows: T(n,k) is the minimum number of alphabetic symbols in a regular expression for the k lexicographically first palindromes of length 2*n over a binary alphabet, n >= 0, 1 <= k <= 2^n.

Original entry on oeis.org

0, 2, 4, 4, 6, 10, 12, 6, 8, 12, 14, 20, 22, 26, 28, 8, 10, 14, 16, 22, 24, 28, 30, 38, 40, 44, 46, 52, 54, 58, 60, 10, 12, 16, 18, 24, 26, 30, 32, 40, 42, 46, 48, 54, 56, 60, 62, 72, 74, 78, 80, 86, 88, 92, 94, 102, 104, 108, 110, 116, 118, 122, 124, 12, 14, 18, 20, 26, 28, 32, 34, 42, 44, 48, 50, 56, 58, 62
Offset: 0

Views

Author

Hermann Gruber, Feb 12 2022

Keywords

Comments

Following the notation in Gruber/Holzer (2021), for n >= 0 and 1 <= k <= 2^n, let P_{n,k} denote the set containing the lexicographically first k palindromes of even length 2n over the binary alphabet {a,b}. T(n,k) is the minimum number of alphabetic symbols in any regular expression describing the set P_{n,k}.

Examples

			Triangle T(n,k) begins:
      k=1   2   3   4   5   6 ...
  n=0:  0,
  n=1:  2,  4;
  n=2:  4,  6, 10, 12;
  n=3:  6,  8, 12, 14, 20, 22, 26, 28;
  n=4:  8, 10, 14, 16, 22, 24, 28, 30, 38, 40, 44, 46, 52, 54, 58, 60;
  ...

Links

Crossrefs

Cf. A000120 (sum of binary digits), A351490 (on odd lengths).

Programs

  • Mathematica
    Flatten[Table[2n+4(k-1)-2Total[IntegerDigits[k-1,2]],{n,0,6},{k,2^n}]] (* Stefano Spezia, Feb 13 2022 *)

Formula

T(n,k) = 2*n + 4*(k-1) - 2*wt(k-1), where wt(n) = A000120(n) is the sum of the binary digits of n. [Gruber and Holzer theorem 14]

A211944 Number of distinct finite languages over 3-ary alphabet, whose minimum regular expression has reverse Polish length 2n-1.

Original entry on oeis.org

5, 15, 85, 589, 4512, 37477, 328718, 2998039
Offset: 1

Views

Author

Hermann Gruber, Apr 26 2012

Keywords

Links

A211943 Number of distinct regular languages over 3-ary alphabet, whose minimum regular expression has reverse Polish length n.

Original entry on oeis.org

5, 3, 15, 33, 106, 361, 1012, 3859, 11655, 43431
Offset: 1

Views

Author

Hermann Gruber, Apr 26 2012

Keywords

Links

A211954 Number of distinct finite languages over 4-ary alphabet, whose minimum regular expression has ordinary length n.

Original entry on oeis.org

6, 16, 74, 336, 1474, 6560, 28861, 128720, 578033, 2624460
Offset: 1

Views

Author

Hermann Gruber, Apr 26 2012

Keywords

Links

A211953 Number of distinct regular languages over 4-ary alphabet, whose minimum regular expression has ordinary length n.

Original entry on oeis.org

6, 20, 102, 520, 2628, 13482, 68747, 354500, 1840433
Offset: 1

Views

Author

Hermann Gruber, Apr 26 2012

Keywords

Links

A211952 Number of distinct finite languages over 3-ary alphabet, whose minimum regular expression has ordinary length n.

Original entry on oeis.org

5, 9, 33, 117, 391, 1350, 4546, 15753, 55053, 196185
Offset: 1

Views

Author

Hermann Gruber, Apr 26 2012

Keywords

Links

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.