  A new generalisation of Goldbach's conjecture (GGC) - also generalising that
of Lemoine - is tested, introduced by the first author. It states that for
every pair of positive integers $m_1, m_2$, every sufficiently large integer
$n$ satisfying certain simple criteria can be expressed as $n=m_1p+m_2q$ for
some primes $p$ and $q$. GGC is checked up to $10^{12}d$ for all (up to
$10^{13}d$ for some) pairs of coefficients $m_1, m_2$, where $d=\gcd{(m_1,
m_2)}$ and $m_1/d, m_2/d \leq 40$. The largest counterexamples found that
cannot be obtained in this form are presented. Their relatively small sizes
support the plausibility of GGC. Lemoine's conjecture is verified up to a new
record of $10^{13}$. Four naturally arising verifying algorithms are described
and their running times compared for every $m_1\leq m_2\leq 40$ relatively
prime. These seek to find either the $p$- or the $q$-minimal $(m_1,
m_2)$-partitions of all numbers tested, by either descending or ascending
search for the prime to be maximised or minimised, respectively, in the
partitions. For all $m_1, m_2$ descending searches were faster than ascending
ones. A heuristic explanation is provided. The relative speed of ascending
[descending] searches for the $p$- and for the $q$-minimal partitions,
respectively, varied by $m_1, m_2$. Using the average of $p^*_{m_1, m_2}(n)$ -
the minimal $p$ in all $(m_1, m_2)$-partitions of $n$ - up to a sufficiently
large threshold, two functions of $m_1, m_2$ are introduced, which may help
predict these rankings. Our predictions correspond well with actual rankings.
These could be further improved by developing approximations to $p^*_{m_1,
m_2}(n)$. Numerical data are presented, including average and maximum values of
$p^*_{m_1, m_2}(n)$ up to $10^9$. An extension of GGC is proposed, generalising
the Twin prime conjecture and the assertion that there are infinitely many
Sophie Germain primes.
