%I #24 Aug 03 2024 01:52:34
%S 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,
%T 29,11,31,32,12,34,35,6,37,38,14,40,41,15,43,44,7,46,47,17,49,50,18,
%U 52,53,5,55,56,20,58,59,21,61,62,9,64,65,23,67,68,24,70,71,10,73
%N Number of states of the minimal deterministic finite automaton that accepts ternary strings that represent numbers that are divisible by n.
%C a(n) = n for all n coprime to 3.
%H Liangzhou Chen, <a href="/A347717/b347717.txt">Table of n, a(n) for n = 1..10000</a>
%F a(1) = 1, a(2) = 2, a(3n) = a(n) + 1, a(3n+1) = 3n+1, a(3n+2) = 3n+2.
%e The minimal DFA when n=6, giving the form of transition table:
%e +-------+-----------+
%e | | tr. func. |
%e | state +---+---+---+
%e | | 0 | 1 | 2 |
%e +-------+---+---+---+
%e |->*A | A | C | B | (mod 6 = 0)
%e +-------+---+---+---+
%e | B | A | C | B | (mod 6 = 2,4)
%e +-------+---+---+---+
%e | C | C | B | C | (mod 6 = 1,3,5)
%e +-------+---+---+---+
%o (PARI) a(n) = n / 3^valuation(n, 3) + valuation(n, 3)
%Y Cf. A007949, A038502, A119674.
%K nonn,easy
%O 1,2
%A _Liangzhou Chen_, Sep 10 2021