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,3

Comments

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

Partial sums of A238845.

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.

Formula

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

Example

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.

Crossrefs

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

Sequence in context: A331072 A096276 A371970 * A272341 A075725 A049407

Adjacent sequences: A239088 A239089 A239090 * A239092 A239093 A239094

Keyword

nonn,base

Author

N. J. A. Sloane, Mar 22 2014

Status

approved