A347717 Number of states of the minimal deterministic finite automaton that accepts ternary strings that represent numbers that are divisible by n.

1, 2, 2, 4, 5, 3, 7, 8, 3, 10, 11, 5, 13, 14, 6, 16, 17, 4, 19, 20, 8, 22, 23, 9, 25, 26, 4, 28, 29, 11, 31, 32, 12, 34, 35, 6, 37, 38, 14, 40, 41, 15, 43, 44, 7, 46, 47, 17, 49, 50, 18, 52, 53, 5, 55, 56, 20, 58, 59, 21, 61, 62, 9, 64, 65, 23, 67, 68, 24, 70, 71, 10, 73

Offset

1,2

Comments

a(n) = n for all n coprime to 3.

Links

Liangzhou Chen, Table of n, a(n) for n = 1..10000

Formula

a(1) = 1, a(2) = 2, a(3n) = a(n) + 1, a(3n+1) = 3n+1, a(3n+2) = 3n+2.

Example

The minimal DFA when n=6, giving the form of transition table:
+-------+-----------+
|       | tr. func. |
| state +---+---+---+
|       | 0 | 1 | 2 |
+-------+---+---+---+
|->*A   | A | C | B | (mod 6 = 0)
+-------+---+---+---+
|   B   | A | C | B | (mod 6 = 2,4)
+-------+---+---+---+
|   C   | C | B | C | (mod 6 = 1,3,5)
+-------+---+---+---+

Prog

(PARI) a(n) = n / 3^valuation(n, 3) + valuation(n, 3)

Crossrefs

Cf. A007949, A038502, A119674.

Sequence in context: A242348 A186053 A133082 * A130265 A368156 A359045

Adjacent sequences: A347714 A347715 A347716 * A347718 A347719 A347720

Keyword

nonn

Author

Liangzhou Chen, Sep 10 2021

Status

approved