%I #25 Apr 27 2020 17:34:06
%S 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,
%T 11,12,9,5,11,18,23,21,24,29,27,20,21,29,32,27,25,28,23,15,14,21,25,
%U 22,23,27,24,17,15,20,21,17,14,15,11,6,13,22,29,27,32,39,37
%N Number of distinct nonempty subsequences of the binary expansion of n.
%C The subsequence does not need to consist of adjacent terms.
%H Andrew Howroyd, <a href="/A293722/b293722.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>
%F a(2^n) = 2n + 1.
%F a(2^n-1) = n if n>0.
%F a(n) = A293170(n) - 1. - _Andrew Howroyd_, Apr 27 2020
%e a(4) = 5 because 4 = 100_2, and the distinct subsequences of 100 are 0, 1, 00, 10, 100.
%e Similarly a(7) = 3, because 7 = 111_2, and 111 has only three distinct subsequences: 1, 11, 111.
%e a(9) = 10: 9 = 1001_2, and we get 0, 1, 00, 01, 10, 11, 001, 100, 101, 1001.
%o (Python)
%o def a(n):
%o if n == 0: return 1
%o r, l = 1, [0, 0]
%o while n:
%o r, l[n%2] = 2*r - l[n%2], r
%o n >>= 1
%o return r - 1
%Y Cf. A141297.
%Y If the empty subsequence is also counted, we get A293170.
%K nonn,base,easy
%O 0,3
%A _Orson R. L. Peters_, Oct 15 2017
%E Terms a(50) and beyond from _Andrew Howroyd_, Apr 27 2020