19
1
A subsequence is any sequence that you can get from another by deleting any amount of characters. The distinct non-empty subsequences of 100
are 0
, 1
, 00
, 10
, 100
. The distinct non-empty subsequences of 1010
are 0
, 1
, 00
, 01
, 10
, 11
, 010
, 100
, 101
, 110
, 1010
.
Write a program or function that given a positive integer n returns the number of distinct non-empty subsequences of the binary expansion of n.
Example: since 4
is 100
in binary, and we saw that it had five distinct non-empty subsequences above, so f(4) = 5
. Starting from n = 1, the sequence begins:
1, 3, 2, 5, 6, 5, 3, 7, 10, 11, 9, 8, 9, 7, 4, 9, 14, 17, 15, 16, 19, 17, 12
However, your program must work for any n < 250 in under a second on any modern machine. Some large examples:
f(1099511627775) = 40
f(1099511627776) = 81
f(911188917558917) = 728765543
f(109260951837875) = 447464738
f(43765644099) = 5941674
4I disagree with the time restriction. – ATaco – 2017-10-16T01:24:58.190
1
This sounded really familiar, especially after looking at the plot. Turns out I looked into a very closely related sequence earlier this year, but I counted the number of distinct binary numbers, not binary strings, you get when taking subsequences (so I discounted leading zeros). I had even sandboxed it, but due to the equivalence in the Math.SE post, it would have been a dupe of some Stern-Brocot challenge. The plot of your sequence is a bit nicer (i.e. more chaotic) though. :)
– Martin Ender – 2017-10-16T09:36:30.8975@ATaco The time restriction has a good reason. There is an efficient algorithm, and it is interesting yet well golfable. If I don't have a time restriction I feel that nearly every answer would simply brute force all possible subsequences, which very, very quickly wouldn't work anymore. In a sense they're non-answers. – orlp – 2017-10-16T11:23:34.800