<p>There's another paper on the same subject:  B. Alexeev, Minimal DFA for testing divisibility, J. Comput. Syst. Sci. 69 (2004), 235–243.</p>

CC BY-SA 3.0
2015-04-16T12:10:08.477Z
2015-04-16T12:10:08.477Z
Jeffrey Shallit
<p>There is a known formula for minimum number of states for such a finite automaton. This depends on $n$ as well as the radix $R$ of the underlying positional representation. </p>

<p>If $n$ is coprime to $R$, then the minimal number of states is $n$. However, when $n$ shares a factor with the radix then the situation is rather complicated. See Mathematica Journal Vol 3 Issue 11. <a href="http://www.mathematica-journal.com/data/uploads/2011/01/Sutner.pdf">"Divisibility and State Complexity"</a> by Klaus Sutner.</p>

CC BY-SA 3.0
2012-01-29T21:15:02.810Z
Exactly the sort of thing I was looking for. Thanks, I'll dive into the paper sometime soon.
Nick Van Hoogenstyn
CC BY-SA 3.0
2016-07-27T12:47:03.537Z
The link seems broken
Nicola Gigante
CC BY-SA 3.0
2012-01-29T03:47:02.417Z
2012-01-31T19:20:51.030Z
2012-01-31T19:20:51.030Z
David Harris
<p>I'm working on a problem set for a class, and thought of a question related to what I was working on. <strong>Is there a minimum number of states that a finite automaton must have in order to accept binary strings that represent numbers divisible by an integer n?</strong> In an earlier problem set, I was able to construct a DFA that accepted binary strings divisible by 3 with 3 states. Is this a coincidence, or is there something inherent to the general problem of detecting strings divisible by n that suggests a minimum number of states? </p>

<p>I promise this will not answer a homework question for me! :)</p>

CC BY-SA 3.0
2012-01-29T02:15:40.093Z
The typical construction is easily generalized to $n$ states for mod $n$. It will all make sense when you'll understand why your DFA actually accepts the correct language.
Michael Blondin
CC BY-SA 3.0
2012-01-29T04:09:00.587Z
Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the [FAQ] for more information.
Kaveh
CC BY-SA 3.0
2012-01-29T05:27:33.953Z
@Kaveh: I think the question is okay, especially given David's concise answer.
Huck Bennett
CC BY-SA 3.0
2012-01-29T06:10:08.943Z
@HuckBennett I agree with Kaveh that this question should be closed on cstheory, mostly to be consistent. However, I also agree with you: this is a fun question and when you first see DFAs it is definitely one you should be asking yourself. I think the OP should try to have some fun working out the answer for himself, and then consult [math.SE](http://math.stackexchange.com/) for more info.
Artem Kaznatcheev
CC BY-SA 3.0
2012-01-29T06:15:30.300Z
@ArtemKaznatcheev: Well put. Fair enough.
Huck Bennett
CC BY-SA 3.0
2012-01-29T13:43:32.093Z
This isn't homework (although it's inspired by a homework question), it's an interesting question, I don't believe it's a well-known result and the answer to the question appeared in a research journal. I don't see why it should be closed. The *upper bound* was homework, and is indeed easy, but the question was about the lower bound.
Peter Shor 
CC BY-SA 3.0
2012-01-29T13:47:32.603Z
@MichaelBlondin that's true when the input is a number in unary notation. For example, in base 10, numbers divisible by 5 end in 0 or 5, so you only need two states for a DFA to accept them.
Janoma
CC BY-SA 3.0
2012-01-29T22:55:05.600Z
@Janoma: Indeed. The end of the question suggests the OP confuses upper bounds with lower bounds.
Michael Blondin
CC BY-SA 3.0
2012-01-31T21:33:04.700Z
suggest the moderator(s) not be so fast to kill questions (esp unilaterally) that come from site newbies or undergraduates & rely more on the built-in voting mechanisms instead. arguably this problem relates to the complexity of integer division, integer remainder, primality testing, factoring, gcd etc (lower bounds on which are mostly deep open questions)
vzn
CC BY-SA 3.0
2012-02-01T16:46:42.977Z
here is an example of a deep link between regular languages, integer division, and a premiere open problem in math/CS, the collatz conjecture: Jeﬀrey O. Shallit and David W. Wilson (1991), The “3x + 1” Problem and Finite Automata, Bulletin of the EATCS (European Association for Theoretical Computer Science), No. 46, 1991, pp. 182–185.
vzn
CC BY-SA 3.0
2012-02-03T16:35:01.100Z
but this question could also be construed to be asking about DFA minimization which is also a well studied problem see eg [how do you normalize/minimize a FSM](http://stackoverflow.com/questions/1105779/how-do-you-normalize-a-finite-state-machine)
vzn
<automata-theory>
Finite automata that accept binary strings divisible by n
Nick Van Hoogenstyn
# Finite automata that accept binary strings divisible by n

(Asked by: username_0 on 2012-01-29)

I'm working on a problem set for a class, and thought of a question related to what I was working on. **Is there a minimum number of states that a finite automaton must have in order to accept binary strings that represent numbers divisible by an integer n?** In an earlier problem set, I was able to construct a DFA that accepted binary strings divisible by 3 with 3 states. Is this a coincidence, or is there something inherent to the general problem of detecting strings divisible by n that suggests a minimum number of states?

I promise this will not answer a homework question for me! :)

**Tags:** automata-theory
> **Comments:**
> **username_1**: The typical construction is easily generalized to $n$ states for mod $n$. It will all make sense when you'll understand why your DFA actually accepts the correct language.  
> **username_2**: Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the [FAQ] for more information.  
> **username_3**: @Kaveh: I think the question is okay, especially given David's concise answer.  
> **username_4**: @HuckBennett I agree with Kaveh that this question should be closed on cstheory, mostly to be consistent. However, I also agree with you: this is a fun question and when you first see DFAs it is definitely one you should be asking yourself. I think the OP should try to have some fun working out the answer for himself, and then consult [math.SE](http://math.stackexchange.com/) for more info.  
> **username_3**: @ArtemKaznatcheev: Well put. Fair enough.  
> **username_5**: This isn't homework (although it's inspired by a homework question), it's an interesting question, I don't believe it's a well-known result and the answer to the question appeared in a research journal. I don't see why it should be closed. The *upper bound* was homework, and is indeed easy, but the question was about the lower bound.  
> **username_6**: @MichaelBlondin that's true when the input is a number in unary notation. For example, in base 10, numbers divisible by 5 end in 0 or 5, so you only need two states for a DFA to accept them.  
> **username_1**: @Janoma: Indeed. The end of the question suggests the OP confuses upper bounds with lower bounds.  
> **username_7**: suggest the moderator(s) not be so fast to kill questions (esp unilaterally) that come from site newbies or undergraduates & rely more on the built-in voting mechanisms instead. arguably this problem relates to the complexity of integer division, integer remainder, primality testing, factoring, gcd etc (lower bounds on which are mostly deep open questions)  
> **username_7**: here is an example of a deep link between regular languages, integer division, and a premiere open problem in math/CS, the collatz conjecture: Jeﬀrey O. Shallit and David W. Wilson (1991), The “3x + 1” Problem and Finite Automata, Bulletin of the EATCS (European Association for Theoretical Computer Science), No. 46, 1991, pp. 182–185.  
> **username_7**: but this question could also be construed to be asking about DFA minimization which is also a well studied problem see eg [how do you normalize/minimize a FSM](http://stackoverflow.com/questions/1105779/how-do-you-normalize-a-finite-state-machine)  

---

## 2 answers

### Answer by username_9 on 2012-01-29. Score: 32 | Accepted answer

There is a known formula for minimum number of states for such a finite automaton. This depends on $n$ as well as the radix $R$ of the underlying positional representation.

If $n$ is coprime to $R$, then the minimal number of states is $n$. However, when $n$ shares a factor with the radix then the situation is rather complicated. See Mathematica Journal Vol 3 Issue 11. ["Divisibility and State Complexity"](http://www.mathematica-journal.com/data/uploads/2011/01/Sutner.pdf) by Klaus Sutner.

> **Comments:**
> **username_0**: Exactly the sort of thing I was looking for. Thanks, I'll dive into the paper sometime soon.  
> **username_10**: The link seems broken  

---

### Answer by username_8 on 2015-04-16. Score: 9

There's another paper on the same subject: B. Alexeev, Minimal DFA for testing divisibility, J. Comput. Syst. Sci. 69 (2004), 235–243.


---

