A293170 - OEIS

%I #10 Mar 26 2020 20:56:04

%S 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,

%T 14,12,13,10,6,12,19,24,22,25,30,28,21,22,30,33,28,26,29,24,16,15,22,

%U 26,23,24,28,25,18,16,21,22,18,15,16,12,7,14,23,30,28,33,40,38

%N Number of distinct subsequences of the binary expansion of n.

%H Andrew Howroyd, <a href="/A293170/b293170.txt">Table of n, a(n) for n = 0..4096</a>

%H Geeks for Geeks, <a href="https://www.geeksforgeeks.org/count-distinct-subsequences/">Count Distinct Subsequences</a>

%o (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

%o (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

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

%K nonn,look,base

%O 0,1

%A _N. J. A. Sloane_, Oct 18 2017

%E Terms a(50) and beyond from _Andrew Howroyd_, Mar 01 2020