A293722 Number of distinct nonempty subsequences of the binary expansion of n.
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, 11, 12, 9, 5, 11, 18, 23, 21, 24, 29, 27, 20, 21, 29, 32, 27, 25, 28, 23, 15, 14, 21, 25, 22, 23, 27, 24, 17, 15, 20, 21, 17, 14, 15, 11, 6, 13, 22, 29, 27, 32, 39, 37
Offset: 0
Examples
a(4) = 5 because 4 = 100_2, and the distinct subsequences of 100 are 0, 1, 00, 10, 100. Similarly a(7) = 3, because 7 = 111_2, and 111 has only three distinct subsequences: 1, 11, 111. a(9) = 10: 9 = 1001_2, and we get 0, 1, 00, 01, 10, 11, 001, 100, 101, 1001.
Links
- Andrew Howroyd, Table of n, a(n) for n = 0..4096
- Geeks for Geeks, Count Distinct Subsequences
Programs
-
Python
def a(n): if n == 0: return 1 r, l = 1, [0, 0] while n: r, l[n%2] = 2*r - l[n%2], r n >>= 1 return r - 1
Formula
Extensions
Terms a(50) and beyond from Andrew Howroyd, Apr 27 2020
Comments