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