## Linear Combinations of Semiprimes

### Problem 278

Published on Saturday, 13th February 2010, 05:00 am; Solved by 617; Difficulty rating: 50%
Given the values of integers 1 < `a`_{1} < `a`_{2} <... < `a`_{n}, consider the linear combination

`q`_{1}`a`_{1} + `q`_{2}`a`_{2} + ... + `q`_{n}`a`_{n} = `b`, using only integer values `q`_{k} ≥ 0.

Note that for a given set of `a`_{k}, it may be that not all values of `b` are possible.

For instance, if `a`_{1} = 5 and `a`_{2} = 7, there are no `q`_{1} ≥ 0 and `q`_{2} ≥ 0 such that `b` could be

1, 2, 3, 4, 6, 8, 9, 11, 13, 16, 18 or 23.

In fact, 23 is the largest impossible value of `b` for `a`_{1} = 5 and `a`_{2} = 7.

We therefore call `f`(5, 7) = 23.

Similarly, it can be shown that `f`(6, 10, 15)=29 and `f`(14, 22, 77) = 195.

Find ∑ `f`(`p*q,p*r,q*r`), where `p`, `q` and `r` are prime numbers and `p` < `q` < `r` < 5000.