Fibonacci series in bit string

Question

I am working on Fibonacci series but in bit string which can be represented as:

f(0)=0;
f(1)=1;
f(2)=10;
f(3)=101;
f(4)=10110;
f(5)=10110101;

Secondly, I have a pattern for example '10' and want to count how many times this occurs in particular series, for example, the Fibonacci series for 5 is '101101101' so '10' occur 3 times.

my code is running correctly without error but the problem is that it cannot run for more than the value of n=45 I want to run n=100 can anyone help? I only want to calculate the count of occurrence

n=5
fibonacci_numbers = ['0', '1']
for i in range(1,n):
    fibonacci_numbers.append(fibonacci_numbers[i]+fibonacci_numbers[i-1])
#print(fibonacci_numbers[-1])
print(fibonacci_numbers[-1])
nStr = str (fibonacci_numbers[-1])
pattern = '10'
count = 0
flag = True
start = 0
while flag:
    a = nStr.find(pattern, start)

    if a == -1:
        flag = False
    else:
        count += 1
        start = a + 1
print(count)

Answer 1

This is a fun one! The trick is that you don't actually need that giant bit string, just the number of 10s it contains and the edges. This solution runs in O(n) time and O(1) space.

from typing import NamedTuple

class FibString(NamedTuple):
    """First digit, last digit, and the number of 10s in between."""
    first: int
    tens: int
    last: int

def count_fib_string_tens(n: int) -> int:
    """Count the number of 10s in a n-'Fibonacci bitstring'."""

    def combine(b: FibString, a: FibString) -> FibString:
        """Combine two FibStrings."""
        tens = b.tens + a.tens
        # mind the edges!
        if b.last == 1 and a.first == 0:
            tens += 1
        return FibString(b.first, tens, a.last)

    # First two values are 0 and 1 (tens=0 for both)
    a, b = FibString(0, 0, 0), FibString(1, 0, 1)

    for _ in range(1, n):
        a, b = b, combine(b, a)

    return b.tens  # tada!

I tested this against your original implementation and sure enough it produces the same answers for all values that the original function is able to calculate (but it's about eight orders of magnitude faster by the time you get up to n=40). The answer for n=100 is 218922995834555169026 and it took 0.1ms to calculate using this method.

Answer 2

The nice thing about the Fibonacci sequence that will solve your issue is that you only need the last two values of the sequence. 10110 is made by combining 101 and 10. After that 10 is no longer needed. So instead of appending, you can just keep the two values. Here is what I've done:

n=45
fibonacci_numbers = ['0', '1']
for i in range(1,n):
    temp = fibonacci_numbers[1]
    fibonacci_numbers[1] = fibonacci_numbers[1] + fibonacci_numbers[0]
    fibonacci_numbers[0] = temp

Note that it still uses a decent amount of memory, but it didn't give me a memory error (it does take a bit of time to run though).

I also wasn't able to print the full string as I got an OSError [Errno 5] Input/Output error but it can still count and print that output.

---

For larger numbers, storing as a string is going to quickly cause a memory issue. In that case, I'd suggest doing the fibonacci sequence with plain integers and then converting to bits. See here for tips on binary conversion.

While the regular fibonacci sequence doesn't work in a direct sense, consider that 10 is 2 and 101 is 5. 5+2 doesn't work - you want 10110 or an or operation 10100 | 10 yielding 22; so if you shift one by the length of the other, you can get the result. See for example

x = 5
y = 2
(x << 2) | y
>> 22

Shifting x by the number of bits representing y and then doing a bitwise or with | solves the issue. Python summarizes these bitwise operations well here. All that's left for you to do is determine how many bits to shift and implement this into your for loop!

---

For really large n you will still have a memory issue shown in the plot: '

Answer 3

Finally i got the answer but can someone explain it briefly why it is working

def count(p, n):
    count = 0
    i = n.find(p)
    while i != -1:
        n = n[i + 1:]
        i = n.find(p)
        count += 1
    return count


def occurence(p, n):
    a1 = "1"
    a0 = "0"
    lp = len(p)
    i = 1
    if n <= 5:
        return count(p, atring(n))
    while lp > len(a1):
        temp = a1
        a1 += a0
        a0 = temp
        i += 1
        if i >= n:
            return count(p, a1)
    fn = a1[:lp - 1]
    if -lp + 1 < 0:
        ln = a1[-lp + 1:]
    else:
        ln = ""
    countn = count(p, a1)
    a1 = a1 + a0
    i += 1
    if -lp + 1 < 0:
        lnp1 = a1[-lp + 1:]
    else:
        lnp1 = ""
    k = 0
    countn1 = count(p, a1)
    for j in range(i + 1, n + 1):
        temp = countn1
        countn1 += countn
        countn = temp
        if k % 2 == 0:
            string = lnp1 + fn
        else:
            string = ln + fn
        k += 1
        countn1 += count(p, string)
    return countn1


def atring(n):
    a0 = "0"
    a1 = "1"
    if n == 0 or n == 1:
        return str(n)
    for i in range(2, n + 1):
        temp = a1
        a1 += a0
        a0 = temp
    return a1


def fn():


    a = 100
    p = '10'
    print( occurence(p, a))




if __name__ == "__main__":
    fn()