fct_a = 16807
start_a = 634
fct_b = 48271
start_b = 301
divisor = 2147483647
divisor2 = 2 ** 16
def fmt_bits(x):
x = bin(x)[2:]
x = '0'*(16-len(x)) + x
return(x)
fmt_bits(2 ** 16 -1 )
So... I'm guessing we're not supposed to actually run the 40 million checks... but we could try
matches = 0
a = start_a
b = start_b
for i in range(4 * (10 ** 7)):
a *= fct_a
b *= fct_b
a = a % divisor
b = b % divisor
bin_a = bin(a)[2:]
if (a% divisor2)== (b % divisor2):
matches += 1
matches
Well.. okay. I suspect that there is some repeating cycle where the same pattern will show up over and over.
Now we've changed the logic a bit and we will keep a sequence going for each generator of multiples of 4 for a and multiples of 8 for b. We'll then compare those sequences one by one.
matches = 0
a = start_a
b = start_b
list_a = []
list_b = []
hits = [0, 0]
while min(hits) < 5*10**6:
a *= fct_a
b *= fct_b
a = a % divisor
b = b % divisor
if a % 4 == 0 :
list_a.append(a)
hits[0] = hits[0] + 1
if b % 8 == 0 :
list_b.append(b)
hits[1] = hits[1] + 1
for a, b in zip(list_a, list_b):
if (a% divisor2)== (b % divisor2):
matches += 1
matches
mmmm yea so I feel like this one was supposed to be solved in a fancier way but... not sure that I see it.