cp's OEIS Frontend

A293722 Number of distinct nonempty subsequences of the binary expansion of n.

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