A293722 Number of distinct nonempty subsequences of the binary expansion of n.

1, 1, 3, 2, 5, 6, 5, 3, 7, 10, 11, 9, 8, 9, 7, 4, 9, 14, 17, 15, 16, 19, 17, 12, 11, 15, 16, 13, 11, 12, 9, 5, 11, 18, 23, 21, 24, 29, 27, 20, 21, 29, 32, 27, 25, 28, 23, 15, 14, 21, 25, 22, 23, 27, 24, 17, 15, 20, 21, 17, 14, 15, 11, 6, 13, 22, 29, 27, 32, 39, 37

Offset

0,3

Comments

The subsequence does not need to consist of adjacent terms.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..4096

Geeks for Geeks, Count Distinct Subsequences

Formula

a(2^n) = 2n + 1.

a(2^n-1) = n if n>0.

a(n) = A293170(n) - 1. - Andrew Howroyd, Apr 27 2020

Example

a(4) = 5 because 4 = 100_2, and the distinct subsequences of 100 are 0, 1, 00, 10, 100.
Similarly a(7) = 3, because 7 = 111_2, and 111 has only three distinct subsequences: 1, 11, 111.
a(9) = 10: 9 = 1001_2, and we get 0, 1, 00, 01, 10, 11, 001, 100, 101, 1001.

Prog

(Python)
def a(n):
    if n == 0: return 1
    r, l = 1, [0, 0]
    while n:
        r, l[n%2] = 2*r - l[n%2], r
        n >>= 1
    return r - 1

Crossrefs

Cf. A141297.

If the empty subsequence is also counted, we get A293170.

Sequence in context: A057028 A195112 A276618 * A364254 A153152 A153153

Adjacent sequences: A293719 A293720 A293721 * A293723 A293724 A293725

Keyword

nonn,base,easy

Author

Orson R. L. Peters, Oct 15 2017

Extensions

Terms a(50) and beyond from Andrew Howroyd, Apr 27 2020

Status

approved