A239091 Prefix overlap of dictionary consisting of binary expansions of 0 through n.

0, 1, 2, 3, 5, 6, 8, 9, 12, 14, 17, 18, 21, 23, 26, 27, 31, 34, 38, 40, 44, 47, 51, 52, 56, 59, 63, 65, 69, 72, 76, 77, 82, 86, 91, 94, 99, 103, 108, 110, 115, 119, 124, 127, 132, 136, 141, 142, 147, 151, 156, 159, 164, 168, 173, 175, 180, 184, 189, 192, 197, 201, 206

Offset: 1

Author

N. J. A. Sloane, Mar 22 2014

Keywords

• nonn
• base

Comments

The prefix overlap of a dictionary is the sum of the prefix overlaps between successive words.

Partial sums of A238845.

Examples

			For n=5 the dictionary is
0
1
10
11
100
101
and the successive prefix overlaps are 0,1,1,1,2, whose sum is a(5)=5.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..10000
• Rodica Simion and Herbert S. Wilf, The distribution of prefix overlap in consecutive dictionary entries, SIAM J. Algebraic Discrete Methods, 7(1986), no. 3, 470--475. MR0844051.

Crossrefs

Cf. A000523, A011371, A061168, A238845, A239092.

Formula

a(n) = A061168(n+1) - A011371(n+1) + A000523(n+1). - Alan Michael Gómez Calderón, Jul 17 2025