A293170 Number of distinct subsequences of the binary expansion of n.

2, 2, 4, 3, 6, 7, 6, 4, 8, 11, 12, 10, 9, 10, 8, 5, 10, 15, 18, 16, 17, 20, 18, 13, 12, 16, 17, 14, 12, 13, 10, 6, 12, 19, 24, 22, 25, 30, 28, 21, 22, 30, 33, 28, 26, 29, 24, 16, 15, 22, 26, 23, 24, 28, 25, 18, 16, 21, 22, 18, 15, 16, 12, 7, 14, 23, 30, 28, 33, 40, 38

Offset

0,1

Links

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

Geeks for Geeks, Count Distinct Subsequences

Prog

(PARI) a(n)={if(!n, 2, my(M=Map(Mat([1, 1]))); while(n, my(R=Mat(M)[, 1]); for(i=1, #R, mapput(M, bitor(R[i]<<1, bittest(n, 0)), 1)); n>>=1); #M)} \\ Andrew Howroyd, Mar 01 2020
(PARI) a(n)={if(!n, 2, my(p=vector(2), s=1); while(n, my(k=1+bitand(n, 1), t=s); s = 2*s-p[k]; p[k] = t; n>>=1); s)} \\ Andrew Howroyd, Mar 26 2020

Crossrefs

a(n) = A293722(n) + 1.

Sequence in context: A357709 A238790 A238787 * A341469 A101200 A122585

Adjacent sequences: A293167 A293168 A293169 * A293171 A293172 A293173

Keyword

nonn,look,base

Author

N. J. A. Sloane, Oct 18 2017

Extensions

Terms a(50) and beyond from Andrew Howroyd, Mar 01 2020

Status

approved