A247374 Number of button presses required to try every combination of a binary combination lock with n number buttons.

3, 8, 17, 38, 77, 165, 331, 698, 1397, 2921, 5843, 12149, 24299, 50315, 100631, 207698, 415397, 855105, 1710211, 3512801, 7025603, 14403923, 28807847, 58967773, 117935547, 241071395, 482142791, 984343883, 1968687767, 4014934295, 8029868591, 16360277378, 32720554757, 66607912625, 133215825251, 270969218153

Offset: 1

Author

Elliott Line, Sep 15 2014

Keywords

• nonn

Comments

This type of lock is quite common in the real world. The lock has typically 13 'number' buttons (actually 0 1 2 3 4 5 6 7 8 9 X Y Z), plus a C (for clear) button, and a knob to turn to 'try' the combination. The way it functions is that the unlocking code is an n-digit binary number. By pressing one of the number buttons, you change the corresponding digit from 0 to 1. Pressing C reverts all digits to 0.

Examples

			A lock with four number buttons (plus try and clear) would have 16 combinations to try, namely 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111.
All combinations can be tried in 38 presses using the following sequence of presses:
T 1 T 2 T 3 T 4 T C 2 T 3 T 4 T C 3 T 4 T 1 T C 4 T 1 T 2 T C 1 3 T C 2 4 T. The T (tries) will attempt the combinations in the following order: 0000, 1000, 1100, 1110, 1111, 0100, 0110, 0111, 0010, 0011, 1011, 0001, 1001, 1101, 1010, 0101.
		

Crossrefs

Cf. A000079, A014495, A014314.

Formula

a(n) = A000079(n) + A014495(n) + A014314(n). A000079 is how many times the 'try' button (or knob) is pressed. A014495 is how many times the C (clear) button is pressed. A014314 is how many times the number buttons are pressed.

Conjectured to be D-finite with recurrence: n*a(n) +2*(-2*n+1)*a(n-1) +(n-2)*a(n-2) +2*(7*n-10)*a(n-3) +4*(-5*n+11)*a(n-4) +8*(n-3)*a(n-5)=0. - R. J. Mathar, Nov 19 2019