Go to Problem

It’s easy since I spent only 30+ minutes. So try it before read my thought and you’ll have some fun.

  • I ‘guess’ it would be very slow to check all primes one by one.
  • [1..9] are all Harshad numbers (seeds).
  • Take one seed, add one digit to it and check if it’s valid. For example, take 2, check [20..29]. All valid numbers are new seeds.
  • Check if a new seed is also a strong Harshad number.
  • If a seed is a strong Harshad number, append one digit to it and check if it’s a ‘strong, right truncatable Harshad primes’. For example, 201 is a strong Harshad number, check if [2010..2019] are primes.
  • Sum all valid primes, done.
  • This is actually a tree structure, solve it with BFS.
from sympy import isprime

K = 100000000000000

def add_digit(seed) :
  res = []

  k = seed[0] * 10
  p = seed[1]

  for i in range(10) :
    if (k + i) % (p + i) == 0 :
      res.append([k + i, p + i])

  return res

def check_primes(seed) :
  if not isprime(seed[0] // seed[1]) :
    return 0

  k = 10 * seed[0]

  if k >= K :
    return 0

  s = 0

  for i in range(1, 10, 2) :
    if isprime(k + i) :
      s += k + i

  return s

seeds_0 = [
  [1, 1], [2, 2], [3, 3], [4, 4], [5, 5],
  [6, 6], [7, 7], [8, 8], [9, 9]
]

seeds_1 = []

SSRTHP = 0

while len(seeds_0) > 0 :
  seeds_0, seeds_1 = [], seeds_0

  for seed in seeds_1 :
    if seed[0] >= K :
      continue

    seeds_0 += add_digit(seed)

  for seed in seeds_0 :
    SSRTHP += check_primes(seed)


print(SSRTHP)