# Finding the length of the longest run in a very long generated sequence

So I am trying to calculate the longest run of True's in a boolean sequence in Python. The sequence is very long (>10^10) and so it's not possible to generate it in reasonable time, let alone store it in memory. Instead, I generate the n-th item in the sequence. Is a more efficient algorithm in terms of speed possible, without multiprocessing or statistical analysis of the sequence? Abstracting away the details of the generator, the code looks like this:

run = 1
record = 1
i = 0
while i < sequence_length:
if nth_place(i):
for j in range(i-1, -1, -1):
if nth_place(j): run += 1
else: break

for j in range(i+1, sequence_lengh):
if nth_place(i): run += 1
else:
if run > record: record = run
run = 1
i = j
break

i += (record + 1)


Description: Instead of checking every position, the algorithm makes jumps of size of current record+1. If the result is False then it jumps again and repeats - this ensures that the longest run that could be missed has at most the length of current record. If the result is True, then it starts counting backwards until it reaches a False. Then it picks up from (i+1)-th place and continues counting forwards until it reaches a False. If the counted run is longer than the current record, the record gets updated. i gets updated too, and the algorithm repeats, now jumpring from the current position.

Full description as follows:
I am trying to calculate the longest possible run of pairs of numbers of format (6n+1,6n-1) between pairs of twin primes, that are created by the first m primes.
For this, I have a list of m primes that are greater than 3 and for each prime in the list there is associated boolean sequence of according length, with False everywhere except at positions p//3 and p-(p//3)-1. For example, given a list [5,7], the list of associated sequences is [[0,1,0,1,0],[0,0,1,0,1,0,0]].
The long sequence that the question is about is then generated by cyclically iterating the sequences and storing the logical disjunction. For example:

01010010100101001010010100101001010
00101000010100001010000101000010100
-----------------------------------
01111010110101001010010101101011110


Generating the sequence is fine for small lists of primes, but as the number of primes increases, the sequence grows with primorial time complexity, which is worse than factorial. Therefore I can't generate the whole sequence, but only get the n-th term. The full program is here:
(the function in question is count_ones)

import math

def is_prime(n): #checks whether a given number is prime
if n == 2: return True
if n % 2 == 0 or n <= 1: return False

sqr = int(math.sqrt(n)) + 1

for divisor in range(3, sqr, 2):
if n % divisor == 0: return False
return True

def next_prime(current_prime): #returns the next prime
if current_prime == 2: return 3

counter = current_prime + 2
while 1:
if is_prime(counter): return counter
counter += 2

def get_pattern(n): #generates a pattern of a prime
lis = [False for x in range(n)]
lis[n//3] = True
lis[n-(n//3)-1] = True
return lis

def list_product(lis): #computes the product of a list of numbers
product = 1
for i in range(len(lis)): product *= lis[i]
return product

def nth_place(patterns,primes,n):
for a,b in zip(patterns, primes):
if a[n%b]: return True
else:
return False

def count_ones(patterns,primes):
if primes[-1] == 5: return 1 #skip trivial case with a single prime 5

for i in patterns: i = dict(enumerate(i))
primes = tuple(primes)
patterns = tuple(patterns)

run = 1
record = 1
#since the sequence is symmetrical, we'll need only half of it
sequence_length = list_product(primes)//2 + 1
i = 0

while i < sequence_length:
if nth_place(patterns, primes, i):
for j in range(i-1, -1, -1):
if nth_place(patterns, primes, j): run += 1
else: break

for j in range(i+1, sequence_length):
if nth_place(patterns, primes, j): run += 1
else:
if run > record: record = run
run = 1
i = j
break

i += (record + 1)

return record

def main():
number_of_primes = 6 #change this value
prime = 3
primes = []
patterns = []

for i in range(number_of_primes):
prime = next_prime(prime)
primes.append(prime)
patterns.append(get_pattern(prime))

record = count_ones(patterns,primes)
print('{} - {}'.format(primes,record))

main()


A minor and obvious improvement that I missed in the main loop of count_ones function: allocate a separate variable to hold the value of record+1 and recalculate it only when the current record itself changes, instead of every iteration of the loop.

• It would help if you could add the implementation of nth_place. This way, your code could actually be run by the reviewers and they can check themselves if the alternatives they propose are actually better. – Graipher Jun 27 '17 at 11:58
• @Graipher this is actually a bit tricky to explain without context. I tried to explain how the whole program works. – ZyTelevan Jun 27 '17 at 16:51
• sequence_lengh in snippet isn't quite correct. I have difficulties recognising said snippet in The full program: could you factor out the predicate (nth_place())? – greybeard Jan 10 '18 at 10:29
• @greybeard sorry for causing confusion, I edited the full program to be more analogous to the snippet. – ZyTelevan Jan 10 '18 at 17:21

Checking from the end of a promising index range intending to leap as far ahead as possible, thereby reducing the number of checks, is the way to go.
There is nothing special about the indexes you start to check from:
Why start checking upwards without knowing there's a new record?

Work in progress: not named, not documented, not tested

target = 1
''' record if met '''
good = 0
''' number of good indices seen '''
while bad < length - target:
goal = bad + target  # if predicate(bad+1 .. goal): new record
for check in range(goal, bad + good, -1):  # exclude known good
if not predicate(check):
good = goal - check  # may be lower than before
break
else:  # new record!
for goal in range(goal + 1, length):
if not predicate(goal):
good = 0
break

(Where record lengths are more likely at the end of a sequence, reverse before or invert range()s & such.)
• (What to call ugly?) – greybeard Jan 10 '18 at 10:27