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

Author

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

Keywords

• nonn
• easy

Comments

a(n) = n for all odd n.

Examples

			a(12) = 5.
		

Links

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

Programs

Mathematica

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

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

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