login
Number of distinct nonempty subsequences of the binary expansion of n.
2

%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