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

1, 2, 3, 3, 5, 4, 7, 4, 9, 6, 11, 5, 13, 8, 15, 5, 17, 10, 19, 7, 21, 12, 23, 6, 25, 14, 27, 9, 29, 16, 31, 6, 33, 18, 35, 11, 37, 20, 39, 8, 41, 22, 43, 13, 45, 24, 47, 7, 49, 26, 51, 15, 53, 28, 55, 10, 57, 30, 59, 17, 61, 32, 63, 7, 65, 34, 67, 19, 69, 36, 71, 12, 73, 38, 75, 21, 77

Offset

1,2

Comments

a(n) = n for all odd n.

Links

Table of n, a(n) for n=1..77.

Formula

Recurrence: a(1)=1; then a(2n)=a(n)+1, a(2n+1)=2n+1. - Benoit Cloitre, Jun 04 2007

a(n) = A000265(n) + A007814(n) = n/2^A007814(n) + A007814(n). - Ralf Stephan, Jul 07 2013

Example

a(12) = 5.

Prog

(PARI) a(n)=n/2^valuation(n, 2)+valuation(n, 2) - Ralf Stephan, Jul 07 2013
(PARI) a(n)=if(n<2, 1, if(n%2, n, a(n/2)+1)) - Benoit Cloitre, Jun 04 2007

Crossrefs

Sequence in context: A135533 A296075 A318678 * A064920 A064916 A062854

Adjacent sequences: A119671 A119672 A119673 * A119675 A119676 A119677

Keyword

nonn

Author

Mirko Rahn (rahn(AT)ira.uka.de), Jun 12 2006

Status

approved