<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}


\usepackage{multirow}
\usepackage{multicol}
\usepackage{subcaption}
\usepackage{rotating}
\usepackage{tabularx}
\usepackage[linesnumbered,boxed]{algorithm2e}
\usepackage{longtable}
\usepackage{geometry}
\usepackage{lipsum}
\usepackage[linesnumbered,boxed]{algorithm2e}
\usepackage{xcolor}
\usepackage{bm}
\usepackage{amsthm}
\usepackage{thmtools}
\usepackage{float}
\usepackage{slashbox}
\usepackage{comment}
\usepackage[section]{placeins}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}


\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}



\DeclareMathOperator{\len}{length}
\DeclareMathOperator{\isp}{isprime}
\SetKwProg{Fn}{Function}{}{end}\SetKwFunction{Erato}{SmallPrimes}
\SetKwProg{Fn}{Function}{}{end}\SetKwFunction{Gmqr}{Generatem2qr}
\SetKwProg{Fn}{Function}{}{end}\SetKwFunction{GGC}{GGC}
\SetKwProg{Fn}{Function}{}{end}\SetKwFunction{Checkone}{Check1}
\SetKwProg{Fn}{Function}{}{end}\SetKwFunction{GGCone}{GGC1}
\SetKwProg{Fn}{Function}{}{end}\SetKwFunction{Genismp}{GenerateIsm1p}
\SetKwProg{Fn}{Function}{}{end}\SetKwFunction{Genresp}{GenerateResiduePattern}
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}
\SetAlgoLongEnd

\DeclareMathOperator{\lcm}{lcm_{m_1, m_2}}

\def\modd#1 #2{#1\ \mbox{\rm (mod}\ #2\mbox{\rm )}}

\begin{document}

\begin{center}
\includegraphics[width=4in]{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
	
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
	
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
	
\begin{center}
		\vskip 1cm{\LARGE\bf 	Empirical Verification of a Generalization of \\
		\vskip .1in
Goldbach's Conjecture 
		}
		\vskip 1cm
		\large
		Zs\'ofia Juh\'asz\\
		Dept. of Computer Algebra \\
		Faculty of Informatics\\
		E\"otv\"os Lor\'and University \\
		1117 Budapest \\
		Hungary\\
		\href{mailto:jzsofia@inf.elte.hu}{\tt jzsofia@inf.elte.hu}\\
		\ \\
			M\'at\'e Bartalos\\
		\href{mailto:bartmate@gmail.com}{\tt bartmate@gmail.com}\\
		\ \\
		
		P\'eter Magyar and G\'abor Farkas\\
		Faculty of Informatics \\
		E\"otv\"os Lor\'and University Center Savaria\\
		9700 Szombathely \\
		Hungary\\
		\href{mailto:map115599@gmail.com}{\tt map115599@gmail.com}\\
		\href{mailto:farkasg@inf.elte.hu}{\tt farkasg@inf.elte.hu}	
	\end{center}
	
	\vskip .2 in
	\begin{abstract}
We test Hardy and Littlewood's generalization (GGC) of Goldbach's and
Lemoine's conjectures. According to GGC, for relatively prime positive
integers $m_1$ and $m_2$, every sufficiently large integer $n$ satisfying
certain simple congruence criteria can be expressed as $n=m_1p+m_2q$ for
some primes $p$ and $q$.       We check GGC up to $10^{12}$ for all (up
to $10^{13}$ for some) relatively
prime coefficients $m_1, m_2\leq 40$,
and present the largest counterexamples  that cannot be obtained in this
form.  We verify Lemoine's conjecture up to a new record of $10^{13}$. We
compare the running times of	    four natural verification algorithms
for all relatively prime $m_1\leq m_2\leq 40$. The algorithms seek to
find either the $p$- or the $q$-minimal $(m_1, m_2)$-partitions of all
numbers tested, by either a descending or an ascending search for the
prime to be maximized or minimized, respectively, in the partitions. For
all $m_1, m_2$	descending searches  were faster than ascending ones. We
provide a heuristic explanation.   The relative speed of ascending
[descending] searches for the $p$- and 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, we introduce two functions of $m_1,
m_2$, which may help predict these rankings.  Our predictions correspond
well with actual  rankings, and could	inform new verification efforts.
Numerical data are presented, including average and maximum values of
$p^*_{m_1, m_2}(n)$ up to $10^9$.
\end{abstract}


\section{Introduction}	\label{SectIntro}
One of the best known and longest standing open problems in number theory is due to Goldbach  \cite{Fuss}, who formulated his famous conjecture in 1742, in a letter to Euler. In modern form, the even (or strong) Goldbach  conjecture states that every even number greater than $2$ can be expressed as the sum of two primes. Search for a proof or disproof of this claim has fascinated generations of scholars and  curious minds since. 
 
Progress includes Lu's proof \cite{Wen}  that the number of even integers up to  $x$ which do not have Goldbach partitions is $O(x^{0.879})$.  Chen showed that every sufficiently large even number is the sum of a prime and a semiprime (the product of at most two primes) \cite{Chen}.  In 2013  Helfgott provided a proof for the  odd (weak or ternary) Goldbach conjecture---a weaker statement than the even Goldbach conjecture---asserting that every odd number greater than $5$ is the sum of three primes \cite{Helfgott2013, Helfgott2015}.

With a general proof out of reach, several efforts have targeted the verification of the even Goldbach conjecture (GC) empirically up to increasing limits \cite{Pipping, Richstein, Sinisalo, Granville1989}. Oliveira e Silva et al.\  \cite{Oliveira2014} achieved the current record of $4\cdot 10^{18}$  in a large scale computational project in 2014. A Goldbach partition of an even number $n$ is an expression $n=p+q$ where $p$ and $q$ are prime. The Goldbach partition of $n$ containing the smallest value of $p$ is called the minimal  Goldbach partition of $n$,  and $p(n)$ and $q(n)$ denote the corresponding values of $p$ and $q$, respectively \cite{Granville1989, Oliveira2014}. Oliveira e Silva et al.\  \cite{Oliveira2014} carried out the    verification  by segments of size $10^{12}$,   in each interval searching for the minimal Goldbach partitions of even numbers  using an efficient sieve method. Subsequently, they handled  outstanding values $n$ individually   by `ascending search' for $p(n)$. For each interval to be tested they first  generated primes---potential candidates for $q$---in a somewhat larger interval, using a cache-efficient modified segmented sieve of Eratosthenes. 
   
The rate of growth of $p(n)$ is of some theoretical interest. Granville et al.\  \cite{Granville1989}  conjectured   $p(n)=O(\log ^2 n\log \log n)$. Granville also suggested two more precise, incompatible conjectures of the form $p(n)\leq (C+o(1))\log^2 n\log{\log{n}}$, where $C$ is `sharp' in the sense that $C$ is the smallest constant with this property: one with $C=C_2^{-1}\approx 1.51478$ and the other one with $C=2e^{-\gamma}C_2^{-1}\approx 1.70098$, where $C_2\approx 0.66016$ is the twin prime constant and $\gamma\approx 0.57722$ is the Euler-constant \cite{Oliveira2014}. Empirical comparison of the plausibility of these conjectures was inconclusive due to the requirement of data up to even higher limits \cite{Oliveira2014}.   

In 1894 Lemoine \cite{Lemoine}  proposed a stronger version of the weak Goldbach conjecture,   stating that every odd number $n&gt;5$ can be expressed as $n=p+2q$ for some primes $p$ and $q$ \cite[p.\ 424]{Dickson1919}. The highest threshold of  verification of Lemoine's conjecture (LC) the authors have found claims of is  $10^{10}$ \cite{MaketheBrain}.

In 1923 Hardy and Littlewood \cite{Hardy}  introduced the following generalization (GGC) of the even Goldbach conjecture, also generalizing LC:  
for all relatively prime positive integers $m_1$ and $m_2$, every sufficiently large integer $n$ satisfying certain simple congruence conditions can be expressed as $n=m_1p+m_2q$ for some primes $p$ and $q$. It appears  that this generalization is lesser known, and has not been studied again until  2017  \cite{FarkasJuhasz}. Hence, current paper is the second one concerned with the verification of GGC in its general form.  The authors \cite{FarkasJuhasz} tested GGC  up to $10^{9}$ for each $m_1, m_2 \leq 25$ relatively prime,  and provided the smallest values of $n$ satisfying the conditions of GGC starting from which all integers $\leq 10^9$ also satisfying these  can be $(m_1, m_2)$-partitioned.  
   
We extend the scope and limit of verification of GGC to all coefficients  $m_1, m_2\leq 40$ relatively prime up to  $ 10^{12}$ (up to $10^{13}$ for some $m_1, m_2$),  and  present  the greatest values $n\leq 10^{12}$ satisfying the conditions of GGC which cannot be $(m_1, m_2)$-partitioned. The relatively small sizes of the largest counterexamples support GGC. We confirm LC  up to a new record of $10^{13}$. We applied four different natural verification algorithms in case of every pair $m_1&lt; m_2$. (For $m_1=m_2=1$ we only have two different approaches.)  We compare their speed for each $m_1, m_2$, provide heuristic explanations for their speed rankings, and seek predictions for the fastest one  when testing  up to large thresholds. In this paper we are not aiming to fully optimize the algorithms, but interested in comparing four natural approaches to testing.  For each pair $m_1, m_2$, the fastest one  can be further improved,  and potentially combined with other---perhaps more efficient, e.g., sieving---methods  for testing up to higher limits in the future. 

After preliminaries,  Section \ref{SectDescAlg}  describes the four  algorithms. An $(m_1,m_2)$-partition of $n$ is an expression $n=m_1p+m_2q$ where $p$ and $q$ are prime. We call the $(m_1,m_2)$-partition of $n$ containing the smallest value of $p$ [$q$] the $p$-minimal [$q$-minimal] $(m_1,m_2)$-partition of $n$.  Searching for the minimal Goldbach partition at the verification of GC  \cite{Oliveira2014} has two analogues when checking  GGC  with $m_1\neq m_2$: finding either the $p$- or the $q$-minimal $(m_1, m_2)$-partitions of numbers. In either case one can search in descending order for the prime to be maximized or in ascending order for the prime to be minimized  in the partitions.  These considerations yield four approaches to testing. We also present some findings about the functions $p^*_{m_1, m_2}(n)$---where $p^*_{m_1, m_2}(n)$ is the smallest value of $p$ in all  $(m_1,m_2)$-partitions of $n$--- and about the largest numbers $\hat{k}_{m_1, m_2}$ found satisfying the conditions of GGC that cannot be  $(m_1, m_2)$-partitioned, which are relevant to the designs of the algorithms.

Section \ref{SectImpl} provides information about the implementation of the algorithms and our measures to check the correctness of our computations.

Section \ref{SectTimes} discusses the results regarding the speed ranking of the four algorithms for each pair $m_1\leq m_2\leq 40$ relatively prime---presented in Section \ref{SectTables}--- with some  heuristic explanations by the first author. Since  primes  among larger numbers   are scarcer on average, one may hypothesize that descending search for the prime to be maximized in the partition is faster than ascending search for the prime to be minimized. This is fully supported by our data. According to the results, whether descending [ascending] search for  the $p$- or for the $q$-minimal partitions is faster depends on the pair $m_1, m_2$. We propose two hypotheses to predict these rankings, using two functions of $m_1, m_2$ and of the average of $p^*_{m_1, m_2}(n)$ taken up to a sufficiently large threshold. Predicted and actual rankings show  reasonably good match.  Approximations for the functions $p^*_{m_1, m_2}(n)$ would help estimate  the time complexities of the  algorithms, and ascertain the plausibility of the hypotheses.

Section \ref{SectFuture} outlines our conclusions and some questions for future work.

Section \ref{SectTables}  contains a subset of the data generated, including  the largest value $n\leq 10^{12}$ satisfying the conditions of GGC that cannot be $(m_1, m_2)$-partitioned for all $m_1, m_2\leq 40$, and the maximum and average values of $p^*_{m_1, m_2}(n)$ when $n\leq 10^9$ for all relatively
prime $m_1, m_2\leq 20$. We show the actual speed rankings  of the four algorithms and those predicted by our hypotheses, for all relatively
prime $m_1&lt;m_2\leq 40$.

Section \ref{SectPseudo} includes the pseudocode of the main program implementing one of the algorithms.

\section{Preliminaries} \label{SectPrelim}
For every integer $a$ and $b$, let $\gcd{(a, b)}$ denote the greatest common divisor of $a$ and $b$. Hardy and Littlewood \cite{Hardy} introduced the following conjecture:
\begin{conjecture} 	\label{conRGGC} 
	Let $m_1$ and $m_2$ be positive integers such that $\gcd(m_1, m_2)=1$. Then for every sufficiently large integer $n$ satisfying the conditions
	\begin{enumerate}
		\item $\gcd(n, m_1)=\gcd(n, m_2)=1$ and   \label{conRGGC1}
		\item $n\equiv \modd{m_1+m_2} {2}$,   \label{conRGGC2}
	\end{enumerate}
	there exist primes $p$ and $q$ such that 
	\begin{equation} \label{EqnGGpartition}
	n=m_1p+m_2q.
	\end{equation}
\end{conjecture}
Furthermore, they also conjectured the following estimate for the number of ways $N(n)$ in which an integer $n$ satisfying the conditions of  GGC can be expressed in the form \ref{EqnGGpartition}:
$$ N(n)\sim \frac{2C_2}{m_1m_2}\frac{n}{(\log n)^2}\prod \left(\frac{p-1}{p-2}\right),$$
where $C_2$ is the twin prime constant, and the product is taken over all odd primes $p$ which divide $m_1, m_2$ or $n$.

We let GGC$_{m_1, m_2}$ denote the claim of GGC for given coefficients $m_1, m_2$. Then GGC$_{1, 1}$ and GGC$_{1, 2}$ are Goldbach's and Lemoine's conjectures, respectively. It is easy to see \cite{FarkasJuhasz} that GGC is equivalent to the following:
\begin{conjecture} \label{conGGC}
	Let $m_1$ and $m_2$ be positive integers.  Then for every sufficiently large integer $n$ satisfying the conditions	
	\begin{enumerate}
		\item $\gcd(n, m_1)=\gcd(n, m_2) =\gcd(m_1, m_2)$ and   \label{conGGC1}
		\item $n\equiv \modd{m_1+m_2} {2^{s+1}}$, where $2^s$ is the largest power of $2$ that is a common divisor of $m_1$ and $m_2$,  \label{conGGC2}
	\end{enumerate}
	there exist primes $p$ and $q$ such that 
	\begin{equation*} 
		n=m_1p+m_2q.
	\end{equation*}
\end{conjecture}
In the sequel we consider GGC. The letters $n$, $m_1$, and $m_2$ denote positive integers such that $m_1$ and $m_2$ are relatively prime.

\begin{definition}
An expression of the form \ref{EqnGGpartition} where $p$ and $q$ are primes is called an $(m_1, m_2)$\textit{-Goldbach partition} (or $(m_1, m_2)$\textit{-partition}) \textit{of} $n$.   We say that 
  $n$ \textit{can be} $(m_1, m_2)$\textit{-partitioned} if it possesses at least one $(m_1, m_2)$-partition.
\end{definition}

For every $m_1, m_2$, the number $n=m_1+m_2$  satisfies the conditions of GGC$_{m_1, m_2}$ 
and cannot be $(m_1, m_2)$-partitioned. Hence, if GGC$_{m_1, m_2}$ is true then there exists a largest positive integer satisfying the conditions of GGC$_{m_1, m_2}$  that  cannot be $(m_1, m_2)$-partitioned, which we denote by $k_{m_1, m_2}$. Let $\hat{k}_{m_1, m_2}$ stand for the  largest integer $\leq 10^{12}$ satisfying the conditions of GGC$_{m_1, m_2}$ that cannot be $(m_1, m_2)$-partitioned. We conjecture that $\hat{k}_{m_1, m_2}=k_{m_1, m_2}$ for every pair $m_1, m_2$ tested.


\begin{definition}
If  $n$ can be $(m_1, m_2)$-partitioned then the smallest and the largest values of $p$ [$q$] in all $(m_1, m_2)$-partitions of $n$ are denoted by $p^*_{m_1, m_2}(n)$ [$q^*_{m_1, m_2}(n)$] and $p^{**}_{m_1, m_2}(n)$  [$q^{**}_{m_1, m_2}(n)$], respectively. We call $n=m_1p^*_{m_1, m_2}(n)+m_2q^{**}_{m_1, m_2}(n)$ the $p$\textit{-minimal}  (or $q$\textit{-maximal}) and 
$n=m_1p^{**}_{m_1, m_2}(n)+m_2q^{*}_{m_1, m_2}(n)$ the $p$\textit{-maximal}  (or $q$\textit{-minimal}) $(m_1, m_2)$\textit{-partition of} $n$. 
\end{definition}

Clearly, for all $m_1$, $m_2$  the conditions  of GGC$_{m_1, m_2}$ and GGC$_{m_2, m_1}$ on $n$ are equivalent, and every $(m_1, m_2)$-partition of $n$ is also  an $(m_2, m_1)$-partition if the order of terms is disregarded. Hence, a number $n$  can be $(m_1, m_2)$-partitioned if and only if it can be $(m_2, m_1)$-partitioned, and in this case $p^*_{m_1, m_2}(n)=q^*_{m_2, m_1}(n)$ and $p^{**}_{m_1, m_2}(n)=q^{**}_{m_2, m_1}(n)$. Also, we have $\hat{k}_{m_1, m_2}=\hat{k}_{m_2, m_1}$. Conjectures GGC$_{m_1, m_2}$ and GGC$_{m_2, m_1}$ are equivalent, and if they hold, then $k_{m_1, m_2}=k_{m_2, m_1}$.

\subsection{Notation}
In the sequel  $p_i$ denotes the $i^{\text{th}}$ prime number ($i\in \mathbb{N}^+$), e.g., we have $p_1=2, p_2=3$, etc. For every $n$,  the value $\varphi(n)$ of Euler's totient function at $n$ is the number of positive integers less than or equal to $n$ that are relatively prime to $n$. For given  $m_1$ and $m_2$,  we let $\lcm$ denote the least common multiple of  $m_1, m_2$, and $2$. For every $L&gt; \hat{k}_{m_1, m_2}$ for which there is at least one  $n$ satisfying the conditions of GGC$_{m_1, m_2}$ such that $\hat{k}_{m_1, m_2} &lt;n\leq L$,  we refer to the average and the maximum values of $p^*_{m_1, m_2}(n)$ over all $\hat{k}_{m_1, m_2}&lt; n\leq L$ satisfying the conditions of GGC$_{m_1, m_2}$ more succinctly as the \textit{average} and \textit{maximum}, respectively, \textit{of} $p^*_{m_1, m_2}$ \textit{up to} $L$. For every integer $a$ and $m\neq 0$,   the modulo $m$ residue of $a$ is denoted by $a \bmod m$. 

\section{Verifying algorithms}  \label{SectDescAlg}
In this section we describe the four algorithms  applied for checking GGC$_{m_1, m_2}$ up to 
$N_{m_1, m_2}\approx 10^{12}$ for every pair $m_1\leq m_2\leq 40$ relatively prime. (This means $490$ different pairs $m_1\leq m_2$.) We also present some results about the functions $p^*_{m_1, m_2}(n)$ and the values $\hat{k}_{m_1, m_2}$. 

\subsection{Input, output, and some notes on \texorpdfstring{$p^*_{m_1, m_2}(n)$}{Lg} and \texorpdfstring{$\hat{k}_{m_1, m_2}$}{Lg}}

\subsubsection{Input and  output} All algorithms verify GGC$_{m_1, m_2}$ in a segmented fashion. The input are  $m_1$ and $m_2$ relatively prime, the threshold of verification $N$, the length $\triangle$ of the segments to be checked at a time,  and a further, implementation dependent parameter $\alpha$. These can be set as required---subject to the constraints  on the input provided in the outline of the algorithms---giving flexibility to our codes. We chose $N$  to be the smallest multiple of $2m_1 m_2$ greater than or equal to $10^{12}$---denoted by $N_{m_1, m_2}$---and $\triangle$ to be the smallest multiple of $2m_1m_2$ greater than or equal to $5\cdot 10^7$. (Assuming $N$ and $\triangle$ are divisible by $2m_1 m_2$ slightly simplified our code at parts.)
 
For every $n$ satisfying the conditions of GGC$_{m_1, m_2}$ the algorithms only check  if $n$ has an $(m_1, m_2)$-partition $n=m_1p+m_2q$ such that $m_1p\leq \alpha$ (or $m_2q\leq \alpha$). The output is the array $\mathsf{residual}$ containing those $n\leq N_{m_1, m_2}$ satisfying the conditions of GGC$_{m_1, m_2}$ which do not possess such a partition. After an algorithm has finished, it remains to check by another method if numbers in $\mathsf{residual}$ can be $(m_1, m_2)$-partitioned.

\subsubsection{Functions \texorpdfstring{$p^*_{m_1, m_2}(n)$}{Lg} and the choice of \texorpdfstring{$\alpha$}{Lg}} 
We aimed to set the value of  $\alpha$ so that $\mathsf{residual}$  only contains numbers that cannot be $(m_1, m_2)$-partitioned at all, by ensuring that $m_1p^*_{m_1, m_2}(n)\leq \alpha$ holds for all relatively prime
$m_1, m_2\leq 40$ and $n\leq N_{m_1, m_2}$ satisfying the conditions of GGC$_{m_1, m_2}$ that can be $(m_1, m_2)$-partitioned. We observed that  $p^*_{m_1, m_2}(n)$ remains relatively small even for  large values of $n$. For example, Figure \ref{figAvgp} demonstrates the slow growth of $p^*_{m_1, m_2}(n)$ by showing the  average of $p^*_{m_1, m_2}(n)$ in each interval of length $10^6$ centred at $x=10^6k+5\cdot 10^5$ ($0\leq k\leq 10^3-1$) in the cases $m_1=1, m_2=2$ (Subfigure \ref{figAvgp1}), $m_1=4 , m_2=17$ (Subfigure  \ref{figAvgp2}), and $m_1=7, m_2=3$ (Subfigure  \ref{figAvgp3}). Table \ref{TableAverMaxp} contains the maximum and average values of $p^*_{m_1, m_2}(n)$  up to $n\leq 10^9$ for each $m_1, m_2\leq 20$ relatively prime. For $n\leq 10^9$, over all $m_1, m_2\leq 40$ relatively prime the maximum of $p^*_{m_1, m_2}(n)$ is $78697$ (at $m_1=32$, $m_2=37$), and the maximum of $m_1p^*_{m_1, m_2}(n)$ is $2858879$ (at $m_1=37$, $m_2=38$). Experimentally we also found that $m_1p^*_{m_1, m_2}(n)\leq 5\cdot 10^7$ for all $n\leq N_{m_1, m_2}$ satisfying the conditions of GGC$_{m_1, m_2}$ that can be $(m_1, m_2)$-partitioned, for all $m_1, m_2\leq 40$ relatively prime. Hence, in our implementation $\alpha =5\cdot 10^7$, and so   for all $m_1, m_2$, the largest number in $\mathsf{residual}$ equals $\hat{k}_{m_1, m_2}$. Choosing smaller suitable $\alpha$ could have been possible, but the resulting improvements  in running times  would have been insignificant. 

\begin{figure}[H]
	\centering
	\begin{subfigure}{0.3\textwidth}
		\includegraphics[width=\textwidth]{Avgp_1_2new.png}
		\caption{$m_1=1, m_2=2$}
		\label{figAvgp1}
	\end{subfigure}
	\hfill
	\begin{subfigure}{0.3\textwidth}
		\includegraphics[width=\textwidth]{Avgp_4_17.png}
		\caption{$m_1=4, m_2=17$}
		\label{figAvgp2}
	\end{subfigure}
	\hfill
	\begin{subfigure}{0.3\textwidth}
		\includegraphics[width=\textwidth]{Avgp_7_3.png}
		\caption{$m_1=7, m_2=3$}
		\label{figAvgp3}
	\end{subfigure}	
	\caption{The average value of $p^*_{{m_1, m_2}}(n)$ in the interval of length $10^6$ centred at $x=10^{6} k+5\cdot 10^5$ for $0\leq k\leq 10^3-1$, in cases of  $m_1, m_2$ indicated under each subfigure.}
	\label{figAvgp}
\end{figure}

\subsubsection{Values of \texorpdfstring{$\hat{k}_{m_1, m_2}$}{Lg}}
Table \ref{TableCountEx} shows  $\hat{k}_{m_1, m_2}$ for all
relatively prime $m_1, m_2\leq 40$. The maximum (at $m_1=32$, $m_2=37$) and  average of $\hat{k}_{m_1, m_2}$ are $412987$  and  $52004.84$, respectively. The relatively small sizes of $\hat{k}_{m_1, m_2}$ support GGC, and also meant that the extra time required for checking numbers in $\mathsf{residual}$ was negligible.
 
\subsection{The algorithms}

\subsubsection{Different approaches to testing} The main difference between Algorithms 1a, 1b, 2a, and 2b lies in their methods for checking if a number can be $(m_1, m_2)$-partitioned.  These---for given ordered pair $(m_1, m_2)$---are summarized below: 

\textit{Algorithm 1a [1b]:} `Descending search for the prime to be maximized' in the partitions. Algorithm 1a  [1b] searches for the $p$-minimal [$q$-minimal] ($m_1, m_2$)-partition  $n=m_1p^*_{m_1, m_2}(n)+m_2q^{**}_{m_1, m_2}(n)$  [$n=m_1p^{**}_{m_1, m_2}(n)+m_2q^{*}_{m_1, m_2}(n)$] by trying all possible candidates $q$ [$p$] for $q^{**}_{m_1, m_2}(n)$   [for $p^{**}_{m_1, m_2}(n)$] in decreasing  order until it finds that $n-m_2q=m_1p$ [$n-m_1p=m_2q$] for some prime $p$ [$q$].

\textit{Algorithm 2a [2b]:} `Ascending search for the prime to be minimized' in the partitions. 
Algorithm 2a [2b] searches for the $p$-minimal [$q$-minimal] ($m_1, m_2$)-partition  $n=m_1p^*_{m_1, m_2}(n)+m_2q^{**}_{m_1, m_2}(n)$  [$n=m_1p^{**}_{m_1, m_2}(n)+m_2q^{*}_{m_1, m_2}(n)$] by trying all possible candidates $p$ [$q$] for $p^*_{m_1, m_2}(n)$   [for $q^{*}_{m_1, m_2}(n)$] in increasing order until it finds that $n-m_1p=m_2q$ [$n-m_2q=m_1p$] for some prime $q$ [$p$].

Algorithms 1a and 1b  [2a and 2b] can be implemented by the same program by interchanging the values of $m_1$ and $m_2$. Hence, only Algorithms 1a and 2a are described in this section, referred to as Algorithms 1 and 2, respectively.

\subsubsection{Simplified outlines of Algorithms 1 and 2} \label{SubsectOutline} 


\textit{Input:}  
$m_1, m_2, N$, 
$\triangle, \alpha\in \mathbb{N}^+$ such that $\gcd (m_1, m_2)=1$, $N &gt;9$, $2m_1m_2|N$, $2m_1m_2|\triangle$, and $\alpha\leq \triangle$. 

\noindent \textit{Output:} array $\mathsf{residual}$ containing all numbers $n \leq N$ satisfying the conditions of GGC$_{m_1, m_2}$ for which there are  no primes $p$ and $q$ such that $n=m_1p+m_2q$ and $m_1p\leq \alpha$.

\begin{enumerate}	
	\item \label{AlgI} {Phase I: Unsegmented phase
		
		\begin{enumerate}
			\item \label{AlgI11} Generate `small' primes up to  
			$K= \max{(\lfloor\sqrt{\smash[b]{N/m_2}}\rfloor, \lfloor\alpha/m_1 \rfloor )}$. 			
			
			(proc.\ {\tt{SmallPrimes($K$)}})
			
			\item \label{AlgI12} Generate all numbers 	$m_1p\leq \alpha$ where $p$ is prime. 
			In  Algorithm 2 these are sorted and stored separately according to their residues modulo $m_2$. 			
			
			(proc.\ {\tt{GenerateIsm1p}}($\alpha$) [{\tt{Generatem1pr}}($\alpha$)] in Algorithm 1 [2])		
			
			\item \label{AlgI13} Generate the 
modulo $\lcm$ `residue wheel', i.e., the array of all $\lcm$ residues relatively prime to $m_1m_2$ and congruent to   $m_1+m_2$ modulo $2$. 	(proc.\ {\tt{GenerateResiduePattern}}($m_1, m_2$))		
	\end{enumerate}}	
	
	\item \label{AlgII} {Phase II: Check GGC$_{m_1, m_2}$ segment by segment. For each interval $[A,B)$:		
		
		\begin{enumerate}
			
			\item \label{AlgII1} {Generate $m_2$-times multiples of `large' primes in an interval.				
			
			(proc.\ {\tt{Generatem2qr}}$(C, D)$ [{\tt{Generateism2q}}$(C, D)$] in Algorithm 1 [2])				
				
				\begin{enumerate}
					\item \label{AlgII11} Generate all primes in interval $[C/m_2, D/m_2)$. (The values $C$ and $D$ depend on $A$ and $B$.) 
					\item \label{AlgII12} Generate all numbers of the form $m_2q$ in interval $[C, D)$, where $q$ is prime. Algorithm 1 sorts and stores these numbers separately according to their residues 
					modulo $m_1$.					
				\end{enumerate}			
			}
			\item \label{AlgII2} Check GGC$_{m_1, m_2}$ in interval $[A,B)$. 			
			
			(proc.\ {\tt{Check1}}$(A, B)$ [{\tt{Check2}}$(A, B)$] in Algorithm 1 [2])
		\end{enumerate}
	}	
\end{enumerate}

\subsubsection{Some ideas applied in both algorithms}  
In order to check if every number in an interval $[A, B)$ satisfying the conditions of GGC$_{m_1, m_2}$ has a partition $m_1p+m_2q$ such that $m_1p\leq \alpha$, it is sufficient to possess the lists of all numbers $m_1p\leq \alpha$ where $p$ is prime,  and of all numbers $m_2q$ in interval  $[\max{(0, A-\alpha)},B)$ where $q$ is prime. These lists are generated in Phases I and II, respectively. Although  methods with lower asymptotic time complexities  exist \cite{BaysHudson, Barstow, Misra, Bengelloun, Prichard}, in Phases I and II the sieve of Eratosthenes and a segmented version of this, respectively, is used  to generate primes. 

If $n=m_1p+m_2q$ is an $(m_1, m_2)$-partition then
\begin{align}
	m_2q&amp;\equiv  n\pmod{m_1} \textrm{ and}  \label{Eqn1}\\
	m_1p&amp;\equiv n \pmod{m_2}. \label{Eqn2}
\end{align}
Therefore, for  each $n$, Algorithm 1 [2] in Phase II tries  as  candidates for  $q^{**}_{m_1, m_2}(n)$ [$p^*_{m_1, m_2}(n)$] only primes $q$ [$p$] satisfying congruence \eqref{Eqn1} [\eqref{Eqn2}], which reduces the number of candidates tested by  approximately  a factor of $1/\varphi(m_1)$ [$1/\varphi(m_2)$]. In order to facilitate this, when generating numbers of the form $m_2q$ [$m_1p$]  in an interval  [up to $\alpha$]  Algorithm 1 [2] also sorts them by their 
residues modulo $m_1$ [$m_2$]. 

\subsubsection{Detailed description of the steps in Algorithm 1} \label{SubsectDescrSteps} 

Phase I: Procedure {\tt{SmallPrimes($K$)}} generates a list of all `small' primes up to  $ K= \max{(\lfloor \sqrt{\smash[b]{N_{m_1, m_2}/m_2}} \rfloor, \lfloor\alpha/m_1\rfloor )}$,  using the sieve of Eratosthenes. Procedure {\tt{GenerateIsm1p}}($\alpha$)
outputs the  boolean array $\mathsf{ism_1p}$ of length $\alpha +1$ such that 
for all $0\leq i\leq \alpha$: $\mathsf{ism_1p}[i]=1$ if and only if $i=m_1p$ for some prime $p$. When checking GGC$_{m_1, m_2}$ only those numbers $n$ need to be tested which satisfy the conditions of GGC$_{m_1, m_2}$, which holds if and only if the residue $n \bmod \lcm$ satisfies these. 
Procedure {\tt{GenerateResiduePattern}}($m_1, m_2$) generates boolean array $\mathsf{res}$ of length $\lcm$ such that for all $0\leq i\leq \lcm-1$: $\mathsf{res}[i]=1$ if and only if $\gcd(i, m_1)=\gcd(i, m_2)=1$ and $i\equiv m_1+m_2$ (mod $2$). 

Phase II: For given integers $0\leq C&lt;D$ such that $2m_1m_2|C$ and $2m_1m_2|D$, procedure {\tt{Generatem2qr}}$(C, D)$ generates all numbers of the form $m_2q$ in interval $[C, D)$ where $q$ is prime,  and  stores each $m_2q$ in array $\mathsf{m_2q[r]}$ where $r= m_2q \bmod m_1$  ($0\leq r &lt; m_1$). For given integers  $0\leq A&lt;B$  where $2m_1m_2| A$  and  $2m_1m_2  | B$, procedure {\tt{Check1}}$(A, B)$  checks for every $n$ in $[A,B)$ satisfying the conditions  of GGC$_{m_1, m_2}$  if there exist primes $p$ and $q$ such that $n=m_1p+m_2q$ and $m_1p\leq \alpha$. The procedure  looks for the $p$-minimal $(m_1, m_2)$-partition of $n$,  applying  a `descending' search for $q^{**}_{m_1, m_2}(n)$: trying in decreasing  order the values $m_2q$  where $q$ is prime  such that $m_2q\equiv n$ (mod $m_1$) ---taking these from array $\mathsf{m_2q[r]}$  where $r= n\bmod{m_1}$---and checking if $n-m_2q$ is of the form $m_1p$  for some prime $p$. If such $m_2q$ is found then $q^{**}(n)=q$   and $p^*(n)=(n-m_2q)/m_1$. Otherwise $n$ is added to array $\mathsf{residual}$.  The output is array $\mathsf{residual}$ of those $n$ in $[A,B)$ satisfying the conditions  of GGC$_{m_1, m_2}$  for which there exist no primes $p$ and $q$ such that $n=m_1p+m_2q$ and $m_1p\leq \alpha$.
 
Section \ref{SectPseudo} contains the pseudocode of procedure {\tt{GGC1}}($N,m_1,m_2, \triangle$, $\alpha$)  implementing Algorithm 1.

\section{Implementation and checking for correctness} \label{SectImpl}
We implemented Algorithms 1 and 2 in {\tt C++}. For each $m_1\leq m_2\leq 40$ relatively prime, we checked GGC$_{m_1, m_2}$ up to $N_{m_1, m_2}$ by  Algorithms 1a, 1b, 2a, and 2b. (For $m_1=m_2=1$, Algorithms 1a and 1b [2a and 2b] are identical.)  The program for Algorithm 1 [2] performed both Algorithms 1a and 1b [2a and 2b], with the values of  $m_1$ and $m_2$ interchanged (with $m_1&lt; m_2$ in Algorithms 1a and 2a). Each algorithm ran on one core of a 32-core 64-bit Intel Xeon Scalable processor. 

For each pair  $m_1\leq m_2$ the output arrays $\mathsf{residual}$ of the four algorithms (only two different algorithms in case $m_1=m_2=1$) were identical. We generated the values $p^*_{m_1, m_2}(n)$ [$q^{*}_{m_1, m_2}(n)$]  and $q^{**}_{m_1, m_2}(n)$ [$p^{**}_{m_1, m_2}(n)$] for all $\hat{k}_{m_1, m_2}&lt;n\leq  10^6$ satisfying the conditions of GGC$_{m_1, m_2}$, which were also identical. 

\section{Comparing the running times of the algorithms} \label{SectTimes}

\subsection{Experimental data on running times}
For each pair $m_1\leq m_2\leq 40$ relatively prime, Algorithms 1a and 1b were both   faster than Algorithms 2a and 2b,  the former two  significantly outperforming on average the latter. The speed rankings of Algorithms 1a and 1b  [2a and 2b] varied depending on the pair $m_1&lt; m_2$. On average over all pairs $m_1\leq m_2$, Algorithms 1a and 1b [2a and 2b] showed very similar speed performances.  Table \ref{TableFastestSlowest} presents the average, lowest, and highest running times of each  algorithm, and the pair $m_1, m_2$ where the latter occurred.

\begin{table}[H]
	\centering
	\footnotesize{
		\begin{tabular}{|c|c|c|c|c|c|c|c|}
		\hline
		\multicolumn{1}{|c|}{Algorithm} &amp;  \multicolumn{3}{c|}{Lowest} 
		&amp;     \multicolumn{3}{c|}{Highest } 
		&amp; \multicolumn{1}{c|}{Average time (sec)}		
		\\	
		&amp; \multicolumn{1}{c|}{$m_1$} &amp; \multicolumn{1}{c|}{$m_2$} &amp; \multicolumn{1}{c|}{time (sec)} &amp;         \multicolumn{1}{c|}{$m_1$} &amp; \multicolumn{1}{c|}{$m_2$} &amp; \multicolumn{1}{c|}{ time (sec)} &amp;   \\
		\hline
		Alg. 1a &amp; 7     &amp; 30    &amp; 22473 &amp;        16    &amp; 29    &amp; 114177 &amp;  56045 \\
		Alg. 1b &amp; 6     &amp; 35    &amp; 23345 &amp;       1     &amp; 16    &amp; 108614 &amp;  54461 \\
		Alg. 2a &amp; 33    &amp; 35    &amp; 55742 &amp;       31    &amp; 32    &amp; 293279 &amp;  132154 \\
		Alg. 2b &amp; 35    &amp; 39    &amp; 57391 &amp;        32    &amp; 37    &amp; 293734 &amp;   134559\\
		\hline
	\end{tabular}}
	\caption{Lowest, highest, and average running times (sec) of the algorithms up to $N_{m_1, m_2}\approx 10^{12}$ over all pairs $m_1\leq m_2\leq 40$ relatively prime.} \label{TableFastestSlowest}
\end{table}

For each pair $m_1&lt; m_2$ tested the running times of the four algorithms ranked in one of the following four  orders from fastest to slowest:
\begin{itemize}
\item	Group A:  Algorithms 1a, 1b, 2a, 2b	

\item	Group B: Algorithms 1a, 1b, 2b, 2a	

\item	Group C: Algorithms 1b, 1a, 2a, 2b	

\item	Group D: Algorithms 1b,  1a, 2b,  2a
\end{itemize}
Groups A, B, C, and D contain $21$, $218$, $242$, and $8$ pairs, respectively, as shown by Table \ref{TableSpeeds} in Section \ref{SectTables}. The dominance of groups B and C raises the question whether the pairs in groups A and D would also move to one of these groups when testing up to sufficiently large thresholds. In all $8$ pairs in group D the running times of Algorithms 1a and 1b or those of 2a and 2b were `very close'. We ran all four algorithms for the pairs $(9, 32), (11, 29), (17, 19)$, and $(23, 29)$ in group D---and for six other pairs including $(1, 2)$---up to $\approx 10^{13}$. The running times are shown in Table \ref{TableUpto1013}. The speed rankings changed for all four pairs in group D.  The pairs $(9, 32)$, $(11, 29)$, $(17, 19)$, and $(23, 29)$ moved to groups B,  C, A, and A, respectively. In the latter two cases the running times of Algorithms 1a and 1b were `very close' to each other, which makes it plausible that the pairs might move again to another group if testing until even higher thresholds. These results suggest that the remaining other four pairs in group D may also leave this group in case of larger thresholds.

\begin{table}[H]
	\centering
	\scriptsize{
	\begin{tabular}{|c|c|c|c|c|c||c|c|c|c|}
		\hline
		$m_1$ &amp; $m_2$ &amp; \multicolumn{4}{c||}{Running times (sec) up to 
			$\approx 10^{12}$} &amp; \multicolumn{4}{c|}{Running times (sec) up to 
			 $\approx 10^{13}$} \\
		{\multirow{2}{*}{}} &amp; {\multirow{2}{*}{}} &amp; Alg. 1a &amp; Alg. 1b &amp; Alg. 2a &amp; Alg. 2b  &amp; Alg. 1a &amp; Alg. 1b &amp; Alg. 2a  &amp; Alg. 2b\\
		\hline		
		
		1     &amp; 2     &amp; 77192 &amp; 104914 &amp; 290478 &amp; 182075 &amp; 754817 &amp; 1052855 &amp; 2290673 &amp; 1873002 \\
				
		1     &amp; 3     &amp; 42991 &amp; 67452 &amp; 106733 &amp; 110383 &amp; 423373 &amp; 671771 &amp; 1125928 &amp; 1154959 \\
		
		1     &amp; 5     &amp; 56912 &amp; 77743 &amp; 129483 &amp; 142355 &amp; 555759 &amp; 786325 &amp; 1350077 &amp; 1515172 \\
		
		1     &amp; 7     &amp; 63372 &amp; 82353 &amp; 137414 &amp; 158389 &amp; 627182 &amp; 823687 &amp; 1479262 &amp; 1704191 \\
		
		1     &amp; 9     &amp; 44371 &amp; 69002 &amp; 101032 &amp; 111152 &amp; 431663 &amp; 687392 &amp; 1065525 &amp; 1172360 \\
		
		1     &amp; 11    &amp; 69622 &amp; 86173 &amp; 143534 &amp; 169134 &amp; 745476 &amp; 860608 &amp; 1470691 &amp; 1753254 \\
		
		9     &amp; 32    &amp; 43546 &amp; 43514 &amp; 132022 &amp; 111549 &amp; 549958 &amp; 582308 &amp; 1331716 &amp; 1146279 \\
		
		11    &amp; 29    &amp; 74485 &amp; 52092 &amp; 148247 &amp; 145263 &amp; 744006 &amp; 706943 &amp; 1404459 &amp; 1563704 \\
		
		17    &amp; 19    &amp; 55562 &amp; 55052 &amp; 143130 &amp; 143104 &amp; 736166 &amp; 738674 &amp; 1458811 &amp; 1545744 \\
		
		23    &amp; 29    &amp; 80070 &amp; 59988 &amp; 155817 &amp; 155277 &amp; 800289 &amp; 807146 &amp; 1567925 &amp; 1676299 \\
		\hline
	\end{tabular} }
	\caption{Running times (sec) of the algorithms up to  $\approx 10^{12}$ and $\approx10^{13}$ for some $m_1, m_2$.} \label{TableUpto1013}
\end{table}

\subsection{Estimations for the running times}
The significant parts of the computation in Algorithm 1 [2] are {\tt{Generatem2qr}} and {\tt{Check1}} [{\tt{Generateism2q}} and {\tt{Check2}}]. During 
all iterations procedure {\tt{Generatem2qr}} 
[{\tt{Generateism2q}}] generates all primes up to $N/m_2$, 
and their $m_2$-times multiples, using $O(N\log{\log{N}})$  \cite{Sorenson} and $\pi(N/m_2) \sim N/(m_2(\ln{N}-\ln{m_2}))=o(N\log{\log{N}})$ operations, respectively. Hence, {\tt{Generatem2qr}} [{\tt{Generateism2q}}]  takes $O(N\log{\log{N}})$ time. 

In absence of approximations for the functions $p^*_{m_1, m_2}(n)$  it is difficult to estimate the number of operations performed by {\tt{Check1}}  [{\tt{Check2}}]. However, we can establish the following. For given $m_1, m_2$ relatively prime, the number of values $n\leq N_{m_1, m_2}$ tested---i.e., of those satisfying the conditions of GGC$_{m_1, m_2}$---is approximately $\varphi(m_1m_2)N_{m_1, m_2}/\lcm\approx 10^{12}\varphi(m_1m_2)/\lcm$.

In Algorithm 1, for each $n$ tested, the number of candidates  {\tt{Check1}} tries for $q^*_{m_1, m_2}(n)$ is approximately the number of primes $q$ in the interval between $n/m_2 - m_1p^*_{m_1, m_2}(n)/m_2$ and $n/m_2$  of length $m_1p^*_{m_1, m_2}(n)/m_2$ satisfying $m_2q\equiv n$ (mod $m_1$).  
Using  $\pi(x)-\pi(x-y)\approx y/\ln(x)$ \cite{Heath1988}, this can be estimated as follows:
\begin{equation} \label{EqnEst1}
	\begin{aligned}
		&amp; \frac{m_1p^*_{m_1, m_2}(n)}{\varphi(m_1)m_2\ln (n/m_2)} \approx  
		&amp; \frac{m_1p^*_{m_1, m_2}(n)}{\varphi(m_1)m_2\ln (n)}. 
	\end{aligned}
\end{equation}
In Algorithm 2 for each value $n$ tested, the number of candidates {\tt{Check2}} checks for $p^*_{m_1, m_2}(n)$ is equal to the number of primes $p$ up to $p^*_{m_1, m_2}(n)$ satisfying $m_1p \equiv n$ (mod $m_2$), which is approximately the following:
\begin{equation} \label{EqnEst2}
\frac{\pi(p^*_{m_1, m_2}(n))}{\varphi(m_2)}\sim \frac{p^*_{m_1, m_2}(n)}{\varphi(m_2)\ln{p^*_{m_1, m_2}(n)}}.
\end{equation}

\subsection{Some heuristics}
Currently possessing no approximations for $p^*_{m_1, m_2}(n)$, and thus for the number of operations performed by {\tt{Check1}} and {\tt{Check2}}, it is unclear how the time complexities of {\tt{Generatem2qr}} and {\tt{Check1}} [{\tt{Generateism2q}} and {\tt{Check2}}] compare. In order to obtain empirical data, we ran Algorithm 1a for four pairs $m_1\leq m_2$ up to the thresholds of approximately $10^6, 10^7, 10^8$, and $10^9$, and measured the times taken by {\tt{Check1}} and  {\tt{Generatem2qr}}. In one case {\tt{Check1}} took  around $66\%$, and in all other cases above $80\%$ (usually above $90\%$), whereas {\tt{Generatem2qr}} took in one case $16\%$, but in all other cases below $10\%$, and usually below $5\%$ of the total time. As the threshold increased,  Algorithm 1a spent an increasing and a decreasing fraction of the total time on {\tt{Check1}} and on {\tt{Generatem2qr}}, respectively. 

In the arguments below we assume that in Algorithm 1 [2] {\tt{Check1}} [{\tt{Check2}}] is the most time consuming part of the computation, with higher time complexity than {\tt{Generatem2qr}}  [{\tt{Generateism2q}}]; hence, the relative speed performances of Algorithms 1a, 1b, 2a, and 2b are determined by {\tt{Check1}} and {\tt{Check2}}.

\subsubsection{Comparing the running times of Algorithms 1a and 2a [1b and 2b]}
Granville et al.\  \cite{Granville1989}  conjectured  that $p(n)=p_{1, 1}^*(n)=O(\log ^2 n\log \log n)$, implying $p_{1, 1}^*(n)=o(n^{\varepsilon})$ for 
every $\varepsilon\in \mathbb{R}^+$. Based on our data we also conjecture that 
for all $m_1$ and $m_2$ and $\varepsilon\in \mathbb{R}^+$ we have $p^*_{m_1, m_2}(n)=o(n^{\epsilon})$. This assumption yields $\ln{p^*_{m_1, m_2}(n)}=o(\ln(n))$. Hence 
$$ \frac{m_1p^*_{m_1, m_2}(n)}{\varphi(m_1)\ln (n)} = o\left(\frac{p^*_{m_1, m_2}(n)}{\varphi(m_2)\ln{p^*_{m_1, m_2}(n)}}\right), $$
which heuristically suggests that Algorithm 1a [1b] is faster than Algorithm 2a [2b] for all $m_1, m_2$, when run until sufficiently large threshold. This prediction is in complete accordance with our results: for each pair $m_1, m_2$ tested  Algorithms 1a and 1b were both faster than Algorithms 2a and 2b.

\subsubsection{Comparing the running times of Algorithms 1a and 1b  [2a and 2b]}
Since for given $m_1, m_2$, in Algorithms 1a and 1b [2a and 2b]  {\tt{Check1}} [{\tt{Check2}}] checks the same number of values $n$,  one may attempt to explain their relative speed performances using some  estimate of the `average' time spent by {\tt{Check1}} [{\tt{Check2}}] on processing each value $n$. Based on estimates \ref{EqnEst1} and \ref{EqnEst2},    we introduce the following functions 
for every sufficiently large number $L$:
$$ f_{{}_L}(m_1, m_2):=\frac{m_1\overline{p^*}_{{}_{L}}(m_1, m_2)}{\varphi(m_1)m_2} \textrm{\hspace{2pt} and \hspace{2pt}} g_{{}_L}(m_1, m_2):= \frac{\overline{p^*}_{{}_{L}}(m_1, m_2)}{\varphi(m_2)\ln{\overline{p^*}_{{}_{L}}(m_1, m_2)}},$$ 
where $\overline{p^*}_{{}_{L}}(m_1, m_2)$ is the average of $p^*_{m_1, m_2}(n)$ up to $L$. Then for all $m_1, m_2$ and all  $L$ and $N$ sufficiently large, the following hypotheses can be considered when testing GGC$_{m_1, m_2}$ up to $N$:

H$_1(L, N):$	Algorithm 1a is faster than Algorithm 1b if and only if 
\begin{equation} \label{Eqnx}
	f_{{}_L}(m_1, m_2)&lt;f_{{}_L}(m_2, m_1) \textrm{\; \;}  \left( \Leftrightarrow \textrm{\; \;}  
	\frac{\overline{p^*}_{{}_{L}}(m_1, m_2)}{\overline{p^*}_{{}_{L}}(m_2, m_1)}&lt; \frac{m_2^2\varphi(m_1)}{m_1^2\varphi(m_2)}\right)
\end{equation}	

H$_2(L, N):$ Algorithm 2a is faster than Algorithm 2b if and only if 
\begin{equation} \label{Eqny}
	g_{{}_L}(m_1, m_2)&lt;g_{{}_L}(m_2, m_1) \textrm{\; \;}   \left( \Leftrightarrow \textrm{\; \;}    \frac{\overline{p^*}_{{}_{L}}(m_1, m_2)\ln{\overline{p^*}_{{}_{L}}(m_2, m_1)}}{\overline{p^*}_{{}_{L}}(m_2, m_1)\ln{\overline{p^*}_{{}_{L}}(m_1, m_2)}} &lt; \frac{\varphi(m_2)}{\varphi(m_1)}
	\right). 
\end{equation} 
Then H$_1$ is the hypothesis that H$_1(L, N)$ is true for all $N\geq L$ where $L$ is sufficiently large. Hypothesis H$_2$ is the claim that H$_2(L, N)$ is true for all $N\geq L$ where $L$ is sufficiently large.

We tested H$_1(10^9, N_{m_1, m_2})$ and H$_2(10^9, N_{m_1, m_2})$ for all $489$ pairs $m_1&lt; m_2$ relatively prime. The pairs can be categorized as follows:
\begin{itemize}
\item	Group a:  $f_{{}_{10^9}}(m_1, m_2)&lt;f_{{}_{10^9}}(m_2, m_1)$ and $g_{{}_{10^9}}(m_1, m_2)&lt;g_{{}_{10^9}}(m_2, m_1)$.	

\item	Group b: $f_{{}_{10^9}}(m_1, m_2)&lt;f_{{}_{10^9}}(m_2, m_1)$ and $g_{{}_{10^9}}(m_1, m_2)&gt;g_{{}_{10^9}}(m_2, m_1)$.	

\item	Group c: $f_{{}_{10^9}}(m_1, m_2)&gt;f_{{}_{10^9}}(m_2, m_1)$ and $g_{{}_{10^9}}(m_1, m_2)&lt;g_{{}_{10^9}}(m_2, m_1)$.

\item	Group d: $f_{{}_{10^9}}(m_1, m_2)&gt;f_{{}_{10^9}}(m_2, m_1)$ and $g_{{}_{10^9}}(m_1, m_2)&gt;g_{{}_{10^9}}(m_2, m_1)$.
	\end{itemize} 	
Group a is empty, while groups b, c, and d contain $227$, $258$, and $4$ pairs, respectively. For all four  pairs in group d at least one of the differences $|f_{10^9}(m_1, m_2)-f_{10^9}(m_2, m_1)|$ and $|g_{{}_{10^9}}(m_1, m_2)-g_{{}_{10^9}}(m_2, m_1)|$ is `small' (less than $0.4$). Hence, it is plausible that their group allocation may change if $L$ is sufficiently large.  

Table   \ref{TableSpeeds}   shows the classification of the pairs into groups A, B, C, and D and a, b, c, and d, respectively.  In our experiment H$_1(10^9, N_{m_1, m_2})$  is true for $467$ pairs (groups Ab, Bb, Cc, and Dc), and  H$_2(10^9, N_{m_1, m_2})$ holds for $476$ pairs (groups Ac, Bb, Cc, Bd, and Db). Both claims hold for $458$  pairs (groups Bb and Cc) among all $489$ pairs. Among those $22$ pairs for which H$_1(10^9, N_{m_1, m_2})$ fails (groups Ac, Ad, Bc, Bd, and Db) in case of $15$ pairs either the running times of Algorithms 1a and 1b were `close' (i.e., differed by less than $10^4$ sec) or $|f_{{}_{10^9}}(m_1, m_2)-f_{{}_{10^9}}(m_2, m_1)|$ was `small' (i.e., less than $1$). For all those $13$ pairs for which H$_2(10^9, N_{m_1, m_2})$ fails (groups Ab, Ad, Bc, and Dc) either the running times of Algorithms 2a and 2b were `close' (differed by less than $10^4$ sec) or $|g_{{}_{10^9}}(m_1, m_2)-g_{{}_{10^9}}(m_2, m_1)|$ was `small' (less than $1$). Hence, it is plausible that for sufficiently large $N$ and $L$ the hypotheses may also hold for most (or for all) of these pairs.

Further computational experiments, understanding the behaviours of, and developing estimations for the functions $p^*_{m_1, m_2}(n)$ could help ascertain the plausibility of the two hypotheses. 

\subsection{Further observations regarding \texorpdfstring{$p^*_{m_1, m_2}(n)$}{Lg}}

\begin{figure}[H]
	\centering
	\begin{subfigure}{0.45\textwidth}
		\includegraphics[width=\textwidth]{Avgp_per_Avgq_1_2.png}
		\caption{$m_1=1, m_2=2$}
		\label{figfirst}
	\end{subfigure}
	\hfill
	\begin{subfigure}{0.45\textwidth}
		\includegraphics[width=\textwidth]{Avgp_per_Avgq_2_5.png}
		\caption{$m_1=2, m_2=5$}
		\label{figsecond}
	\end{subfigure}
	\hfill
	\begin{subfigure}{0.45\textwidth}
		\includegraphics[width=\textwidth]{Avgp_per_Avgq_23_40.png}
		\caption{$m_1=23, m_2=40$}
		\label{figthird}
	\end{subfigure}
\hfill
\begin{subfigure}{0.45\textwidth}
	\includegraphics[width=\textwidth]{Avgp_per_Avgq_1_33.png}
	\caption{$m_1=1, m_2=33$}
	\label{figfourth}
\end{subfigure}
	
	\caption{The quotient $\frac{\textrm{average } p^*_{m_1, m_2}(n)}{\textrm{average } q^*_{m_1, m_2}(n)}$ in each interval of length $10^6$ centred at $x$, for $x=10^6k+5\cdot 10^5$ ($k=0, 1, \ldots , 10^3-1$), in cases of some  $m_1, m_2$ indicated under each subfigure.}
	\label{figfigures}
\end{figure}

In Figure \ref{figAvgp}, one can note the slow growths of the average $p^*_{m_1, m_2}(n)$ in intervals of length $10^6$ up to $10^9$. The graphs are close to smooth curves and similar in shape. 

Figure \ref{figfigures} displays the  functions $x\mapsto \textrm{average of } p^*_{m_1, m_2}(n)/\textrm{average of } q^*_{m_1, m_2}(n)$ in intervals of length $10^6$ centred at $x=10^6k+5\cdot 10^5$ ($0\leq k\leq 10^3-1$) for $m_1=1 , m_2= 2$ (Subfigure \ref{figfirst}), $m_1=2 , m_2=5 $ (Subfigure \ref{figsecond}), $m_1=23 , m_2= 40$ (Subfigure \ref{figthird}), and $m_1=1 , m_2=33 $ (Subfigure \ref{figfourth}). The graphs---especially the first three---appear to be remarkably close to straight lines: the trend lines with equations $y=-2\cdot 10^{-11}x+2.4745$, $y=3\cdot 10^{-11}x+2.8297$, $y=5\cdot 10^{-12}x+1.851$, and $y=3\cdot 10^{-9}x+50.374$, respectively, indicated in each subfigure. The values of the functions fall within the following narrow intervals between their minima and maxima  (correct to $3$ decimal places): $[2.408 , 2.519]$, $[2.711 , 2.945]$, $[1.663 , 2.01 ]$, and $ [42.200 , 55.582]$ (Subfigures \ref{figfirst}, \ref{figsecond}, \ref{figthird}, and \ref{figfourth}, respectively). If the smoothly increasing or decreasing trends of these functions continue, it suggests that the functions $L\mapsto \overline{p^*}_{{}_L}(m_1, m_2)/\overline{p^*}_{{}_L}(m_2, m_1)$ may also be  increasing or decreasing, accordingly.  In this case inequality \ref{Eqnx} is either simultaneously true or false for all $L$ sufficiently large.

\FloatBarrier

\section{Conclusion and future work} \label{SectFuture}

The relatively small sizes of $\hat{k}_{m_1, m_2}$ in cases of all pairs $m_1, m_2$ tested support the plausibility of GGC, suggesting that the conjecture merits further investigation.

For all pairs $m_1, m_2\leq 40$ relatively prime, algorithms applying descending search were faster than those using ascending search. Heuristic arguments suggest that this is probably the case in general. However, speed rankings of the two algorithms using descending [ascending] search varied by $m_1, m_2$. The fastest algorithm can be further developed, and potentially combined with sieving methods. Hence, it would be useful to obtain predictions for the fastest one for given $m_1, m_2$ when testing up to large thresholds. Hypotheses H$_1(10^9, N_{m_1, m_2})$ and H$_2(10^9, N_{m_1, m_2})$  were true in our implementation for most $m_1, m_2$ tested, providing support to H$_1$ and H$_2$. Further computational experiments, and developing approximations to  $p^*_{m_1, m_2}(n)$ could help assess their plausibility, and possibly propose  better predictions. It would  be interesting to devise  predictions for the speed rankings purely based on $m_1, m_2$. 

Ranking by size  of the averages $\overline{p^*}_L(m_1, m_2)$ for different $m_1, m_2\leq 40$ for $L$ sufficiently  large appears to be independent of $L$. (We could observe this in our data only when $L\leq 10^{12}$, but this is likely to be the case also for all  larger $L$.) Explaining this ranking---and, in particular, the observation that $\overline{p^*}_{10^9}(m_1, m_2)&gt;\overline{p^*}_{10^9}(m_2, m_1)$ for all $m_1&lt;m_2$ tested (Table \ref{TableAverMaxp})---by the properties of $m_1$ and $m_2$ is a future goal.

Efficient sieving methods could be developed (and potentially combined with one of the four algorithms described) for testing GGC up to higher thresholds.



\section{Tables of data} \label{SectTables}

\begin{table}[H]
	\centering
{\resizebox{.6\columnwidth}{!}{%
\begin{tabular}{|l|c|c|c|c|c|}
			\hline
			&amp; \multicolumn{2}{c|}{5 greatest values}  &amp;	    \multicolumn{2}{c|}{5 smallest values} &amp;   Average \\
			
			
			&amp;  \multicolumn{1}{c|}{value}     &amp; $(m_1, m_2)$ &amp;  \multicolumn{1}{c|}{value} &amp; $(m_1, m_2)$ &amp; value\\
			\hline
			\hline	
			
			$\max \; {p^*_{m_1, m_2}}$ up to $10^9$ &amp; $78697$ &amp; $(32, 37)$ &amp;  $449$ &amp; $(30, 1)$ &amp;  $22889.33538$\\
			&amp; $77723$ &amp; $(23, 37)$  &amp; $557$ &amp; $(17, 1)$  &amp; \\
			
			&amp; $77267$ &amp; $(37, 38)$ &amp; $571$ &amp; $(39, 1)$ &amp; \\
			
			&amp; $76379$ &amp; $(29, 38)$ &amp; $599$ &amp; $(21, 1)$ &amp; \\
			
			&amp; $75989$ &amp; $(1, 38)$  &amp; $631$ &amp; $(24, 1)$  &amp; \\
			\hline				
			
			$\overline{p^*}_{{}_{m_1, m_2}}$ up to $10^9$ &amp; $2064.47552$ &amp; $(1, 37)$ &amp; $12.74269$ &amp; $(30, 1)$  &amp; $687.7063317$\\
			
			&amp; $2059.89836$ &amp; $(1, 38)$ &amp; $15.37864$ &amp; $(15, 1)$  &amp; \\
			
			&amp; $2059.17801$ &amp; $(16, 37)$  &amp; $16.68819$ &amp; $(21, 1)$  &amp; \\
			
			&amp; $2059.1531$ &amp; $(32, 37)$  &amp; $17.27778$ &amp; $(36, 1)$  &amp; \\
			
			&amp; $2058.97664$ &amp; $(2, 37)$  &amp; $17.27898$ &amp; $(6, 1)$  &amp; \\
			
			\hline		
			
			$\hat{k}_{m_1, m_2}$ 	&amp; $412987$ &amp; $(32, 37)$, $(37, 32)$ &amp; $2$ &amp; $(1, 1)$  &amp; $52004.838776$\\		
			
			&amp; $403357$ &amp; $(34, 37)$, $(37, 34)$  &amp; $5$ &amp; $(1, 2)$, $(2, 1)$  &amp; \\		
			
			&amp; $390367$ &amp; $(37, 38)$, $(38, 37)$ &amp; $10$ &amp; $(1, 3)$, $(3, 1)$  &amp; \\		
			
			&amp; $377122$ &amp; $(29, 37)$,  $(37, 29)$ &amp; $13$ &amp; $(1, 6)$, $(6, 1)$  &amp; \\		
			
			&amp; $370837$ &amp; $(29, 32)$, $(32, 29)$  &amp; $17$ &amp; $(2, 3)$, $(3, 2)$  &amp; \\		
			\hline		
		\end{tabular}
		}}
\caption{The five greatest, smallest, and the average values of $\max{p^*_{m_1, m_2}}$ and of $\overline{p^*}_{m_1, m_2}$ up to $10^9$ and of $\hat{k}_{m_1, m_2}$ over all pairs $m_1, m_2\leq 40$ relatively prime.}
\label{TableGrSmAv}
\end{table}

		
{\small{
	\begin{center}	
\begin{longtable}[c]{|c|c|c||c|c|c||c|c|c||c|c|c|}  
	\hline	
	$m_1$ &amp; $m_2$ &amp; $\hat{k}_{m_1, m_2}$ &amp; $m_1$ &amp; $m_2$ &amp; $\hat{k}_{m_1, m_2}$ &amp; $m_1$ &amp; $m_2$ &amp; $\hat{k}_{m_1, m_2}$ &amp; $m_1$ &amp; $m_2$ &amp; $\hat{k}_{m_1, m_2}$   \\
	\hline
	\endhead 
	\hline
	
	\caption{The value of $\hat{k}_{m_1, m_2}$ 	for all 
	relatively prime $m_1\leq m_2\leq 40$.} 
	\endfoot		
		1  &amp; 1  &amp; 2                 &amp; 5  &amp; 32 &amp; 12541             &amp; 12 &amp; 13 &amp; 11449             &amp; 20 &amp; 31 &amp; 102659            \\
		1  &amp; 2  &amp; 5                 &amp; 5  &amp; 33 &amp; 3182              &amp; 12 &amp; 17 &amp; 15101             &amp; 20 &amp; 33 &amp; 29797             \\
		1  &amp; 3  &amp; 10                &amp; 5  &amp; 34 &amp; 13511             &amp; 12 &amp; 19 &amp; 8737              &amp; 20 &amp; 37 &amp; 156137            \\
		1  &amp; 4  &amp; 77                &amp; 5  &amp; 36 &amp; 4699              &amp; 12 &amp; 23 &amp; 16739             &amp; 20 &amp; 39 &amp; 26251             \\
		1  &amp; 5  &amp; 24                &amp; 5  &amp; 37 &amp; 12718             &amp; 12 &amp; 25 &amp; 10477             &amp; 21 &amp; 22 &amp; 29191             \\
		1  &amp; 6  &amp; 13                &amp; 5  &amp; 38 &amp; 14527             &amp; 12 &amp; 29 &amp; 25889             &amp; 21 &amp; 23 &amp; 21962             \\
		1  &amp; 7  &amp; 36                &amp; 5  &amp; 39 &amp; 4954              &amp; 12 &amp; 31 &amp; 18547             &amp; 21 &amp; 25 &amp; 20554             \\
		1  &amp; 8  &amp; 49                &amp; 6  &amp; 7  &amp; 421               &amp; 12 &amp; 35 &amp; 14303             &amp; 21 &amp; 26 &amp; 33767             \\
		1  &amp; 9  &amp; 28                &amp; 6  &amp; 11 &amp; 1361              &amp; 12 &amp; 37 &amp; 67777             &amp; 21 &amp; 29 &amp; 30746             \\
		1  &amp; 10 &amp; 29                &amp; 6  &amp; 13 &amp; 1723              &amp; 13 &amp; 14 &amp; 17827             &amp; 21 &amp; 31 &amp; 30112             \\
		1  &amp; 11 &amp; 54                &amp; 6  &amp; 17 &amp; 2447              &amp; 13 &amp; 15 &amp; 3802              &amp; 21 &amp; 32 &amp; 44473             \\
		1  &amp; 12 &amp; 25                &amp; 6  &amp; 19 &amp; 3133              &amp; 13 &amp; 16 &amp; 32507             &amp; 21 &amp; 34 &amp; 47323             \\
		1  &amp; 13 &amp; 116               &amp; 6  &amp; 23 &amp; 4901              &amp; 13 &amp; 17 &amp; 28876             &amp; 21 &amp; 37 &amp; 41794             \\
		1  &amp; 14 &amp; 163               &amp; 6  &amp; 25 &amp; 2489              &amp; 13 &amp; 18 &amp; 11239             &amp; 21 &amp; 38 &amp; 54287             \\
		1  &amp; 15 &amp; 46                &amp; 6  &amp; 29 &amp; 10987             &amp; 13 &amp; 19 &amp; 30782             &amp; 21 &amp; 40 &amp; 22943             \\
		1  &amp; 16 &amp; 473               &amp; 6  &amp; 31 &amp; 10369             &amp; 13 &amp; 20 &amp; 25913             &amp; 22 &amp; 23 &amp; 108041            \\
		1  &amp; 17 &amp; 526               &amp; 6  &amp; 35 &amp; 2059              &amp; 13 &amp; 21 &amp; 6542              &amp; 22 &amp; 25 &amp; 91277             \\
		1  &amp; 18 &amp; 37                &amp; 6  &amp; 37 &amp; 9427              &amp; 13 &amp; 22 &amp; 49631             &amp; 22 &amp; 27 &amp; 49333             \\
		1  &amp; 19 &amp; 452               &amp; 7  &amp; 8  &amp; 2711              &amp; 13 &amp; 23 &amp; 44446             &amp; 22 &amp; 29 &amp; 161383            \\
		1  &amp; 20 &amp; 109               &amp; 7  &amp; 9  &amp; 754               &amp; 13 &amp; 24 &amp; 14221             &amp; 22 &amp; 31 &amp; 133283            \\
		1  &amp; 21 &amp; 88                &amp; 7  &amp; 10 &amp; 2453              &amp; 13 &amp; 25 &amp; 25658             &amp; 22 &amp; 35 &amp; 91579             \\
		1  &amp; 22 &amp; 401               &amp; 7  &amp; 11 &amp; 2294              &amp; 13 &amp; 27 &amp; 16078             &amp; 22 &amp; 37 &amp; 229309            \\
		1  &amp; 23 &amp; 832               &amp; 7  &amp; 12 &amp; 2371              &amp; 13 &amp; 28 &amp; 74849             &amp; 22 &amp; 39 &amp; 56323             \\
		1  &amp; 24 &amp; 97                &amp; 7  &amp; 13 &amp; 12326             &amp; 13 &amp; 29 &amp; 64634             &amp; 23 &amp; 24 &amp; 39959             \\
		1  &amp; 25 &amp; 296               &amp; 7  &amp; 15 &amp; 1192              &amp; 13 &amp; 30 &amp; 12949             &amp; 23 &amp; 25 &amp; 76528             \\
		1  &amp; 26 &amp; 337               &amp; 7  &amp; 16 &amp; 10463             &amp; 13 &amp; 31 &amp; 82826             &amp; 23 &amp; 26 &amp; 106201            \\
		1  &amp; 27 &amp; 136               &amp; 7  &amp; 17 &amp; 8104              &amp; 13 &amp; 32 &amp; 80609             &amp; 23 &amp; 27 &amp; 50872             \\
		1  &amp; 28 &amp; 1157              &amp; 7  &amp; 18 &amp; 6841              &amp; 13 &amp; 33 &amp; 16024             &amp; 23 &amp; 28 &amp; 136651            \\
		1  &amp; 29 &amp; 1588              &amp; 7  &amp; 19 &amp; 17846             &amp; 13 &amp; 34 &amp; 99131             &amp; 23 &amp; 29 &amp; 172076            \\
		1  &amp; 30 &amp; 61                &amp; 7  &amp; 20 &amp; 8387              &amp; 13 &amp; 35 &amp; 48364             &amp; 23 &amp; 30 &amp; 26633             \\
		1  &amp; 31 &amp; 2918              &amp; 7  &amp; 22 &amp; 10729             &amp; 13 &amp; 36 &amp; 31249             &amp; 23 &amp; 31 &amp; 201812            \\
		1  &amp; 32 &amp; 1951              &amp; 7  &amp; 23 &amp; 13492             &amp; 13 &amp; 37 &amp; 92006             &amp; 23 &amp; 32 &amp; 225457            \\
		1  &amp; 33 &amp; 214               &amp; 7  &amp; 24 &amp; 6583              &amp; 13 &amp; 38 &amp; 91009             &amp; 23 &amp; 33 &amp; 51094             \\
		1  &amp; 34 &amp; 1313              &amp; 7  &amp; 25 &amp; 8618              &amp; 13 &amp; 40 &amp; 63913             &amp; 23 &amp; 34 &amp; 163993            \\
		1  &amp; 35 &amp; 226               &amp; 7  &amp; 26 &amp; 22657             &amp; 14 &amp; 15 &amp; 2921              &amp; 23 &amp; 35 &amp; 81274             \\
		1  &amp; 36 &amp; 397               &amp; 7  &amp; 27 &amp; 4556              &amp; 14 &amp; 17 &amp; 43423             &amp; 23 &amp; 36 &amp; 68507             \\
		1  &amp; 37 &amp; 1616              &amp; 7  &amp; 29 &amp; 29516             &amp; 14 &amp; 19 &amp; 56237             &amp; 23 &amp; 37 &amp; 269506            \\
		1  &amp; 38 &amp; 1117              &amp; 7  &amp; 30 &amp; 3217              &amp; 14 &amp; 23 &amp; 42709             &amp; 23 &amp; 38 &amp; 273151            \\
		1  &amp; 39 &amp; 272               &amp; 7  &amp; 31 &amp; 25304             &amp; 14 &amp; 25 &amp; 23447             &amp; 23 &amp; 39 &amp; 85906             \\
		1  &amp; 40 &amp; 1241              &amp; 7  &amp; 32 &amp; 28057             &amp; 14 &amp; 27 &amp; 19787             &amp; 23 &amp; 40 &amp; 181699            \\
		2  &amp; 3  &amp; 17                &amp; 7  &amp; 33 &amp; 5224              &amp; 14 &amp; 29 &amp; 63871             &amp; 24 &amp; 25 &amp; 44329             \\
		2  &amp; 5  &amp; 163               &amp; 7  &amp; 34 &amp; 36461             &amp; 14 &amp; 31 &amp; 71413             &amp; 24 &amp; 29 &amp; 83609             \\
		2  &amp; 7  &amp; 89                &amp; 7  &amp; 36 &amp; 6091              &amp; 14 &amp; 33 &amp; 19571             &amp; 24 &amp; 31 &amp; 83507             \\
		2  &amp; 9  &amp; 115               &amp; 7  &amp; 37 &amp; 39896             &amp; 14 &amp; 37 &amp; 83717             &amp; 24 &amp; 35 &amp; 50339             \\
		2  &amp; 11 &amp; 673               &amp; 7  &amp; 38 &amp; 21691             &amp; 14 &amp; 39 &amp; 17189             &amp; 24 &amp; 37 &amp; 100333            \\
		2  &amp; 13 &amp; 719               &amp; 7  &amp; 39 &amp; 6472              &amp; 15 &amp; 16 &amp; 8221              &amp; 25 &amp; 26 &amp; 110687            \\
		2  &amp; 15 &amp; 173               &amp; 7  &amp; 40 &amp; 30407             &amp; 15 &amp; 17 &amp; 6668              &amp; 25 &amp; 27 &amp; 39586             \\
		2  &amp; 17 &amp; 2371              &amp; 8  &amp; 9  &amp; 1633              &amp; 15 &amp; 19 &amp; 9664              &amp; 25 &amp; 28 &amp; 88909             \\
		2  &amp; 19 &amp; 1757              &amp; 8  &amp; 11 &amp; 6509              &amp; 15 &amp; 22 &amp; 8161              &amp; 25 &amp; 29 &amp; 102808            \\
		2  &amp; 21 &amp; 275               &amp; 8  &amp; 13 &amp; 18461             &amp; 15 &amp; 23 &amp; 12428             &amp; 25 &amp; 31 &amp; 165446            \\
		2  &amp; 23 &amp; 2209              &amp; 8  &amp; 15 &amp; 1399              &amp; 15 &amp; 26 &amp; 13421             &amp; 25 &amp; 32 &amp; 215743            \\
		2  &amp; 25 &amp; 2399              &amp; 8  &amp; 17 &amp; 22273             &amp; 15 &amp; 28 &amp; 16963             &amp; 25 &amp; 33 &amp; 28454             \\
		2  &amp; 27 &amp; 781               &amp; 8  &amp; 19 &amp; 19427             &amp; 15 &amp; 29 &amp; 29396             &amp; 25 &amp; 34 &amp; 146911            \\
		2  &amp; 29 &amp; 4339              &amp; 8  &amp; 21 &amp; 3517              &amp; 15 &amp; 31 &amp; 22636             &amp; 25 &amp; 36 &amp; 87859             \\
		2  &amp; 31 &amp; 3229              &amp; 8  &amp; 23 &amp; 47249             &amp; 15 &amp; 32 &amp; 15227             &amp; 25 &amp; 37 &amp; 251206            \\
		2  &amp; 33 &amp; 659               &amp; 8  &amp; 25 &amp; 14081             &amp; 15 &amp; 34 &amp; 19219             &amp; 25 &amp; 38 &amp; 197587            \\
		2  &amp; 35 &amp; 3733              &amp; 8  &amp; 27 &amp; 10427             &amp; 15 &amp; 37 &amp; 21236             &amp; 25 &amp; 39 &amp; 40738             \\
		2  &amp; 37 &amp; 11251             &amp; 8  &amp; 29 &amp; 43711             &amp; 15 &amp; 38 &amp; 23873             &amp; 26 &amp; 27 &amp; 39293             \\
		2  &amp; 39 &amp; 1679              &amp; 8  &amp; 31 &amp; 57719             &amp; 16 &amp; 17 &amp; 42103             &amp; 26 &amp; 29 &amp; 174451            \\
		3  &amp; 4  &amp; 55                &amp; 8  &amp; 33 &amp; 10841             &amp; 16 &amp; 19 &amp; 62507             &amp; 26 &amp; 31 &amp; 233429            \\
		3  &amp; 5  &amp; 62                &amp; 8  &amp; 35 &amp; 46243             &amp; 16 &amp; 21 &amp; 12349             &amp; 26 &amp; 33 &amp; 65059             \\
		3  &amp; 7  &amp; 94                &amp; 8  &amp; 37 &amp; 57173             &amp; 16 &amp; 23 &amp; 61861             &amp; 26 &amp; 35 &amp; 142981            \\
		3  &amp; 8  &amp; 251               &amp; 8  &amp; 39 &amp; 21799             &amp; 16 &amp; 25 &amp; 62849             &amp; 26 &amp; 37 &amp; 262897            \\
		3  &amp; 10 &amp; 133               &amp; 9  &amp; 10 &amp; 811               &amp; 16 &amp; 27 &amp; 26209             &amp; 27 &amp; 28 &amp; 56647             \\
		3  &amp; 11 &amp; 140               &amp; 9  &amp; 11 &amp; 2066              &amp; 16 &amp; 29 &amp; 133321            &amp; 27 &amp; 29 &amp; 74744             \\
		3  &amp; 13 &amp; 322               &amp; 9  &amp; 13 &amp; 3008              &amp; 16 &amp; 31 &amp; 128783            &amp; 27 &amp; 31 &amp; 54784             \\
		3  &amp; 14 &amp; 461               &amp; 9  &amp; 14 &amp; 2789              &amp; 16 &amp; 33 &amp; 26981             &amp; 27 &amp; 32 &amp; 82343             \\
		3  &amp; 16 &amp; 853               &amp; 9  &amp; 16 &amp; 7657              &amp; 16 &amp; 35 &amp; 55963             &amp; 27 &amp; 34 &amp; 86791             \\
		3  &amp; 17 &amp; 554               &amp; 9  &amp; 17 &amp; 3968              &amp; 16 &amp; 37 &amp; 186427            &amp; 27 &amp; 35 &amp; 41098             \\
		3  &amp; 19 &amp; 616               &amp; 9  &amp; 19 &amp; 7498              &amp; 16 &amp; 39 &amp; 48067             &amp; 27 &amp; 37 &amp; 94342             \\
		3  &amp; 20 &amp; 1247              &amp; 9  &amp; 20 &amp; 3803              &amp; 17 &amp; 18 &amp; 16151             &amp; 27 &amp; 38 &amp; 86143             \\
		3  &amp; 22 &amp; 817               &amp; 9  &amp; 22 &amp; 11119             &amp; 17 &amp; 19 &amp; 48058             &amp; 27 &amp; 40 &amp; 63599             \\
		3  &amp; 23 &amp; 2204              &amp; 9  &amp; 23 &amp; 7454              &amp; 17 &amp; 20 &amp; 37717             &amp; 28 &amp; 29 &amp; 202273            \\
		3  &amp; 25 &amp; 838               &amp; 9  &amp; 25 &amp; 6658              &amp; 17 &amp; 21 &amp; 13382             &amp; 28 &amp; 31 &amp; 180791            \\
		3  &amp; 26 &amp; 1777              &amp; 9  &amp; 26 &amp; 10271             &amp; 17 &amp; 22 &amp; 83597             &amp; 28 &amp; 33 &amp; 78469             \\
		3  &amp; 28 &amp; 1951              &amp; 9  &amp; 28 &amp; 6469              &amp; 17 &amp; 23 &amp; 89464             &amp; 28 &amp; 37 &amp; 250961            \\
		3  &amp; 29 &amp; 1178              &amp; 9  &amp; 29 &amp; 12058             &amp; 17 &amp; 24 &amp; 39791             &amp; 28 &amp; 39 &amp; 69259             \\
		3  &amp; 31 &amp; 3358              &amp; 9  &amp; 31 &amp; 14422             &amp; 17 &amp; 25 &amp; 39332             &amp; 29 &amp; 30 &amp; 60619             \\
		3  &amp; 32 &amp; 3131              &amp; 9  &amp; 32 &amp; 17021             &amp; 17 &amp; 26 &amp; 89533             &amp; 29 &amp; 31 &amp; 243562            \\
		3  &amp; 34 &amp; 1423              &amp; 9  &amp; 34 &amp; 14803             &amp; 17 &amp; 27 &amp; 34108             &amp; 29 &amp; 32 &amp; 370837            \\
		3  &amp; 35 &amp; 608               &amp; 9  &amp; 35 &amp; 5392              &amp; 17 &amp; 28 &amp; 51589             &amp; 29 &amp; 33 &amp; 105254            \\
		3  &amp; 37 &amp; 3814              &amp; 9  &amp; 37 &amp; 18976             &amp; 17 &amp; 29 &amp; 101834            &amp; 29 &amp; 34 &amp; 244907            \\
		3  &amp; 38 &amp; 5741              &amp; 9  &amp; 38 &amp; 21271             &amp; 17 &amp; 30 &amp; 13703             &amp; 29 &amp; 35 &amp; 166534            \\
		3  &amp; 40 &amp; 2347              &amp; 9  &amp; 40 &amp; 20533             &amp; 17 &amp; 31 &amp; 109916            &amp; 29 &amp; 36 &amp; 97793             \\
		4  &amp; 5  &amp; 361               &amp; 10 &amp; 11 &amp; 7489              &amp; 17 &amp; 32 &amp; 120691            &amp; 29 &amp; 37 &amp; 377122            \\
		4  &amp; 7  &amp; 1691              &amp; 10 &amp; 13 &amp; 11051             &amp; 17 &amp; 33 &amp; 52004             &amp; 29 &amp; 38 &amp; 289069            \\
		4  &amp; 9  &amp; 629               &amp; 10 &amp; 17 &amp; 13813             &amp; 17 &amp; 35 &amp; 64166             &amp; 29 &amp; 39 &amp; 117254            \\
		4  &amp; 11 &amp; 2383              &amp; 10 &amp; 19 &amp; 14621             &amp; 17 &amp; 36 &amp; 45109             &amp; 29 &amp; 40 &amp; 228577            \\
		4  &amp; 13 &amp; 4073              &amp; 10 &amp; 21 &amp; 3811              &amp; 17 &amp; 37 &amp; 203162            &amp; 30 &amp; 31 &amp; 54337             \\
		4  &amp; 15 &amp; 1291              &amp; 10 &amp; 23 &amp; 22993             &amp; 17 &amp; 38 &amp; 173681            &amp; 30 &amp; 37 &amp; 56227             \\
		4  &amp; 17 &amp; 7759              &amp; 10 &amp; 27 &amp; 10537             &amp; 17 &amp; 39 &amp; 45572             &amp; 31 &amp; 32 &amp; 344761            \\
		4  &amp; 19 &amp; 12167             &amp; 10 &amp; 29 &amp; 28411             &amp; 17 &amp; 40 &amp; 86201             &amp; 31 &amp; 33 &amp; 87794             \\
		4  &amp; 21 &amp; 1537              &amp; 10 &amp; 31 &amp; 35303             &amp; 18 &amp; 19 &amp; 35353             &amp; 31 &amp; 34 &amp; 317567            \\
		4  &amp; 23 &amp; 24499             &amp; 10 &amp; 33 &amp; 10567             &amp; 18 &amp; 23 &amp; 28153             &amp; 31 &amp; 35 &amp; 176636            \\
		4  &amp; 25 &amp; 7181              &amp; 10 &amp; 37 &amp; 45817             &amp; 18 &amp; 25 &amp; 10843             &amp; 31 &amp; 36 &amp; 171971            \\
		4  &amp; 27 &amp; 6511              &amp; 10 &amp; 39 &amp; 12731             &amp; 18 &amp; 29 &amp; 48683             &amp; 31 &amp; 37 &amp; 363658            \\
		4  &amp; 29 &amp; 15133             &amp; 11 &amp; 12 &amp; 3623              &amp; 18 &amp; 31 &amp; 37957             &amp; 31 &amp; 38 &amp; 348349            \\
		4  &amp; 31 &amp; 17723             &amp; 11 &amp; 13 &amp; 13018             &amp; 18 &amp; 35 &amp; 16937             &amp; 31 &amp; 39 &amp; 121438            \\
		4  &amp; 33 &amp; 2773              &amp; 11 &amp; 14 &amp; 11293             &amp; 18 &amp; 37 &amp; 53407             &amp; 31 &amp; 40 &amp; 313541            \\
		4  &amp; 35 &amp; 9271              &amp; 11 &amp; 15 &amp; 1646              &amp; 19 &amp; 20 &amp; 76319             &amp; 32 &amp; 33 &amp; 108593            \\
		4  &amp; 37 &amp; 21881             &amp; 11 &amp; 16 &amp; 25723             &amp; 19 &amp; 21 &amp; 12112             &amp; 32 &amp; 35 &amp; 195197            \\
		4  &amp; 39 &amp; 5443              &amp; 11 &amp; 17 &amp; 18404             &amp; 19 &amp; 22 &amp; 76493             &amp; 32 &amp; 37 &amp; 412987            \\
		5  &amp; 6  &amp; 191               &amp; 11 &amp; 18 &amp; 6893              &amp; 19 &amp; 23 &amp; 110416            &amp; 32 &amp; 39 &amp; 113111            \\
		5  &amp; 7  &amp; 458               &amp; 11 &amp; 19 &amp; 35254             &amp; 19 &amp; 24 &amp; 34129             &amp; 33 &amp; 34 &amp; 136343            \\
		5  &amp; 8  &amp; 1333              &amp; 11 &amp; 20 &amp; 17911             &amp; 19 &amp; 25 &amp; 91904             &amp; 33 &amp; 35 &amp; 39994             \\
		5  &amp; 9  &amp; 274               &amp; 11 &amp; 21 &amp; 4022              &amp; 19 &amp; 26 &amp; 120737            &amp; 33 &amp; 37 &amp; 99146             \\
		5  &amp; 11 &amp; 1516              &amp; 11 &amp; 23 &amp; 44204             &amp; 19 &amp; 27 &amp; 26038             &amp; 33 &amp; 38 &amp; 132331            \\
		5  &amp; 12 &amp; 953               &amp; 11 &amp; 24 &amp; 9707              &amp; 19 &amp; 28 &amp; 78671             &amp; 33 &amp; 40 &amp; 71023             \\
		5  &amp; 13 &amp; 4582              &amp; 11 &amp; 25 &amp; 31634             &amp; 19 &amp; 29 &amp; 125218            &amp; 34 &amp; 35 &amp; 166597            \\
		5  &amp; 14 &amp; 3379              &amp; 11 &amp; 26 &amp; 42073             &amp; 19 &amp; 30 &amp; 27077             &amp; 34 &amp; 37 &amp; 403357            \\
		5  &amp; 16 &amp; 4889              &amp; 11 &amp; 27 &amp; 10994             &amp; 19 &amp; 31 &amp; 169292            &amp; 34 &amp; 39 &amp; 139459            \\
		5  &amp; 17 &amp; 2542              &amp; 11 &amp; 28 &amp; 39167             &amp; 19 &amp; 32 &amp; 171469            &amp; 35 &amp; 36 &amp; 52631             \\
		5  &amp; 18 &amp; 1187              &amp; 11 &amp; 29 &amp; 70618             &amp; 19 &amp; 33 &amp; 68188             &amp; 35 &amp; 37 &amp; 201062            \\
		5  &amp; 19 &amp; 3082              &amp; 11 &amp; 30 &amp; 11021             &amp; 19 &amp; 34 &amp; 156803            &amp; 35 &amp; 38 &amp; 206653            \\
		5  &amp; 21 &amp; 656               &amp; 11 &amp; 31 &amp; 45646             &amp; 19 &amp; 35 &amp; 69442             &amp; 35 &amp; 39 &amp; 53336             \\
		5  &amp; 22 &amp; 7523              &amp; 11 &amp; 32 &amp; 63601             &amp; 19 &amp; 36 &amp; 44647             &amp; 36 &amp; 37 &amp; 113177            \\
		5  &amp; 23 &amp; 9218              &amp; 11 &amp; 34 &amp; 64321             &amp; 19 &amp; 37 &amp; 162286            &amp; 37 &amp; 38 &amp; 390367            \\
		5  &amp; 24 &amp; 4229              &amp; 11 &amp; 35 &amp; 31228             &amp; 19 &amp; 39 &amp; 50608             &amp; 37 &amp; 39 &amp; 140548            \\
		5  &amp; 26 &amp; 16543             &amp; 11 &amp; 36 &amp; 18121             &amp; 19 &amp; 40 &amp; 103619            &amp; 37 &amp; 40 &amp; 264023            \\
		5  &amp; 27 &amp; 2858              &amp; 11 &amp; 37 &amp; 68018             &amp; 20 &amp; 21 &amp; 16129             &amp; 38 &amp; 39 &amp; 188473            \\
		5  &amp; 28 &amp; 8237              &amp; 11 &amp; 38 &amp; 84419             &amp; 20 &amp; 23 &amp; 78457             &amp; 39 &amp; 40 &amp; 145279            \\
		5  &amp; 29 &amp; 10246             &amp; 11 &amp; 39 &amp; 26018             &amp; 20 &amp; 27 &amp; 20663             &amp;    &amp;    &amp;                   \\
		5  &amp; 31 &amp; 11668             &amp; 11 &amp; 40 &amp; 59399             &amp; 20 &amp; 29 &amp; 142097            &amp;    &amp;    &amp;                
 \label{TableCountEx}  \end{longtable} 
\end{center}
}}

\begin{table}[H]
\centering
\resizebox{\columnwidth}{!}{%
{\tiny{			 	
		 	\begin{tabular}{|c|c|c|c|c|c||c|c|c|c|c|c||c|c|c|c|c|c|} 
		 \hline	
	$m_1$ &amp; 	$m_2$ &amp; \multicolumn{2}{c|}{$p^*_{m_1, m_2}(n)$}  &amp; \multicolumn{2}{c||}{$q^*_{m_1, m_2}(n)$}  &amp; 	$m_1$ &amp; $m_2$ &amp; \multicolumn{2}{c|}{$p^*_{m_1, m_2}(n)$}  &amp; \multicolumn{2}{c||}{$q^*_{m_1, m_2}(n)$}  &amp; 	$m_1$ &amp; $m_2$ &amp; \multicolumn{2}{c|}{$p^*_{m_1, m_2}(n)$}  &amp; \multicolumn{2}{c|}{$q^*_{m_1, m_2}(n)$} \\		
		 &amp;  &amp; avg &amp; max  &amp; avg  &amp; max &amp;   &amp;   &amp; avg  &amp; max  &amp; avg  &amp; max  &amp;   &amp;   &amp; avg  &amp; max  &amp; avg  &amp; max  \\	
		 \hline
		1     &amp; 1     &amp;       &amp;       &amp;       &amp;       &amp; 4     &amp; 9     &amp; 241.822 &amp; 7927  &amp; 97.774 &amp; 3001  &amp; 9     &amp; 13    &amp; 333.584 &amp; 10193 &amp; 222.26 &amp; 6761 \\
		1     &amp; 2     &amp; 80.839 &amp; 3037  &amp; 32.8  &amp; 1609  &amp; 4     &amp; 11    &amp; 494.758 &amp; 19507 &amp; 160.372 &amp; 5939  &amp; 9     &amp; 14    &amp; 331.513 &amp; 10067 &amp; 198.584 &amp; 6337 \\
		1     &amp; 3     &amp; 72.911 &amp; 2371  &amp; 20.072 &amp; 743   &amp; 4     &amp; 13    &amp; 607.515 &amp; 24919 &amp; 163.502 &amp; 6311  &amp; 9     &amp; 16    &amp; 463.174 &amp; 13627 &amp; 241.826 &amp; 7219 \\
		1     &amp; 4     &amp; 181.026 &amp; 6971  &amp; 32.806 &amp; 1453  &amp; 4     &amp; 15    &amp; 327.845 &amp; 9257  &amp; 73.338 &amp; 2153  &amp; 9     &amp; 17    &amp; 464.765 &amp; 13007 &amp; 227.655 &amp; 6481 \\
		1     &amp; 5     &amp; 176.526 &amp; 6833  &amp; 26.767 &amp; 1093  &amp; 4     &amp; 17    &amp; 841.539 &amp; 29669 &amp; 167.531 &amp; 6553  &amp; 9     &amp; 19    &amp; 528.846 &amp; 15649 &amp; 229.533 &amp; 6301 \\
		1     &amp; 6     &amp; 157.484 &amp; 4969  &amp; 17.279 &amp; 643   &amp; 4     &amp; 19    &amp; 960.026 &amp; 32801 &amp; 168.921 &amp; 6947  &amp; 9     &amp; 20    &amp; 449.818 &amp; 13921 &amp; 180.773 &amp; 5519 \\
		1     &amp; 7     &amp; 281.84 &amp; 9431  &amp; 29.376 &amp; 1129  &amp; 5     &amp; 6     &amp; 118.745 &amp; 3457  &amp; 93.492 &amp; 2801  &amp; 10    &amp; 11    &amp; 370.28 &amp; 13093 &amp; 339.42 &amp; 12241 \\
		1     &amp; 8     &amp; 393.604 &amp; 15497 &amp; 32.806 &amp; 1493  &amp; 5     &amp; 7     &amp; 211.95 &amp; 8969  &amp; 145.513 &amp; 6871  &amp; 10    &amp; 13    &amp; 454.483 &amp; 15731 &amp; 345.898 &amp; 11117 \\
		1     &amp; 9     &amp; 245.866 &amp; 8431  &amp; 20.072 &amp; 647   &amp; 5     &amp; 8     &amp; 295.392 &amp; 10369 &amp; 172.142 &amp; 6229  &amp; 10    &amp; 17    &amp; 632.311 &amp; 21647 &amp; 354.305 &amp; 14369 \\
		1     &amp; 10    &amp; 382.522 &amp; 13009 &amp; 23.958 &amp; 1153  &amp; 5     &amp; 9     &amp; 184.588 &amp; 5333  &amp; 97.315 &amp; 2731  &amp; 10    &amp; 19    &amp; 721.599 &amp; 25057 &amp; 357.248 &amp; 13033 \\
		1     &amp; 11    &amp; 500.068 &amp; 17093 &amp; 31.678 &amp; 1499  &amp; 5     &amp; 11    &amp; 375.582 &amp; 11839 &amp; 156.587 &amp; 5881  &amp; 11    &amp; 12    &amp; 304.228 &amp; 8821  &amp; 267.184 &amp; 8293 \\
		1     &amp; 12    &amp; 342.648 &amp; 11261 &amp; 17.279 &amp; 673   &amp; 5     &amp; 12    &amp; 257.838 &amp; 7309  &amp; 93.511 &amp; 2969  &amp; 11    &amp; 13    &amp; 542.8 &amp; 17299 &amp; 452.035 &amp; 16829 \\
		1     &amp; 13    &amp; 612.063 &amp; 23663 &amp; 32.294 &amp; 1297  &amp; 5     &amp; 13    &amp; 459.273 &amp; 16477 &amp; 159.551 &amp; 5521  &amp; 11    &amp; 14    &amp; 542.423 &amp; 20359 &amp; 406.549 &amp; 15227 \\
		1     &amp; 14    &amp; 611.042 &amp; 20359 &amp; 26.557 &amp; 1129  &amp; 5     &amp; 14    &amp; 459.822 &amp; 15773 &amp; 141.315 &amp; 4651  &amp; 11    &amp; 15    &amp; 295.49 &amp; 8941  &amp; 203.796 &amp; 5527 \\
		1     &amp; 15    &amp; 332.373 &amp; 9127  &amp; 15.379 &amp; 557   &amp; 5     &amp; 16    &amp; 638.409 &amp; 24677 &amp; 172.167 &amp; 6451  &amp; 11    &amp; 16    &amp; 754.067 &amp; 26839 &amp; 494.633 &amp; 17863 \\
		1     &amp; 16    &amp; 849.623 &amp; 33997 &amp; 32.803 &amp; 1597  &amp; 5     &amp; 17    &amp; 637.215 &amp; 22751 &amp; 163.446 &amp; 5657  &amp; 11    &amp; 17    &amp; 751.415 &amp; 25621 &amp; 463.029 &amp; 17713 \\
		1     &amp; 17    &amp; 846.422 &amp; 32779 &amp; 33.084 &amp; 1381  &amp; 5     &amp; 18    &amp; 398.036 &amp; 10499 &amp; 93.511 &amp; 2963  &amp; 11    &amp; 18    &amp; 470.391 &amp; 14251 &amp; 267.222 &amp; 7681 \\
		1     &amp; 18    &amp; 529.975 &amp; 15313 &amp; 17.28 &amp; 701   &amp; 5     &amp; 19    &amp; 726.834 &amp; 25609 &amp; 164.784 &amp; 5711  &amp; 11    &amp; 19    &amp; 856.789 &amp; 27581 &amp; 466.872 &amp; 15467 \\
		1     &amp; 19    &amp; 964.977 &amp; 33791 &amp; 33.364 &amp; 1321  &amp; 6     &amp; 7     &amp; 149.317 &amp; 4597  &amp; 129.94 &amp; 3923  &amp; 11    &amp; 20    &amp; 734.055 &amp; 26497 &amp; 370.239 &amp; 12853 \\
		1     &amp; 20    &amp; 825.834 &amp; 29209 &amp; 23.957 &amp; 1069  &amp; 6     &amp; 11    &amp; 267.139 &amp; 8543  &amp; 139.856 &amp; 4813  &amp; 12    &amp; 13    &amp; 328.85 &amp; 9871  &amp; 310.206 &amp; 9479 \\
		2     &amp; 3     &amp; 69.352 &amp; 2083  &amp; 43.626 &amp; 1399  &amp; 6     &amp; 13    &amp; 328.759 &amp; 10883 &amp; 142.486 &amp; 4957  &amp; 12    &amp; 17    &amp; 459.61 &amp; 13033 &amp; 317.598 &amp; 10657 \\
		2     &amp; 5     &amp; 172.137 &amp; 6379  &amp; 60.482 &amp; 2459  &amp; 6     &amp; 17    &amp; 459.546 &amp; 14731 &amp; 145.948 &amp; 4201  &amp; 12    &amp; 19    &amp; 523.692 &amp; 14699 &amp; 320.198 &amp; 9437 \\
		2     &amp; 7     &amp; 277.107 &amp; 12011 &amp; 66.282 &amp; 2663  &amp; 6     &amp; 19    &amp; 523.593 &amp; 16703 &amp; 147.126 &amp; 4423  &amp; 13    &amp; 14    &amp; 552.943 &amp; 19889 &amp; 499.815 &amp; 16843 \\
		2     &amp; 9     &amp; 241.78 &amp; 7129  &amp; 43.628 &amp; 1549  &amp; 7     &amp; 8     &amp; 323.92 &amp; 12589 &amp; 277.119 &amp; 11197 &amp; 13    &amp; 15    &amp; 301.049 &amp; 8539  &amp; 250.574 &amp; 7151 \\
		2     &amp; 11    &amp; 494.633 &amp; 21107 &amp; 71.487 &amp; 3061  &amp; 7     &amp; 9     &amp; 202.501 &amp; 5717  &amp; 154.108 &amp; 4271  &amp; 13    &amp; 16    &amp; 768.659 &amp; 28463 &amp; 607.268 &amp; 25127 \\
		2     &amp; 13    &amp; 607.339 &amp; 21383 &amp; 72.924 &amp; 3049  &amp; 7     &amp; 10    &amp; 315.347 &amp; 9769  &amp; 207.433 &amp; 6841  &amp; 13    &amp; 17    &amp; 765.986 &amp; 25747 &amp; 566.894 &amp; 21851 \\
		2     &amp; 15    &amp; 327.714 &amp; 9049  &amp; 32.917 &amp; 1031  &amp; 7     &amp; 11    &amp; 411.838 &amp; 15131 &amp; 249.973 &amp; 9439  &amp; 13    &amp; 18    &amp; 479.435 &amp; 15199 &amp; 328.849 &amp; 9277 \\
		2     &amp; 17    &amp; 841.438 &amp; 30859 &amp; 74.71 &amp; 3121  &amp; 7     &amp; 12    &amp; 282.761 &amp; 9137  &amp; 149.358 &amp; 4663  &amp; 13    &amp; 19    &amp; 873.509 &amp; 33703 &amp; 571.528 &amp; 22079 \\
		2     &amp; 19    &amp; 959.87 &amp; 34039 &amp; 75.341 &amp; 3001  &amp; 7     &amp; 13    &amp; 504.267 &amp; 18593 &amp; 254.754 &amp; 10099 &amp; 13    &amp; 20    &amp; 748.115 &amp; 27953 &amp; 454.483 &amp; 14851 \\
		3     &amp; 4     &amp; 97.757 &amp; 2939  &amp; 69.363 &amp; 2411  &amp; 7     &amp; 15    &amp; 274.865 &amp; 7499  &amp; 116.406 &amp; 3583  &amp; 14    &amp; 15    &amp; 270.331 &amp; 7789  &amp; 248.994 &amp; 6689 \\
		3     &amp; 5     &amp; 97.292 &amp; 2909  &amp; 55.338 &amp; 1709  &amp; 7     &amp; 16    &amp; 700.594 &amp; 22783 &amp; 277.12 &amp; 10357 &amp; 14    &amp; 17    &amp; 693.436 &amp; 25121 &amp; 566.271 &amp; 20717 \\
		3     &amp; 7     &amp; 154.073 &amp; 4517  &amp; 60.42 &amp; 1789  &amp; 7     &amp; 17    &amp; 698.137 &amp; 24109 &amp; 260.916 &amp; 11069 &amp; 14    &amp; 19    &amp; 791.453 &amp; 27277 &amp; 570.866 &amp; 20873 \\
		3     &amp; 8     &amp; 211.872 &amp; 6869  &amp; 69.37 &amp; 2383  &amp; 7     &amp; 18    &amp; 436.631 &amp; 13367 &amp; 149.359 &amp; 4481  &amp; 15    &amp; 16    &amp; 347.11 &amp; 9521  &amp; 327.84 &amp; 8893 \\
		3     &amp; 10    &amp; 208.887 &amp; 6359  &amp; 51.951 &amp; 1471  &amp; 7     &amp; 19    &amp; 796.433 &amp; 27583 &amp; 263.145 &amp; 10289 &amp; 15    &amp; 17    &amp; 349.899 &amp; 9539  &amp; 308.256 &amp; 8179 \\
		3     &amp; 11    &amp; 271.626 &amp; 8231  &amp; 64.839 &amp; 2113  &amp; 7     &amp; 20    &amp; 682.396 &amp; 23689 &amp; 207.435 &amp; 6841  &amp; 15    &amp; 19    &amp; 398.729 &amp; 10979 &amp; 310.687 &amp; 9109 \\
		3     &amp; 13    &amp; 333.472 &amp; 10733 &amp; 66.064 &amp; 1999  &amp; 8     &amp; 9     &amp; 241.796 &amp; 7027  &amp; 211.92 &amp; 6961  &amp; 16    &amp; 17    &amp; 841.42 &amp; 30727 &amp; 787.381 &amp; 29531 \\
		3     &amp; 14    &amp; 331.38 &amp; 10259 &amp; 57.045 &amp; 1867  &amp; 8     &amp; 11    &amp; 494.594 &amp; 18481 &amp; 348.832 &amp; 13499 &amp; 16    &amp; 19    &amp; 959.865 &amp; 35327 &amp; 793.796 &amp; 28631 \\
		3     &amp; 16    &amp; 463.076 &amp; 13553 &amp; 69.361 &amp; 2239  &amp; 8     &amp; 13    &amp; 607.287 &amp; 23887 &amp; 355.623 &amp; 12107 &amp; 17    &amp; 18    &amp; 491.044 &amp; 14149 &amp; 459.684 &amp; 12953 \\
		3     &amp; 17    &amp; 464.638 &amp; 12503 &amp; 67.628 &amp; 2269  &amp; 8     &amp; 15    &amp; 327.799 &amp; 9091  &amp; 158.333 &amp; 4817  &amp; 17    &amp; 19    &amp; 894.547 &amp; 33721 &amp; 790.894 &amp; 26927 \\
		3     &amp; 19    &amp; 528.697 &amp; 15217 &amp; 68.167 &amp; 2063  &amp; 8     &amp; 17    &amp; 841.438 &amp; 31081 &amp; 364.403 &amp; 15749 &amp; 17    &amp; 20    &amp; 765.917 &amp; 28429 &amp; 632.339 &amp; 25237 \\
		3     &amp; 20    &amp; 449.579 &amp; 12659 &amp; 51.956 &amp; 1579  &amp; 8     &amp; 19    &amp; 959.894 &amp; 42727 &amp; 367.416 &amp; 13999 &amp; 18    &amp; 19    &amp; 523.747 &amp; 14897 &amp; 495.035 &amp; 16943 \\
		4     &amp; 5     &amp; 172.187 &amp; 7109  &amp; 135.388 &amp; 5521  &amp; 9     &amp; 10    &amp; 208.976 &amp; 6469  &amp; 180.762 &amp; 5501  &amp; 19    &amp; 20    &amp; 772.014 &amp; 28729 &amp; 721.715 &amp; 24071 \\
		4     &amp; 7     &amp; 277.169 &amp; 11497 &amp; 148.746 &amp; 5939  &amp; 9     &amp; 11    &amp; 271.709 &amp; 8363  &amp; 218.093 &amp; 6827  &amp;       &amp;       &amp;       &amp;       &amp;       &amp;  \\\hline
		\end{tabular}%
		}} }
		\caption{Average and maximum values of  $p^*_{m_1, m_2}(n)$ and $q^*_{m_1, m_2}(n)$ where $n\leq 10^9$,	for all relatively prime $m_1\leq m_2\leq 40$.} \label{TableAverMaxp}
 \end{table} 
 
\begin{table}[H] 
\centering					
\resizebox{.8\columnwidth}{!}{%
\begin{tabularx}{\textwidth}{|p{1cm}|X|} 
\hline
						
				Group &amp;  The ordered pairs  $(m_1, m_2)$  contained by the group \\	
				\hline
				\hline	
				
				Ab: &amp; {\scriptsize (1, 3), (1, 9), (1, 15), (1, 21), (1, 33), (1, 39)}
				\\
				\hline
				
				Ac: &amp; {\scriptsize (1, 7), (1, 11), (1, 13), (1, 17), (1, 19), (1, 25), (1, 31), (1, 37), (2, 9), (2, 15), (2, 21), (7, 11)} \\
				\hline
				
				Ad: &amp; {\scriptsize (1, 5), (1, 27), (1, 35)} \\
				\hline
				
				Bb: &amp; {\scriptsize (1, 2), (1, 4), (1, 6), (1, 8), (1, 10), (1, 12), (1, 14), (1, 16), (1, 18), (1, 20), (1, 22), (1, 24), (1,~ 26), (1, 28), (1, 30), (1, 32), (1, 34), (1, 36), (1, 38), (1, 40), (3, 4), (3, 8), (3, 10), (3, 14), (3, 16), (3, 20), (3, 22), (3, 26), (3, 28), (3, 34), (3, 38), (3, 40), (5, 6), (5, 8), (5, 9), (5, 12), (5, ~ 14), (5, 16), (5, 18), (5, 21), (5, 22), (5, 24), (5, 26), (5, 27), (5, 28), (5, 32), (5, 33), (5,~ 34), (5, 36), (5, 38), (5, 39), (7, 8), (7, 9), (7, 10), (7, 12), (7, 15), (7, 16), (7, 18), (7, 20), (7, 22), (7, 24), (7, 26), (7, 27), (7, 30), (7, 32), (7, 33), (7, 34), (7, 36), (7, 38), (7, 39), (7, 40), (9,~ 10), (9, 14), (9, 16), (9, 20), (9, 22), (9, 26), (9, 28), (9, 34),
				(9, 38), (9, 40), (11, 12), (11, 14), (11,~ 15), (11, 16), (11, 18), (11, 20), (11, 21), (11, 24), (11, 25), (11, 26), (11, 27), (11, 28), (11, ~ 30), (11, 32), (11, 34), (11, 35), (11, 36), (11, 38), (11, 39), (11, 40), (13, 14), (13, 15), (13, 16), (13, 18), (13, 20), (13, 21), (13, 22), (13, 24), (13, 25), (13, 27), (13, 28), (13, 30), (13, 32), (13, 33), (13, 34), (13, 35), (13, 36), (13, 38), (13, 40), (15, 16),
				(15, 22), (15, 26), (15, 28), (15, 34), (15, 38), (17, 18), (17, 20), (17, 21), (17, 22), (17, 24), (17, 25), (17, 26), (17, 27), (17, 28), (17, 30), (17, 32), (17, 33), (17, 35), (17, 36), (17, 38), (17, 39), (17, 40), (19, 20), (19, 21), (19, 22), (19, 24), (19, 25), (19, 26), (19, 27), (19, 28), (19, 30), (19, 32), (19, 33), (19, 34), (19, 35), (19, 36), (19, 39), (19, 40), (21, 22),
				(21, 26), (21, 32), (21, 34), (21, 38), (21, 40), (23, 24), (23, 25), (23, 26), (23, 27), (23, 28), (23, 30), (23, 32), (23, 33), (23, 34), (23, 35), (23, 36), (23, 38), (23, 39), (25, 26), (25, 27), (25, 28), (25, 32), (25, 33), (25, 34), (25, 36), (25, 38), (25, 39), (27, 28), (27, 32), (27, 34), (27, 38), (27, 40), (29, 30),
				(29, 32), (29, 33), (29, 34), (29, 35), (29, 36), (29, 38), (29, 39), (31, 32), (31, 33), (31, 34), (31, 35), (31, 36), (31, 38), (31, 39), (33, 34), (33, 38), (33, 40), (35, 36), (35, 38), (35, 39), (37, 38), (37, 39), (39, 40)} \\
				\hline
				
					Bc: &amp; {\scriptsize (15, 32) }
				\\
				\hline
				
				Bd: &amp; {\scriptsize (3, 32)}  \\
				\hline
				
				Cc: &amp; {\scriptsize (1, 23), (1, 29), (2, 3), (2, 5), (2, 7), (2, 11), (2, 13), (2, 17), (2, 19), (2, 23), (2, 25), (2, 27), (2, 29), (2, 31), (2, 33), (2, 35), (2, 37), (2, 39), (3, 5), (3, 7), (3, 11), (3, 13), (3, 17), (3, 19), (3, 23), (3, 25), (3, 29), (3, 31), (3, 35), (3, 37), (4, 5), (4, 7), (4, 9), (4, 11), (4, 13), (4, 15),
				(4, 17), (4, 19), (4, 21), (4, 23), (4, 25), (4, 27), (4, 29), (4, 31), (4, 33), (4, 35), (4, 37), (4, 39), (5, 7), (5, 11), (5, 13), (5, 17), (5, 19), (5, 23), (5, 29), (5, 31), (5, 37), (6, 7), (6, 11), (6, 13), (6, 17), (6, 19), (6, 23), (6, 25), (6, 29), (6, 31), (6, 35), (6, 37), (7, 13), (7, 17), (7, 19), (7, 23), (7, 25),
				(7, 29), (7, 31), (7, 37), (8, 9), (8, 11), (8, 13), (8, 15), (8, 17), (8, 19), (8, 21), (8, 23), (8, 25), (8, 27), (8, 29), (8, 31), (8, 33), (8, 35), (8, 37), (8, 39), (9, 11), (9, 13), (9, 17), (9, 19), (9, 23), (9, 25), (9, 29), (9, 31), (9, 35), (9, 37), (10, 11), (10, 13), (10, 17), (10, 19), (10, 21), (10, 23), (10, 27), (10, 29), (10, 31), (10, 33), (10, 37), (10, 39), (11, 13), (11, 17), (11, 19), (11, 23), (11, 31), (11, 37), (12, 13), (12, 17), (12, 19), (12, 23), (12, 25), (12, 29), (12, 31), (12, 35), (12, 37), (13, 17), (13, 19), (13, 23), (13, 29),
				(13, 31), (13, 37), (14, 15), (14, 17), (14, 19), (14, 23), (14, 25), (14, 27), (14, 29), (14, 31), (14, 33), (14, 37), (14, 39), (15, 17), (15, 19), (15, 23), (15, 29), (15, 31), (15, 37), (16, 17), (16, 19), (16, 21), (16, 23), (16, 25), (16, 27), (16, 29), (16, 31), (16, 33), (16, 35), (16, 37), (16, 39), (17, 23), (17, 29), (17, 31), (17, 37), (18, 19), (18, 23), (18, 25), (18, 29), (18, 31), (18, 35), (18, 37), (19, 23), (19, 29), (19, 31), (19, 37), (20, 21), (20, 23), (20, 27),
				(20, 29), (20, 31), (20, 33), (20, 37), (20, 39), (21, 23), (21, 25), (21, 29), (21, 31), (21, 37), (22, 23), (22, 25), (22, 27), (22, 29), (22, 31), (22, 35), (22, 37), (22, 39), (23, 31), (23, 37), (24, 25), (24, 29), (24, 31), (24, 35), (24, 37), (25, 29), (25, 31), (25, 37), (26, 27), (26, 29), (26, 31), (26, 33), (26, 35), (26, 37), (27, 29), (27, 31), (27, 35), (27, 37), (28, 29), (28, 31), (28, 33), (28, 37), (28, 39), (29, 31), (29, 37), (30, 31), (30, 37), (31, 37), (32, 33), (32, 35), (32, 37), (32, 39), (33, 35), (33, 37), (34, 35), (34, 37), (34, 39), (35, 37), (36, 37), (38, 39)} \\
				\hline
				
				Db: &amp; {\scriptsize (9, 32), (23, 40), (29, 40), (31, 40), (37, 40)}  \\
				\hline			
				
				Dc: &amp; 
				{\scriptsize (11, 29), (17, 19),  (23, 29)}\\
				\hline 
			\end{tabularx}  			 
		}
	\caption{Classification of all pairs $ m_1&lt;m_2\leq 40$ relatively prime into groups A, B, C, and D and a, b, c, and d, 	indicated in the first column by upper and lower case letters, respectively.} \label{TableSpeeds}
\end{table} 

\section{Pseudocode for Algorithm 1} \label{SectPseudo}

{\begin{footnotesize}
		\begin{algorithm}[H] \label{FnGGCone}
			\Fn{\GGCone{$N,m_1,m_2, \triangle$, $\alpha$}}{
				\Input{positive integers $N, m_1,m_2$, $\triangle$,
					 and $\alpha$  such that $\gcd (m_1, m_2)=1$, $N &gt; 9$, $2m_1m_2|N$, $2m_1m_2| \triangle$, and  $\alpha\leq \triangle$.
				}
				\Output{array $\mathsf{residual}$ containing all numbers $n\leq N$ satisfying the conditions  of GGC$_{m_1, m_2}$ for which there do not exist primes $p$ and $q$ such that $n=m_1p+m_2q$ and $m_1p\leq \alpha$.}
				
				\tcc{\textbf{Start Phase I: Unsegmented phase}}
				\tcc{Generating array $\mathsf{primes}$.} 
				\textbf{SmallPrimes($\max{(\lfloor \sqrt{\frac{N_{m_1, m_2}}{m_2}} \rfloor, \lfloor\frac{\alpha}{m_1}\rfloor )})$}\;				
				
				\tcc{Assigning values to array  $\mathsf{ism_1p}$.}				
				
				\textbf{GenerateIsm1p}($\alpha$)\;
				
				\tcc{Assigning values to array  $\mathsf{res}$.}
				
				\textbf{GenerateResiduePattern}($m_1, m_2$)\;
				
				
				\tcc{\textbf{Start Phase II: Segmented phase}}
				
				\tcc{\textbf{Initialization}}
				
				
				Set arrays $\mathsf{residual}$ and $\mathsf{m_2q[r]}$ ($0\leq r&lt; m_1$) empty\;
				
				$A\leftarrow 0$\;
				
				
				\tcc{\textbf{Start segmented computation}}
				
				\While{$A&lt;N$}{
					
					$B\leftarrow \min{(A+\triangle, N)}$\;			
					
					
					\tcc{Keeping only those values in each array $\mathsf{m_2q[r]}$ generated in previous iteration which are greater than $A-\alpha$ and removing all other values.}	
					
					\If{$A&gt;0$}{
						\For{$r=0$ \KwTo $m_1-1$}{				
							
							
							$i\leftarrow 0$\;
							
							\While{$i&lt;\mathrm{length}(\mathsf{m_2q[r]})$ \textrm{and} $\mathsf{m_2q[r]}[i]&lt; A-\alpha$}{		        
								$i\leftarrow i + 1$\;
							}
							
							\If{$i\neq 0$}{
								remove\_interval($\mathsf{mq_2[r]}$, $[0,\ldots , i-1]$)}
						}		    
					}
					
					\tcc{Assigning new values to arrays $\mathsf{m_2q[r]}$.}
					\textbf{Generatem2qr$(A,B)$}\;
					\tcc{Checking GGC$_{m_1,m_2}$ in new interval.}
					
					\textbf{Check1$(A,B)$}\;
					
					$A\leftarrow A+\triangle$\;
					}		
			}  		
		
		\caption{Pseudocode for the main program  implementing Algorithm 1.}
		\end{algorithm} 		
\end{footnotesize}}

\begin{normalsize}


\section{Acknowledgments}
We thank the anonymous referees for their helpful comments and suggestions regarding both content and presentation, which have lead to a much improved version of the paper.

\bibliographystyle{amsplain}

\begin{thebibliography}{99}	
	
	\bibitem{Barstow}  D. R. Barstow,  An experiment in knowledge-based automatic programming, \textit{Artificial
	Intelligence} \textbf{12}  (1979), 73--119.
	
	\bibitem{Bengelloun}  S. Bengelloun, An incremental primal sieve, \textit{Acta Inform.} \textbf{23}  (1986), 119--125.
	
	\bibitem{BaysHudson} C. Bays and R. H. Hudson, The segmented sieve of Eratosthenes and primes in arithmetic progressions to $10^{12}$, \textit{BIT} \textbf{17} (1977), 121--127. 
	
	
	\bibitem{Chen} J. R. Chen, On the representation of a large even number as the sum of a prime and the product of at most two primes, \textit{Sci. Sin.} \textbf{16} (1973), 157--176.	
	
	\bibitem{Dickson1904} L. E. Dickson, A new extension of Dirichlet's theorem on prime numbers, \textit{Messenger of Mathematics}  {\bf33} (1904), 155--161.
	
	\bibitem{Dickson1919} L. E. Dickson, \textit{History of the Theory of Numbers, Vol. I}, Carnegie Institution of Washington, 1919.
	
	\bibitem{FarkasJuhasz} G. Farkas and Zs. Juh\'asz,  A generalization of Goldbach's conjecture, \textit{Ann. Univ. Sci. Budapest. Sect. Comput.} {\bf 46} (2017), 39--53.
	
	\bibitem{Fuss} P. N. Fuss,  \textit{Correspondance Math\'ematique et Physique de Quelques C\'el\`ebres G\'eom\`etres du XVIII\`eme Si\`ecle}, L'Impr. de l'Acad\'emie imp\'eriale des sciences, 1843.	
	
	\bibitem{Granville1989} A. Granville, J. van de Lune, and H. J. J. te Riele, Checking the Goldbach conjecture on a vector computer, in R. A. Mollin, ed., \textit{Number Theory and Applications,} Kluwer Academic Publishers,  1989, pp. 423--433.	
	
	\bibitem{GriesMisra}  D. Gries  and  J. Misra,  A linear sieve algorithm for finding prime numbers, \textit{Commun. ACM} \textbf{21} (1978), 999--1003.
		
	\bibitem{Hardy} G. H. Hardy and J. E. Littlewood,  Some problems of `Partitio numerorum'; III: On the expression of a number as a sum of primes, \textit{Acta Math.} \textbf{44} (1923), 1--70. 	
	
	\bibitem{Helfgott2013} H. A. Helfgott,   The ternary Goldbach conjecture is true, arxiv preprint arXiv:1312.7748 [math.NT], 2013. Available at \url{https://arxiv.org/abs/1312.7748}.	
	
	\bibitem{Helfgott2015} H. A. Helfgott,  The ternary Goldbach problem, arxiv preprint arXiv:1501.05438 [math.NT], 2015. Available at 
	\url{https://arxiv.org/abs/1501.05438}.		
	
	\bibitem{Heath1988} D. R. Heath-Brown,  The number of primes in a short interval, \textit{J. Reine Angew. Math.} \textbf{389} (1988),  22--63.	
	
	
	\bibitem{Lemoine} \'E. Lemoine, Lemoine's conjecture,  \textit{L'Interm\'ediaire des Math\'ematiciens} \textbf{1} (1894), 179.
	
	\bibitem{Maier} H. Maier, Primes in short intervals, \textit{Michigan Math. J.} \textbf{32}  (1985), 221--225. 
	
	\bibitem{MaketheBrain} Make the Brain Happy,  Lemoine's conjecture verified to $10^{10}$, 2019, \url{https://www.makethebrainhappy.com/2019/06/lemoines-conjecture-verified-to-1010.html}. 
	
	\bibitem{Misra} J. Misra, An exercise in program explanation, \textit{ACM Transactions on Programming Languages and Systems} \textbf{3}  (1981), 104--109.
	
	\bibitem{Oliveira2013}  T. Oliveira e Silva,  Goldbach conjecture verification, 2015, \url{http://sweet.ua.pt/tos/goldbach.html}. 
	
	\bibitem{Oliveira2014}  T. Oliveira e Silva,  S. Herzog,  and S. Pardi, Empirical verification of the even Goldbach conjecture and computation of prime gaps up to $4\cdot 10^{18}$,  \textit{Math. Comp.} {\bf 83}  (2014), 2033--2060.
	
	\bibitem{Pipping}  N. Pipping, Die Goldbachsche Vermutung und der Goldbach-Vinogradovsche Satz, \textit{Acta Acad. Aboensis, Math. Phys.} \textbf{11} (1938), 4--25.	
	
	\bibitem{Prichard} P. Pritchard,  Linear prime-number sieves: a family tree, \textit{Sci. Comput. Program.} \textbf{9} (1987), 17--35.	
	
	\bibitem{Richstein}  J. Richstein, Verifying the Goldbach conjecture up to $4\cdot 10^{14}$, \textit{Math. Comp.} \textbf{70} (2000), 1745--1749.	
	
	\bibitem{Sinisalo}  M. K. Sinisalo, Checking the Goldbach conjecture up to $4\cdot 10^{11}$, \textit{Math. Comp.} \textbf{61} (1993), 931--934.	
	
	\bibitem{Sorenson} J. Sorenson, An introduction to prime number sieves, Computer Sciences Technical Report $\# 909$,  University of Wisconsin-Madison, Department of Computer Sciences, 1990. Available at: \url{https://minds.wisconsin.edu/handle/1793/59248}.
	
	\bibitem{Wen} W. C. Lu,  Exceptional set of Goldbach number, \textit{J. Number Theory} \textbf{130} (2010),  2359--2392. 
	
\end{thebibliography}



\bigskip
\hrule
\bigskip

\noindent 2020 {\it Mathematics Subject Classification}:
Primary 11A41; Secondary 11P32.

\noindent \emph{Keywords: } Goldbach conjecture, Lemoine's conjecture, prime number.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000040},
\seqnum{A002091},
\seqnum{A002092},
\seqnum{A046927},
\seqnum{A194828},
\seqnum{A195352},
\seqnum{A195353}, and
\seqnum{A195354}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received March 31 2023;
revised versions received April 1 2023; July 24 2023; February 2 2024.
Published in {\it Journal of Integer Sequences}, March 18 2024.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{normalsize}

\end{document}


</pre></body></html>