A165956 a(0) = 1. For n >= 1, a(n) = the number of earlier terms that, when written in binary, are substrings in binary n.

1, 1, 2, 2, 4, 4, 4, 2, 8, 8, 5, 6, 9, 7, 7, 4, 11, 11, 10, 10, 12, 8, 9, 10, 14, 13, 11, 11, 14, 12, 10, 4, 13, 13, 13, 13, 12, 13, 13, 14, 18, 17, 10, 15, 19, 18, 16, 13, 18, 18, 20, 17, 26, 21, 19, 21, 22, 21, 26, 24, 20, 21, 12, 5, 14, 14, 14, 14, 15, 17, 17, 19, 19, 16, 23, 22, 21

Offset

0,3

Comments

If we instead had an offset of 1 and a(1)=1, then we would have sequence A122954.

Links

John Tyler Rascoe, Table of n, a(n) for n = 0..10000

Example

13 in binary is 1101. The earlier terms that, when written in binary, are substrings in 1101 are: a(0)=1, a(1)=1, a(2) = 2 = 10 in binary, a(3) = 2 = 10 in binary, a(7) = 2 = 10 in binary, a(10) = 5 = 101 in binary, and a(11) = 6 = 110 in binary. There are 7 such terms, so a(13) = 7.

Prog

(Python)
from collections import Counter
def A165956_list(nmax):
    A, C = [1], Counter()
    for n in range(1, nmax+1):
        b = bin(n)[2:]
        C.update({bin(A[-1])[2:]})
        A.append(sum(C[i] for i in C if b.find(i) != -1))
    return A # John Tyler Rascoe, Mar 11 2023

Crossrefs

Cf. A122954.

Sequence in context: A042946 A037202 A227091 * A263991 A065285 A302437

Adjacent sequences: A165953 A165954 A165955 * A165957 A165958 A165959

Keyword

base,nonn

Author

Leroy Quet, Oct 01 2009

Extensions

More terms from Sean A. Irvine, Nov 09 2009

Status

approved