cp's OEIS Frontend

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

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