playing with fibonacci riddles and primes

fibonacci_riddle.py

######################################
# Let Fib(n) be the string formed by concatenating the first n sequential 
#   Fibonacci numbers (i.e. Fib(0) = 1, Fib(1) = 11, Fib(2) = 112, …). 
##
# Find the first ten-digit prime number that occurs as twenty sequential 
# digits in Fib(n).
#
# This prime number is the result (2584418167)
######################################
# Jon Robbins
######################################
from math import sqrt
from itertools import count, islice
from io import StringIO

###
# fibonacci sequence generator
def Fr(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1
    elif n > 1:
        return F(n-1) + F(n-2)
    else:
        #error
        return 0

def F(n):
    #print('f of ' ,n)
    return round(((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5)))

def Fiter():
    a,b = 0,1
    yield a
    yield b
    while True:
        a, b = b, a + b
        yield b

def Fsub(n):
    i = 0    
    for cur in Fiter():
        if i >= n:
            break
        i += 1
    return cur

    
def FsubG(startNumber, endNumber):
    for cur in Fiter():
        if cur > endNumber:
            return
        if cur >= startNumber:
            yield cur
    return
        
#Let Fib(n) be the string formed by concatenating the first n sequential 
# Fibonacci numbers (i.e. Fib(0) = 1, Fib(1) = 11, Fib(2) = 112, …). 

def Fib(n):
    seq = ''
    for i in range(1,n+1):
        seq += str(int(Fsub(i)))
    return seq

def FibR(n):
    seq = ""
    if n == 0:
        return str(F(n))
    elif n > 0:
        return Fib(n-1) + str(F(n))
    else:
        return 'error'

def FibIO(n):
    seq = StringIO()
    for i in range(0,n):
        seq.write(str(F(n)))

    return seq.getvalue()

def isPrime(n):
    return n > 1 and all(n%i for i in islice(count(2), int(sqrt(n)-1)))

def scanChunk(s, startPos, chunkSize):    
    if len(s) < chunkSize:
        return False
    
    chunk = ''
    stopPos = startPos + chunkSize

    if (stopPos) > len(s) :
            return False
          
    chunk = s[startPos:stopPos]
    #print('chunk: ',chunk,' | start: ', startPos, ' | stop: ', stopPos)
        
    if isPrime(float(chunk)):
        return chunk
    else:
        return False

    
# Find the Nth ten-digit prime number that occurs as ten sequential 
# digits in Fib(n). Go to {prime number}.com 
# to proceed with the interview.   
def aSearch(results, nItem = 1, searchLen = 10):
    sFib = ''
    seqDigs = ''
    startPos = 0
    pcount = 0
    found = False
    nFibs = round(nItem/2)
    if nFibs < 30:
        nFibs = 30

    while (found == False):
        #print("regenerating fib string (", nFibs, ")")
        sFib = Fib(nFibs)
        fLen = len(sFib)

        #print("##########")
        #print("Fib#",nFibs,": ", sFib)
        #print("length: ", fLen)
        #print('startpos: ',startPos, '| primecount', pcount)
        
        if fLen < searchLen:
            nFibs += 1
            continue

        for startPos in islice(count(startPos), fLen):
            
            seqDigs = scanChunk(sFib, startPos, searchLen)
            if seqDigs:
                pcount += 1
                #print('startpos: ',startPos, '| primecount', pcount, '| prime(s) : ', seqDigs )                
                if pcount == nItem:
                    print('***** result is: ' + seqDigs + ' *****')
                    results[seqDigs] = pcount
                    found = True
                    return results
            elif (fLen < (startPos + searchLen)):
                break


        nFibs += 1
        
    return "no result (limit)"
    

#By taking each pair of digits modulo 26, you will have 5 numbers between 0 and 25.
def dig_to_alpha_index(snum):
    s = ''
    nOut = []
    for c in snum:
        s += c
        if len(s) == 2:
            m = int(s) % 26
            nOut.append(m)
            m = 0
            s = ''

    #print(nOut)
    return nOut

#Map those five numbers to the alphabet using A=0, B=1, ...
def index_to_alpha(n):
        return chr(ord('A') + n)

def convert_alpha_index(arIndex):
    sout = ''
    for i in arIndex:
        sout += index_to_alpha(i)
    return sout

def convert_int_to_string(snum):
    ar = dig_to_alpha_index(snum)
    return convert_alpha_index(ar)
    
results = {}
#aSearch(results, 5)
#aSearch(results, 10)
aSearch(results, 1333)
aSearch(results, 4477)
print(results)


for key, value in results.items():
    print(value, ':', key, ':', convert_int_to_string(key))