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

Paolo Xausa, Table of n, a(n) for n = 1..10000

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.

Mathematica

Table[n/2^# + # & [IntegerExponent[n, 2]], {n, 100}] (* Paolo Xausa, Jul 24 2024 *)

Prog

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

Crossrefs

Sequence in context: A135533 A296075 A318678 * A064920 A064916 A062854

Adjacent sequences: A119671 A119672 A119673 * A119675 A119676 A119677

Keyword

nonn,easy

Author

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

Status

approved