Count the total number of subsets without consecutive elements
I'm trying to solve a rather tricky problem with combinatorics and subset counting. First of all, assume that we have given a set A = {1, 2, 3, ... N}, where N <= 10 ^ (18). Now we want to count subsets that do not have consecutive numbers in their representation.
Example
Let, say, N = 3 and A = {1,2,3}. There are 2 ^ 3 complete subsets, but we don't want to count subsets (1,2), (2,3) and (1,2,3). So, overall on this question, we want to answer 5 because we only want to count the remaining 5 subsets. These subsets (empty subset) are (1), (2), (3), (1,3). We also want to print the result modulo 10 ^ 9 + 7.
What have I done so far
I thought it needed to be solved using dynamic programming with two states (we take the i-th element or not), but then I saw that N could go up to 10-18, so I thought it should be solved using mathematical formula. Could you please give me some advice on where I should start getting the formula.
Thanks in advance.
source to share
Take a look at How many subsets does not contain consecutive elements? on the stock exchange of mathematical statistics.
They conclude that the number of inconsistent subsets in the set {1,2,3 ... n} is fib (n + 2), where fib is the function that calculates the Fibonacci sequence for n + 2. Your solution n = 3 corresponds to this decision. If you can implement the Fibonacci algorithm, then you can solve this problem, but solving the question for a number up to 10 ^ 18 will still be a problem.
As mentioned in the comments, you can check out the fast doubling algorithm on Hacker Earth .
It will find Fibonacci numbers in O (log n).
source to share