Lucas B. Vieira - cp's OEIS frontend

User: Lucas B. Vieira

Lucas B. Vieira has authored 4 sequences.

A370821 Number of minimal deterministic Mealy automata with n states outputting ternary strings.

3, 12, 54, 210, 798, 2850, 10038, 34410, 116406, 388362, 1283430, 4203786, 13675038, 44211570, 142202574, 455299242, 1451997726, 4614253122, 14617620726, 46177325994, 145505603694, 457437342546, 1435074324006, 4493508791754, 14045385985902

Offset: 1

Lucas B. Vieira, Mar 02 2024

nonn

a(n) counts the minimal number of ternary words w = uv, with |w| = n, such that u is an irreducible prefix and v a primitive word. This defines a minimal "pattern", written as "u(v)", describing the behavior of a minimal n-state deterministic Mealy automaton outputting a string from a ternary alphabet, where u is the transient output, and v the cyclic output, possibly truncated. Used in the definition of the Deterministic Complexity (DC) of strings (Vieira and Budroni, 2022).

			a(1) = 3 as there are only 3 deterministic Mealy automata with 1 state producing ternary words, corresponding to the 3 patterns (0), (1) and (2), generating the strings w=0^L, w=1^L, and w=2^L for L >= 1.
a(2) = 12, since there are 12 minimal ternary patterns: (01), 0(1), (02), 0(2), (10), 1(0), (12), 1(2), (20), 2(0), (21), 2(1).
E.g.: The ternary string w = 000120120 can be described by the pattern 00(012), where the parentheses indicate the repeating part, up to truncation. This pattern is minimal, with 5 symbols (ignoring the parentheses). It describes the behavior of a minimal deterministic Mealy automaton producing the string w, leading to its Deterministic Complexity (DC) to be DC(w) = 5.

M. Domaratzki, D. Kisman, and J. Shallit, On the number of distinct languages accepted by finite automata with n states, J. Autom. Lang. Combinat. 7 (2002) 4-18, Section 6, f_1(n).

Lucas B. Vieira and Costantino Budroni, Temporal correlations in the simplest measurement sequences, Quantum 6 p. 623 (2022).

Cf. A059412 for the case of binary strings.

Cf. A143324 for psi(k,n).

NumPrimitiveWords[k_, n_] := Sum[MoebiusMu[d] k^(n/d), {d, Divisors[n]}];
a[n_] := NumPrimitiveWords[3, n] + Sum[(3 - 1) 3^(i - 1) NumPrimitiveWords[3, n - i], {i, 1, n - 1}]

a(n) = psi(3, n) + Sum_{i=1..n-1} (3-1)*3^(i-1)*psi(3, n-i), where psi(k,n) is the number of primitive words of length n on a k-letter alphabet (Cf. A143324).

A370489 Deterministic complexity of binary strings, in shortlex order.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 1, 3, 2, 2, 2, 2, 3, 1, 1, 4, 3, 3, 3, 2, 3, 2, 2, 3, 2, 3, 3, 3, 4, 1, 1, 5, 4, 4, 3, 3, 4, 3, 3, 3, 2, 4, 4, 3, 4, 2, 2, 4, 3, 4, 4, 2, 3, 3, 3, 4, 3, 3, 4, 4, 5, 1, 1, 6, 5, 5, 4, 4, 5, 4, 4, 3, 3, 5, 4, 4, 5, 3, 3, 4, 3, 5, 5, 2

Offset: 1

Lucas B. Vieira, Mar 02 2024

a(n) = DC(w[n]), where w[n] is the n-th binary string in shortlex order: 0, 1, 00, 01, 10, 11, 000, 001, .... (row n-1 of A076478).
The Deterministic Complexity (DC) of a string w is the minimum number of states in a deterministic Mealy automaton outputting the string w. Alternatively, DC(w) = |u|+|v| for the smallest (possibly empty) u and primitive word v, such that w = trunc(uv^k,|w|) for some k >= 1, where trunc(x,L) truncates the word x to length L.
1..L each appear at least twice in row L since DC(0^i 1^(L-i)) = DC(1^i 0^(L-i)) = i+1 for i = 0..L-1. - Michael S. Branicky, Mar 03 2024

			For n = 1, w[1] = 0, and DC(w[1]) = 1. The minimal deterministic Mealy automaton outputting w[1] has a single state, transitioning to itself and outputting 0.
For n = 36, w[36] = 00101, and DC(w[36]) = 3. The minimal deterministic Mealy automaton has 3 states: transitions 1->2 and 2->3 output 0, and 3->2 outputs 1.

Michael S. Branicky, Table of n, a(n) for n = 1..10000
Lucas B. Vieira and Costantino Budroni, Temporal correlations in the simplest measurement sequences, Quantum 6 p. 623 (2022).

Cf. A059412, A076478, A370821.

(* e.g. DC[{0,0,1,0,1}] = 3 *)
DC[seq_] := With[{L = Length[seq]}, Do[If[With[{c = dc - t}, Take[Flatten[{Take[seq, t], ConstantArray[Take[Drop[seq, t], c], Ceiling[(L - t)/c]]}], L]] == seq, Return[dc]], {dc, 0, L}, {t, 0, dc - 1}]];
a[n_] := DC[Rest[IntegerDigits[n + 1, 2]]];
(* Table for all sequences up to length 10 *)
With[{L = 10}, Table[a[n], {n, 2*(2^L-1)}]]

def DC(w): return next(dc for dc in range(1, len(w)+1) for i in range(dc) if w == (w[:i]+w[i:dc]*(1+(len(w)-i)//(dc-i)))[:len(w)])
def a(n): return DC(bin(n+1)[3:])
print([a(n) for n in range(1, 88)]) # Michael S. Branicky, Mar 03 2024

A355564 Triangle read by rows: T(n,k) = n(1+2k) - k*(1+k), n >= 1, 0 <= k <= n-1.

Original entry on oeis.org

1, 2, 4, 3, 7, 9, 4, 10, 14, 16, 5, 13, 19, 23, 25, 6, 16, 24, 30, 34, 36, 7, 19, 29, 37, 43, 47, 49, 8, 22, 34, 44, 52, 58, 62, 64, 9, 25, 39, 51, 61, 69, 75, 79, 81, 10, 28, 44, 58, 70, 80, 88, 94, 98, 100, 11, 31, 49, 65, 79, 91, 101, 109, 115, 119, 121

Offset: 1

Lucas B. Vieira, Jul 07 2022

T(n,k) is the number of potentially nonzero elements in a square, n X n band matrix of bandwidth k, i.e., the number of matrix elements (i,j) for which |i-j| <= k.

T(n,0) = n, as a zero-bandwidth matrix is diagonal, and T(n,n-1) = n^2, as the band encompasses the entire matrix.

			Triangle starts:
  1;
  2,  4;
  3,  7,  9;
  4, 10, 14, 16;
  5, 13, 19, 23, 25;
  6, 16, 24, 30, 34, 36;
  7, 19, 29, 37, 43, 47, 49;
  ...
Example: For n = 6 and k = 2, we have a band matrix of the form
    [. . . 0 0 0]
    [. . . . 0 0]
    [. . . . . 0]
    [0 . . . . .],
    [0 0 . . . .]
    [0 0 0 . . .]
where dots represent the entries which may have nonzero values. The number of such entries is T(6,2) = 24.

The sequence is complementary to A095832, i.e.: T(n,k) = n^2 - A095832(n,k).

Differences within a row T(n,k+1) - T(n,k) give A212012.

Flatten[Table[n (1 + 2 k) - k (1 + k), {n, 1, 10}, {k, 0, n - 1}]]

A115588 Number of distinct prime numbers necessary to represent a natural number n > 1.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 1, 2, 1, 3, 1, 2, 2, 2, 2, 2, 1, 2, 2, 3, 1, 3, 1, 2, 3, 2, 1, 2, 2, 2, 2, 2, 1, 2, 2, 3, 2, 2, 1, 3, 1, 2, 3, 2, 2, 3, 1, 2, 2, 3, 1, 2, 1, 2, 3, 2, 2, 3, 1, 2, 2, 2, 1, 3, 2, 2, 2, 3, 1, 3, 2, 2, 2, 2, 2, 3, 1, 2, 3, 2, 1, 3, 1, 3, 3, 2

Offset: 2

Lucas B. Vieira, Mar 09 2006

nonn

The sequence gives the number of distinct prime numbers needed to represent a given natural number greater than or equal to 2 upon recursive factorization of powers. In order to do this, we must factor any subsequent composite number that may appear on the exponents of the next factorizations (e.g., 4 in 48=2^4*3), until only prime numbers are used. - Lucas B. Vieira, Mar 15 2006

In this sequence, a(n)=1 if n is prime, or a power tower (tetration or iterated exponentiation) of a prime base (e.g., 2^2, 3^3^3^3, 7^7). The sequence reaches a new boundary whenever n is a primorial number (factorial of primes). - Lucas B. Vieira, Mar 15 2006

			a(4)=1, since 4=2^2 and the only prime used was 2.
a(30)=3 because 30=2*3*5 and three primes were necessary.
a(65536)=1, since 65536=2^16=2^(2^4)=2^(2^(2^2)) and, again, only one prime was needed.
a(1) would be undefined, so it is not included.

Alois P. Heinz, Table of n, a(n) for n = 2..10000

Cf. A000040, A001221, A002110, A381399, A381400.

b:= n-> `if`(n=1, {}, {seq([i[1], b(i[2])[]][], i=ifactors(n)[2])}):
a:= n-> nops(b(n)):
seq(a(n), n=1..200);  # Alois P. Heinz, Apr 27 2012

A115588[n_] := Length[Union[NestWhile[DeleteCases[Flatten[FactorInteger[#]], 1] &, {n}, AnyTrue[#, CompositeQ] &]]];
Array[A115588, 100, 2] (* Paolo Xausa, Feb 24 2025 *)

listf(f, list) = {for (k=1, #f~, listput(list, f[k,1]); if (isprime(f[k,2]), listput(list, f[k,2]), if (f[k,2] > 1, my(vexp = Vec(listf(factor(f[k,2]), list))); for (i=1, #vexp, listput(list, vexp[i]););););); list;}
a(n) = {my(f=factor(n), list=List()); #select(isprime, Set(Vec(listf(f, list))));} \\ Michel Marcus, Dec 02 2020

cp's OEIS Frontend

User: Lucas B. Vieira

A370821 Number of minimal deterministic Mealy automata with n states outputting ternary strings.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A370489 Deterministic complexity of binary strings, in shortlex order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

A355564 Triangle read by rows: T(n,k) = n*(1+2*k) - k*(1+k), n >= 1, 0 <= k <= n-1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A115588 Number of distinct prime numbers necessary to represent a natural number n > 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A355564 Triangle read by rows: T(n,k) = n(1+2k) - k*(1+k), n >= 1, 0 <= k <= n-1.