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

Author

Liangzhou Chen, Sep 10 2021

Keywords

• nonn
• easy

Comments

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

Examples

			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)
+-------+---+---+---+
		

Links

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

Crossrefs

Cf. A007949, A038502, A119674.

Programs

PARI

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

Formula

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