Some progress for the future me:

  • The problem can be reduced to a Combination Sum problem. In particular, we can generate the range of possible primes as the sum of the array (range can be from ord(a) * <some_value> to ord(z) * 1020). We can use a DP approach to solve this as we have a lot of incremental sum, however, storage might be an issue. Some trimming can be done to ensure the solution does not exceed the length
  • How the array.prod() for numpy works is that it wraps around 64-bit value (Mac/Linux behavior). In particular, the following snippet of code should help you understand what’s going on. Basically the result is modulo $2 ^ 64$. The negative sign can be obtained from casting a unsigned long long to a signed long long easily in C.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

a = [42 for _ in range(42)] + [43]
# Get the actual product
pre_sum = math.prod(a)

# Get the modulo 2 ** 64
pre_sum_mod = pre_sum % (2 ** 64)
print(pre_sum_mod)

# Now convert to numpy array
a = np.array(a)

# Using the product of numpy
post_sum = a.prod()
print(post_sum)

print(math.log2(pre_sum_mod - int(post_sum)))
  • Solution should be in C to enable quick brute forcing. An idea can be to initialize the first characters that must be in the candidate string, e.g 1aA and try to find a combination that satisfies the array.sum() == array.prod().