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.
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. \$\endgroup\$sequence_lengh
in snippet isn't quite correct. I have difficulties recognising said snippet inThe full program
: could you factor out the predicate (nth_place()
)? \$\endgroup\$