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

Author

N. J. A. Sloane, Oct 18 2017

Keywords

• nonn
• look
• base

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..4096
• Geeks for Geeks, Count Distinct Subsequences

Crossrefs

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

Programs

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

Extensions

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