Linear Combinations of Semiprimes

Given the values of integers $1 < a_1 < a_2 < \dots < a_n$, consider the linear combination $q_1 a_1+q_2 a_2 + \dots + q_n a_n=b$, using only integer values $q_k \ge 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 \ge 0$ and $q_2 \ge 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 $\displaystyle \sum f( p\, q,p \, r, q \, r)$, where $p$, $q$ and $r$ are prime numbers and $p < q < r < 5000$.

To find the value of $f(a_1, a_2, …, a_n)$ for a given set of positive integers $a_k$, we can use a dynamic programming approach.

We will create a boolean array `possible` with size `b+1`, where `possible[b]` will be `True` if $b$ is possible to obtain using the given set of integers $a_k$, and `False` otherwise.

Initially, we set `possible[0]` to `True`, since we can always obtain $b=0$ by setting all $q_k$ to $0$.

Then, for each integer $a_k$ in the set, we iterate over all values of $b$ from $a_k$ to the target value. For each value of $b$, we check if there exists a combination of $q_k$’s such that $b – a_k$ is possible to obtain. If it is, then we set `possible[b]` to `True`.

Finally, we iterate from the target value backwards until we find the largest value of $b$ such that `possible[b]` is `False`. We return this value as the result of $f(a_1, a_2, …, a_n)$.

Now, we can write the Python code to solve this problem:

“`python
def f(a):
b = sum(a)
possible = [False] * (b+1)
possible[0] = True

for ak in a:
for bi in range(ak, b+1):
if possible[bi – ak]:
possible[bi] = True

for bi in range(b, -1, -1):
if not possible[bi]:
return bi

# Sum of f(p*q, p*r, q*r) for primes p, q, r
primes = [2, 3, 5, 7, 11, 13, …] # List of prime numbers less than 5000
total_sum = 0

for pi in range(len(primes)-2):
p = primes[pi]
for qi in range(pi+1, len(primes)-1):
q = primes[qi]
for ri in range(qi+1, len(primes)):
r = primes[ri]
total_sum += f([p*q, p*r, q*r])

print(total_sum)
“`

Note: In the code above, `…` represents the remaining prime numbers less than 5000. In practice, you will need to replace it with the complete list of prime numbers. Also, make sure you have an efficient algorithm to generate the prime numbers up to 5000.

More Answers: