278 : 半素数の線型結合

いくつかの整数$1 < a_1 < a_2 < \dots < a_n$に対し、次の線形の組み合わせについて考える。 $q_1 a_1 + q_2 a_2 + \dots + q_n a_n = b$、ただし$q_k ≥ 0$は整数のみとする。

与えられた整数列$a_k$に対して、$b$は全ての値を網羅しないかもしれないことに注意せよ。 例えば、$a_1 = 5, a_2 = 7$のとき、$b$が 1, 2, 3, 4, 6, 8, 9, 11, 13, 16, 18 または 23 となるような $q_1 ≥ 0, q_2 ≥ 0$は存在しない。 実際、23 は$a_1 = 5, a_2 = 7$に対して$b$の値とならない最大の数である。 これを$f(5, 7) = 23$とする。 同様に、$f(6, 10, 15) = 29, f(14, 22, 77) = 195$であることを示せる。

$p, q, r$が素数で$p < q < r < 5000$であるとしたとき、$\sum f(pq,pr,qr)$を求めよ。