\documentstyle[amscd,amssymb,verbatim,12pt,lscape]{amsart}
\input psfig

\setlength{\textwidth}{6.2in}
\setlength{\textheight}{8in}
\setlength{\oddsidemargin}{.2in}
\setlength{\topmargin}{-0.25in}
\setlength{\headheight}{0in}

\newtheorem{lemma}{Lemma}
\newtheorem{cor}{Corollary}
\newtheorem{theorem}{Theorem}

\theoremstyle{definition}
\newtheorem{conj}{Conjecture}

\theoremstyle{remark}
\newtheorem{rem}{Remark}	\renewcommand{\therem}{}
\newtheorem{rems}{Remarks}	\renewcommand{\therems}{}

\newcommand{\C}{\Bbb C}
\newcommand{\Q}{\Bbb Q}
\newcommand{\Z}{{\Bbb Z}}
\newcommand{\R}{{\Bbb R}}

\newcommand{\Erdos}{Erd\H{o}s\ }

\newcommand{\abs}[1]{\left| #1 \right|}


\renewcommand{\theequation}{\thesection.\arabic{equation}}
\newcounter{\theequation}


\renewcommand{\baselinestretch}{1.123}

\begin{document}

\title[Jumping Champions]{Jumping Champions}
\subjclass{}
\keywords{}
\date{1997}

\author{Andrew Odlyzko}
\address{AT\&T Labs -  Research\\ Florham Park, NJ 07932, USA, 
amo@@research.att.com}

\author{Michael Rubinstein}
\address{Princeton University, Princeton, NJ, 08544, USA,
miker@@math.princeton.edu}

\author{Marek Wolf}
\address{Institute of Theoretical Physics, University of Wroclaw, Wroclaw, 
PL-50-204, Poland, mwolf@@proton.ift.uni.wroc.pl}

\maketitle

\paragraph{Abstract:}
The asymptotic frequency with which pairs of primes below $x$ differ by some
fixed integer is understood heuristically, although not rigorously,
through the Hardy-Littlewood k-tuple conjecture.  Less is known about
the differences of consecutive primes.  For all $x$ between $1000$
and $10^{12}$, the most common difference between consecutive 
primes is $6$.  We present heuristic and empirical evidence that $6$ 
continues as the most common difference (jumping champion) up to
about $x=1.7427\cdot10^{35}$, where it is replaced by $30$.  
In turn, $30$ is eventually
displaced by $210$, which then is displaced by $2310$, and so on.
Our heuristic arguments are based on a quantitative form of
the Hardy-Littlewood conjecture.  The technical difficulties in
dealing with consecutive primes are formidable enough that even
that strong conjecture does not suffice to produce a rigorous
proof about the behavior of jumping champions.


\vspace*{+.1in}


%****************************************************************************
\setcounter{equation}{0}
\setcounter{table}{0}
\setcounter{figure}{0}
\section{Introduction}
\label{intro}

An integer $D$ is called a jumping champion
if $D$ is the most frequently occurring difference between
consecutive primes $\leq x$ for some $x$ (occasionally there are several 
jumping champions).  Since the initial primes are $2, 3, 5, 7, 11$, the jumping 
champions are 1 for $x = 3$, 1 and 2 for $x = 5$, 2 for $x = 7$,
and 2 for $x = 11$.  (It is clear that we only need to consider prime
values of $x$.)

Jumping champions for various $x$ up to around 1000 are presented in 
Table~\ref{initial-champions}.
Initially 2 and 4 dominate as jumping champions, with 2 showing up more
frequently than 4, and 6 showing up only a few times.  
However, at $x = 563$, $D = 6$ takes over
as jumping champion, and except for $x = 941$, where it shares leadership
with $D = 4$, is the only champion at least up to $x = 10^{12}$.
One might therefore be led to conclude that 6 should remain
the jumping champion out to infinity.  However, this appears to be another
of the many number theoretic functions where the initial
behavior is misleading.  We will present heuristics that
suggest that 6 does not remain jumping champion forever.
\begin{conj}
   \label{conj-jumping-champions}
   The jumping champions are 4 and the primorials $2,6,30,210,2310,\ldots$.
\end{conj}

The heuristics (see Section 2) suggest that 6 is the jumping champion up to about
$x=1.7427\cdot10^{35}$, where 30 becomes the jumping champion.
(Harley~\cite{Harley}, stimulated by a report on an early phase of
our research, has independently computed this number as the point of
transition between 6 and 30.)  In turn, 30 is displaced
as jumping champion by 210 around $x=10^{425}$.  This is substantiated 
by numerical experimentation (see the end of Section 2 and Table~\ref{transitions}).
It is likely that in the transition zones,
the two contenders in all cases trade places as jumping champions, but
we have neither the computing power to verify
this numerically nor the theoretical tools to prove it.
Although Conjecture~\ref{conj-jumping-champions} is very simple and 
elegant, it is surprisingly deep.

The heuristics we develop are based on the famous
Hardy-Littlewood $k$-tuple conjecture.  
The twin prime conjecture says that there exist infinitely
many primes $p$ such that $p+2$ is also a prime.  On the other
hand, there is only a single prime $p$ such that $p$, $p+2$, and
$p+4$ are all primes, since at least one of these 3 integers
is divisible by 3.  The Hardy-Littlewood $k$-tuple conjecture~\cite{HL}
is that unless there is a trivial divisibility condition
that stops  $p, p+a_1, \ldots, p+a_{k}$ from 
consisting of primes infinitely often, then such prime tuples will
occur, and will even occur with a certain asympotic density
that is easy to compute in terms of the $a_i$.  While there
is a general belief that the $k$-tuple conjecture is true,
it remains unproven.

There seems to be little
hope of making any progress towards a proof of 
Conjecture~\ref{conj-jumping-champions} without assuming at least a 
quantitative form of the $k$-tuple conjecture.  However, as we will show, even 
assuming the strongest form of that conjecture that seems reasonable in
view of our knowledge of prime numbers, we are still left
with formidable obstacles that prevent us from obtaining
a complete proof of Conjecture~\ref{conj-jumping-champions}.  Still, in 
investigating jumping champions, we are led to some nice combinatorics related to 
the coefficients in the $k$-tuple conjecture.  

A strong form of the $k$-tuple conjecture leads to an
explicit asymptotic formula for the frequency with which an integer
$D$ appears as the difference of consecutive primes $\leq x$.
This formula has some interesting arithmetical properties,
and it leads to the "irregularly regular" behavior shown in 
Figure~\ref{irregular-regular}. Brent~\cite{Brent} was the first
to suggest this formula and gave an algorithm for computing certain
coefficients that arise in the formula.

A conjecture that follows from Conjecture~\ref{conj-jumping-champions}, 
but should be considerably easier to prove, and might conceivably be
provable unconditionally, is the following.

\begin{conj}
   \label{conj-weaker}
   The jumping champions tend to infinity. Furthermore, any fixed prime
   $p$ divides all sufficiently large jumping champions.
\end{conj}

The first part of Conjecture~\ref{conj-weaker} was proved by 
\Erdos and Straus~\cite{ES}
under the assumption of a quantitative form of the $k$-tuple 
conjecture.  

As far as we are aware, the first question about
the behavior of jumping champions was raised (without use of
the term jumping champion, which was invented by John Horton Conway 
in 1993) by Harry Nelson in 1977-8~\cite{Nelson}. \Erdos  and Straus, 
motivated by Nelson's note, proved, under the assumption
of a form of the $k$-tuple conjecture, that jumping champions
for $x$ tend to infinity with $x$.  They also raised the question
of the rate at which champions tend to infinity.  We answer
this question in our note, assuming (as \Erdos and Straus
suggested might have to be done) stronger conjectures.
These suggest that the size of the champion jumps from
$(1 + o(1)) \log{x} / (\log\log x)^2$ to
$(1 + o(1)) \log{x} / (\log\log x)$ 
when $x$ is the transition point, and then, as $x$ increases, proceeds 
to decrease down to $(1 + o(1)) \log{x} / (\log\log x)^2$ again.  

Jumping champions have been thought about independently
several times since the work of \Erdos and Straus.  We were
led to look at them by John Conway.  Meally and Leech have
also asked about their behavior~\cite{Guy}.


%*************************************************************************
\section{The Heuristics}

\subsection{The $k$-tuple Conjecture}
Let $0 < m_1 < m_2 < \ldots < m_k$.
The $k$-tuple conjecture predicts that the number of primes 
$p \leq x$ such that $p+2m_1,p+2m_2,\ldots,p+2m_k$ are all prime is
\begin{equation}
   \label{HL-conjecture}
   P(x;m_1,m_2,\ldots,m_k) \sim C(m_1,m_2,\ldots,m_k)
   \int_{2}^{x} \frac{dt}{\log^{k+1}{t}} 
\end{equation}
where
\begin{equation}
   \label{HL-constants}
   C(m_1,m_2,\ldots,m_k) = 2^k \prod_{q}
   \frac{\left(1-w(q;m_1,m_2,\ldots,m_k)/q\right)}{(1-1/q)^{k+1}}.
\end{equation}
In (\ref{HL-constants}), $q$ runs over all odd primes, and
$w(q;m_1,m_2,\ldots,m_k)$ denotes the number of distinct residues
of $0,m_1,m_2,\ldots,m_k$ mod $q$. Note that if $k=1$ then
\begin{equation}
   \label{2-tuple}
   C(m)=2\prod_q\frac{q(q-2)}{(q-1)^2}
   \prod_{q|m}\frac{(q-1)}{(q-2)}
\end{equation}
depends only on the odd primes dividing $m$, and $C(m_1)=C(m_2)$ iff
$m_1$ and $m_2$ have the same odd prime factors (possibly raised
to different powers).

For a discussion on the $k$-tuple conjecture and references to 
numerical computations in its support, see the introduction to
Halberstam and Richert~\cite{HR}.

Brent~\cite{Brent2}~\cite{Brent} was apparently the first one to study the size of
the error term in the $k$-tuple conjecture.
Hardy and Littlewood did not make any predictions about its size, although the 
standard arguments that assume random cancellation of various terms suggest
it should be of size about $\sqrt{x}$ for each $k$-tuple.  Brent's
computations~\cite[Table 4]{Brent2} support this suggestion for tuples
$p,p+2$ where we find a remainder with roughly half as many digits as the main 
term. See also the comment following~(\ref{A_d_k}).

\subsection{The Heuristics}
Let $N(x,d)$ be the number of primes $p \leq x$ such that
$p+2d$ is the smallest prime $> p$. By inclusion-exclusion we have
\begin{eqnarray}
   \label{inclusion}
   N(x,d) &\leq& \sum_{k=0}^{2K} (-1)^k
   \sum_{0<m_1<\ldots<m_k<d}P(x;m_1,\ldots,m_k,d), \hspace{.1in}
   K=0,1,\ldots \\  \label{exclusion}
   N(x,d) &\geq& \sum_{k=0}^{2K+1} (-1)^k
   \sum_{0<m_1<\ldots<m_k<d}P(x;m_1,\ldots,m_k,d)
\end{eqnarray}
(here the $k=0$ term is $P(x;d)$). So it is natural to compare $N(x,d)$
with
\begin{eqnarray}
   \label{N-asymptotics}
   \int_{2}^{x}
   \sum_{k=1}^{M}\frac{A_{d,k}}{\log^{k+1}{t}}dt
\end{eqnarray}
where $M$ is a positive integer and
\begin{equation}
   \label{A_d_k}
   A_{d,k}=(-1)^{k+1}\sum_{0<m_1<\ldots<m_{k-1}<d}
   C(m_1,\ldots,m_{k-1},d)
\end{equation}
(here $A_{d,1}=C(d)$).

Computations of Brent~\cite{Brent} indicate that taking all the terms 
in~(\ref{N-asymptotics}) (i.e. $M$ is chosen so that $A_{d,M+1}=0$)
approximates $N(x,d)$ to within $O(x^{1/2})$. This can be seen
in~\cite[Table 2]{Brent} which shows an agreement
(between theoretical approximation and reality) that agrees to roughly 
half the decimal places.

Now, the sum in (\ref{A_d_k}) runs over 
$\binom{d-1}{k-1}$ terms and it would not be unreasonable to
guess that $A_{d,k}$ grows nicely with this binomial coefficient. In fact, we show in 
Section 3, Theorem \ref{T:ratios} that for $k$ fixed,
\begin{displaymath}
   A_{d,k+1} \sim (-1)^k A_{d,1}\frac{(2d)^{k}}{k!}, 
   \hspace{.6in}
   \mbox{as $d \rightarrow \infty$}.
\end{displaymath}
This suggests, in conjuction with (\ref{N-asymptotics}), that,
for $d$ large,
\begin{equation}
   \label{N-asymptotics2}
   N(x,d) \sim A_{d,1} \int_2^x \frac{\exp(-2d/\log{t})}{\log^2{t}} dt
\end{equation}
should approximate well the number of gaps of
size $2d$ up to height $x$. However,
not only does $d$ have to be large for this to be a good approximation, but
$x$ has to be large compared to $d$, and this restricts the range in
which we may use (\ref{N-asymptotics2}).

The presence of the $A_{d,1}$ factor in (\ref{N-asymptotics2})
indicates that, in order to make $N(x,d)$ huge, it is preferable for $d$
to have many small prime factors. On the other hand, the $\exp(-2d/\log{t})$
term in the integrand tells us that amongst all $d$ that produce the same
value for $A_{d,1}$, the smallest one wins. More precisely, let
\begin{eqnarray*}
  2d_1 &=& 2^{a_0} p_1^{a_1} \ldots p_j^{a_j} \\
  2d_2 &=& 2 p_1 \ldots p_j \\
  2d_3 &=& 2 \cdot 3 \cdot \ldots q_j
\end{eqnarray*}
where $a_i \geq 1$, where the $p_i$'s are odd primes, and where 
$q_j$ is the $j$th odd prime ($q_1=3,q_2=5,\ldots$). 
Note that $d_3 \leq d_2 \leq d_1$. 

Formula (\ref{N-asymptotics2}) tells us that, for $d_3$
sufficiently large, we should expect $N(x,d_2) \geq N(x,d_1)$
(because $A_{d_2,1}=A_{d_1,1}$ but $d_2 \leq d_1$), and 
$N(x,d_3) \geq N(x,d_2)$ (because  $A_{d_3,1} \geq A_{d_2,1}$
and $d_3 < d_2$). So we see that primorials are favored.

Furthermore, integrating (\ref{N-asymptotics2}) by parts, we find that
$N(x, 3 \cdot \ldots q_{j+1})$ should begin to overtake
$N(x, 3 \cdot \ldots q_j)$ {\em roughly} when 
\begin{displaymath}
   \frac{q_{j+1}-1}{q_{j+1}-2} 
   \exp\left( 
          \frac{-2 \cdot 3 \cdot \ldots q_{j+1}}{\log{x}}
       \right) >
    \exp\left( 
          \frac{-2 \cdot 3 \cdot \ldots q_j}{\log{x}}
       \right)
\end{displaymath}
i.e. roughly when
\begin{displaymath}
   x > \exp(2 \cdot 3 \cdot \ldots q_j \cdot (q_{j+1}-1)(q_{j+1}-2)).
\end{displaymath}

These considerations justify Conjecture 1, at least for sufficiently
large gaps (and very large $x$). 
For smaller $d$, rather than using (\ref{N-asymptotics2}), we
could use the first few terms of (\ref{N-asymptotics}) to study
$N(x,d)$.

For example, $A_{1,1}=A_{2,1}$, and $A_{2,2}=0$ (since there are
no triplets of primes $p, p+2, p+4$ other than $3,5,7$).
Hence both both $N(x,1)$ and $N(x,2)$ should be very close to
\begin{displaymath}
   A_{1,1} \int_2^x \frac{dt}{\log^2{t}}.
\end{displaymath}
This explains why 4 also appears as a champion.

%xxx... 
%Perhaps we should say that N(x,1) and N(x,2) should differ by
%something of order sqrt(x)? However...
%Marek has done some computations (at my (Andrew's) urging)
%on the pi_2(x) - pi_4(x) (where pi_4(x) is the number of "cousins"),
%and this difference is considerably smaller than the difference
%between either pi_2(x) or pi_4(x) and the leading term of their
%asymptotic expansion, c_2*Li_2(x).

We can also determine roughly when 30 will take over from 6 as Champion,
and when 210 will first beat 30.
Using the coefficients from~\cite{Brent} to compute~(\ref{N-asymptotics}) 
with all the terms ($M=2$ when $2d=6$ and $M=8$ when $2d=30$), we
find that 30 should take over as Champion roughly at $x=1.7427\cdot10^{35}$.
Further, taking $M=4$ terms in~(\ref{N-asymptotics}), predicts that 210 will 
first begin to beat 30 sometime in the interval $10^{425} < x < 10^{426}$.
Numerical experimentation substantiates these claims. 
We used Maple's probable prime function to test intervals of
length $10^7$.  If all the probable primes that this function
produced for us are indeed prime, 
then in the interval
$[10^{30},10^{30}+10^{7}]$ there are 5278 gaps of size 6, and 5060 
gaps of size 30, whereas in the interval $[10^{40},10^{40}+10^{7}]$ 
there are 3120 gaps of size 6 and 3209 gaps of size 30.
(Note that even if some of the probable primes we found are not
prime, it is extremely likely there are few of them, so the
statistics we produce would not be noticeably affected.)
Further, in the intervals $[10^{400},10^{400}+10^{7}]$
we find that gaps of size 30 and 210 show up 50 and 33 times, respectively, 
and 26 and 34 times in the interval $[10^{450},10^{450}+10^{7}]$.
These last results are only roughly indicative of true behavior,
since sample sizes are so small.  In fact, in our data for
$10^{450}$, 198 appears to be the champion, as it shows up as
a gap of consecutive primes 40 times!

Section 3 is devoted to studying the coefficients $A_{d,k}$ that appear
in (\ref{N-asymptotics}).

%****************************************************************************
\setcounter{equation}{0}
\section{The coefficients $A_{d,k}$}
We turn now to the problem of estimating the coefficients $A_{d,k}$
that appear in (\ref{N-asymptotics}). In this section we use the 'Big Oh'
notation. $a=O(b)$ is equivalent to $\abs{a} \leq K \abs{b}$ for some constant $K$.
$a=O_c(b)$ is equivalent to $\abs{a} \leq K(c) \abs{b}$ for some $K(c)$.

We can prove (unconditionally)
\begin{theorem}
   \label{T:ratios}
   Let $1 \leq k \leq c\log\log{d}$, where $c$ is a constant. Then,
   \begin{equation}
     \label{recursion}
      A_{d,k+1}=-A_{d,k}\frac{2d}{k}\left(1+O_c(k/\log\log{d})\right)
   \end{equation}
\end{theorem}

\begin{rem}
Numerical data suggests (see Figure~\ref{fig_A_d_k}) that the $1+O_c(k/\log\log{d})$ 
above can be replaced by $1+O(k\log{d}/d)$.
\end{rem} 

\begin{pf}
First observe that if $A_{d,k}=0$ then $A_{d,k+1}=0$ and the theorem holds trivially.
($A_{d,k} =0$ implies that all $p,p+2m_1,\ldots,p+2m_{k-1},p+2d$ tuples are ruled out.
Hence, so are all the $p,p+2m_1,\ldots,p+2m_{k},p+2d$ tuples, because each one
contains (many) $p,p+2m_1,\ldots,p+2m_{k-1},p+2d$ sub-tuples). 
Therefore, assume $A_{d,k} \neq 0$.  From (\ref{HL-constants}) 
and (\ref{A_d_k}) we have 
\begin{displaymath}
   \frac{A_{d,k+1}}{A_{d,k}} 
      =\frac {-2 \sum\limits_{0<m_1<\ldots<m_{k}<d} \prod_q \left(1-w(q;m_1,m_2,\ldots,m_{k},d)/q\right) }
          {\sum\limits_{0<m_1<\ldots<m_{k-1}<d} \prod_q \left(1-w(q;m_1,m_2,\ldots,m_{k-1},d)/q\right)(1-1/q) }.
\end{displaymath}
(if $k=1$, the denominator is $\prod_q \left(1-w(q;d)/q\right)(1-1/q)$).
Now, if $q>d$ then, 
$w(q;m_1,m_2,\ldots,m_{k},d)=k+2$, and $w(q;m_1,m_2,\ldots,m_{k-1},d)=k+1$.
So the above is
\begin{equation}
   \label{ratio-As}
   \frac{A_{d,k+1}}{A_{d,k}} = - 2 P_1 P_2
\end{equation}
with
\begin{equation}
   \label{P_1}
   P_1= \frac
      {\sum\limits_{0<m_1<\ldots<m_{k}<d} \prod_{q \leq d} \left(1-w(q;m_1,m_2,\ldots,m_{k},d)/q\right) }
      {\sum\limits_{0<m_1<\ldots<m_{k-1}<d} \prod_{q \leq d} \left(1-w(q;m_1,m_2,\ldots,m_{k-1},d)/q\right)(1-1/q) }
\end{equation}
and
\begin{equation}
   \label{P_2}
   P_2=\prod_{q>d}\frac{(1-(k+2)/q)}{(1-1/q)(1-(k+1)/q)},
\end{equation}
$P_2$ poses little difficulty and is easily estimated by
using the Taylor series for $\log(1-x)$,
\begin{equation}
   \label{P_2-exp}
   P_2=\exp
   \left(
      -\sum_{m=2}^{\infty} \sum_{q>d}
      \frac{1}{m}\left(
         \left(\frac{k+2}{q}\right)^m
         -\left(\frac{k+1}{q}\right)^m
         -\frac{1}{q^m}
      \right)
   \right),
   \hspace{.5in}
   k+2 \leq d.
\end{equation}

Now
\begin{displaymath}
   0 < (k+2)^m - (k+1)^m -1 <m(k+2)^{m-1}, \hspace{.5in} m \geq 2
\end{displaymath}
which can be seen by writing 
\begin{displaymath}
   (k+2)^m-(k+1)^m=
   (k+2)^{m-1}+(k+2)^{m-2}(k+1)+\ldots+(k+1)^{m-1}.
\end{displaymath}
Hence
\begin{displaymath}
   1 > P_2 >
   \exp \left(  
      -\sum_{m=2}^{\infty} (k+2)^{m-1} \sum_{q>d} \frac{1}{q^m}
   \right).
\end{displaymath}
But
\begin{displaymath}
   \sum_{q>d} \frac{1}{q^m} < \sum_{n=d+1}^{\infty} \frac{1}{n^m} < \int_{d}^{\infty} \frac{dt}{t^m}
   = \frac{1}{(m-1)} \frac{1}{d^{m-1}},
\end{displaymath}
so
\begin{displaymath}
   1 > P_2 > \exp \left( 
                - \sum_{m=2}^{\infty} \frac{1}{(m-1)} \frac{(k+2)^{m-1}}{d^{m-1}}
             \right)
      =  1 - \frac{k+2}{d}, 
      \hspace{.5in}
   k+2 < d.
\end{displaymath}
i.e.
\begin{equation}
   \label{P2}
   P_2 = 1 + O(k/d), \hspace{.5in} k+2 < d.
\end{equation}
In fact, a better estimate is not hard to establish. Since (\ref{P2}) 
contributes less
than the error claimed in the theorem, we omit the proof and simply state
\begin{equation}
   P_2 = 1 - \frac{k}{d \log d} + 
   O\left( \frac{1}{d \log d} + \frac{k}{d \log^2 d} \right),
   \hspace{.5in} k < d/2.
\end{equation}
Next, consider $P_1$. On scrutinizing (\ref{P_1}), we see that 
each term in the denominator may be matched with terms in the numerator.
We write
\begin{equation}
   \label{P_1-b}
   P_1 = \frac{1}{k}
         \frac
         {
           \sum\limits_{0 < m_1 < \ldots < m_{k-1} < d}    
           \sum\limits_{ {0<m_0<d} \atop {m_0 \neq m_i; i=1,\ldots , k-1} }
              \prod_{q \leq d} 
              \left(1-w(q;m_0,m_1,\ldots,m_{k-1},d)/q\right)
         }
         {
           \sum\limits_{0 < m_1 < \ldots < m_{k-1} < d}
           \prod_{q \leq d} \left(1-w(q;m_1,m_2,\ldots,m_{k-1},d)/q\right)(1-1/q)
         }
\end{equation}
and claim that each inner sum in the numerator is approximately $d$ times its corresponding
term in the denominator. More precisely, we show that, for $k \leq c \log\log{d}$
($c$ a constant),
\begin{eqnarray}
   \label{inner-sum}
  && \sum\limits_{ {0<m_0<d} \atop {m_0 \neq m_i; i=1,\ldots , k-1}}
     \prod_{q \leq d}
     \left(1-w(q;m_0,m_1,\ldots,m_{k-1},d)/q\right) \nonumber \\
  &&  = d ( 1 + O_c (k / \log\log{d}) )
        \prod_{q \leq d} 
        \left(1-w(q;m_1,m_2,\ldots,m_{k-1},d)/q\right)(1-1/q).
\end{eqnarray}
The theorem would then follow on combining
(\ref{inner-sum}) with (\ref{P_1-b}), (\ref{P2}), and (\ref{ratio-As}).

To prove (\ref{inner-sum}), break up $\prod_{q \leq d}$ into two pieces.
Let
\begin{equation}
   \label{d-bounds}
   3 \cdot 5 \cdot \ldots \cdot q_a \leq d < 3 \cdot 5 \cdot \ldots \cdot q_{a+1},
   \hspace{.5in} d \geq 15
\end{equation}
and write 
\begin{equation}
   \label{product}
   \prod_{q \leq d} = \prod_{q \leq q_{a-1}} \prod_{q_a \leq q \leq d}.
\end{equation}
By the Prime Number Theorem, 
\begin{equation}
   \label{PNT}
   q_a \sim \log{d}.
\end{equation}

Now, if the r.h.s. of (\ref{inner-sum}) is zero (this happens if 
$w(q;m_1,\ldots,m_{k-1},d) = q$ for some $q \leq d$) then so is the l.h.s
(since then $w(q;m_0,m_1,\ldots,m_{k-1},d)$ also equals $q$), and (\ref{inner-sum})
is trivially true. So, assume that this isn't the case and consider
\begin{equation}
   \label{prod-f_q}
   \sum\limits_{ {0<m_0<d} \atop {m_0 \neq m_i; i=1,\ldots , k-1}}
       \prod_{q \leq q_{a-1}}
       \prod_{q_{a} \leq q \leq d} f_q(m_0,\ldots,m_{k-1},d),
\end{equation}
where
\begin{displaymath}
   f_q(m_0,\ldots,m_{k-1},d) = \frac
   {
      \left(1-w(q;m_0,m_1,\ldots,m_{k-1},d)/q\right)
   }
   {
      \left(1-w(q;m_1,m_2,\ldots,m_{k-1},d)/q\right)(1-1/q)
   }.
\end{displaymath}
To simplify things, (\ref{prod-f_q}) may be written as
\begin{displaymath}
   \sum_{m_0=1}^{d}\prod_{q \leq q_{a-1}}
                   \prod_{q_{a} \leq q \leq d} f_q(m_0,\ldots,m_{k-1},d)
   - k \prod_{q \leq d} \frac{1}{1-1/q}.
\end{displaymath}
The second term above is $O(k \log{d})$ (in fact, by a theorem
of Mertens~\cite{Ingham}, it contributes $\sim -\frac{k}{2}e^\gamma \log{d}$)
and will be overshadowed by the first term. So, let
\begin{equation}
   \label{S}
   S = \sum_{m_0=1}^{d}\prod_{q \leq q_{a-1}}
                   \prod_{q_{a} \leq q \leq d} f_q(m_0,\ldots,m_{k-1},d).
\end{equation}
Our goal is to show $S =  d ( 1 + O (k / \log\log{d}) )$.
We first estimate the contribution from $\prod_{q_{a} \leq q \leq d}$.
Letting $w_q = w(q;m_1,\ldots,m_{k-1},d)$, we have
\begin{equation}
   \label{w_q}
   w(q;m_0,m_1,\ldots,m_{k-1},d) = 
   \begin{cases}
      w_q &\mbox{if \hspace{.063in}} 
              q \mid m_0(m_1-m_0)\ldots(m_{k-1}-m_0)(d-m_0) \\
      w_q + 1 &\mbox{ otherwise}.
   \end{cases}
\end{equation}
For most $q$ (when $k$ is small compared to $d$) the latter holds.
In fact, let $L$ be the number of $q$'s that satisfy
\begin{enumerate}
   \item $q_{a} \leq q \leq d$
   \item $q \mid m_0(m_1-m_0)\ldots(m_{k-1}-m_0)(d-m_0)$.
\end{enumerate}
Now, $m_0(m_1-m_0)\ldots(m_{k-1}-m_0)(d-m_0) < d^{k+1}$, and so
$q_{a}^L < d^{k+1}$. Hence, from (\ref{PNT}),
\begin{equation}
   \label{L}
   L = O \left( \frac{k \log{d}}{\log\log{d}} \right).
\end{equation}
But
\begin{displaymath}
   \prod_{q_{a} \leq q \leq d} \frac{1-(k+2)/q}{(1-1/q)(1-(k+1)/q)} \leq
     \prod_{q_{a} \leq q \leq d} f_q 
   \leq \frac{1}{(1-1/q_a)^L}.
\end{displaymath}
The l.h.s above is roughly of the same form as (\ref{P_2}), and by (\ref{P2}), 
it is $1+O(k/q_a) =$ $1+O(k/\log{d})$, (so long as $k < (q_a -2) \sim \log{d}$).
Meanwhile,
\begin{eqnarray*}
   \frac{1}{(1-1/q_a)^L} 
       &=& e^{O(L/q_A)} \\
       &=& e^{O\left(k/\log\log{d}\right)}\\
       &=& 1 + O_c\left(k/\log\log{d}\right), 
\end{eqnarray*}
%xxx Note to myself:the constant in the last big O is exp(c) which can be seen by
%expanding exp in its Taylor series, keeping the 1, and pulling
%out a k/loglogd in the rest of the series
assuming $k \leq c\log\log{d}$, $c$ a constant.
Therefore, pulling out $\prod_{q_a \leq q \leq d} f_q$ from (\ref{S})
\begin{equation}
   \label{almost-there}
   S = \left( 1 + O_c\left(k/\log\log{d}\right) \right)
       \sum_{m_0=1}^{d}
       \prod_{q \leq q_{a-1}} f_q(m_0,\ldots,m_{k-1},d), \hspace{.2in} k \leq c\log\log{d}.
\end{equation}
Next, write 
\begin{eqnarray*}
   d &=& \alpha (3 \cdot 5 \cdot \ldots \cdot q_{a-1}) + \beta \\
     &=& \alpha Q + \beta,
\end{eqnarray*}
where, by (\ref{d-bounds}), $\alpha,\beta \in \Z$, $\alpha \geq q_a$, 
$0 \leq \beta < 3 \cdot 5 \cdot \ldots \cdot q_{a-1}$, and break up the
sum over $m_0$
\begin{displaymath}
   \sum_{m_0=1}^{d} = \sum_{m_0=1}^{\alpha Q} + \sum_{\alpha Q + 1}^{d}.
\end{displaymath}
The second sum on the r.h.s. contributes $O(\beta \log\log{d})$, which
can be seen from 
$\prod_{q \leq q_{a-1}} f_q \leq \prod_{q \leq q_{a-1}} 1/(1-1/q)$.
But $\beta < d/q_a = O(d/\log{d})$, so the
contribution to~(\ref{almost-there}) from this sum is
$O(d \log\log{d}/\log{d})$.
To complete our proof we show 
\begin{equation}
   \label{alpha-Q-sum}
   \sum_{m_0=1}^{\alpha Q} \prod_{q \leq q_{a-1}} f_q(m_0,\ldots,m_{k-1},d) = 
    \alpha Q = d (1+O(1/\log{d})).
\end{equation}
This in combination with all our other estimates will establish the theorem.

To prove~(\ref{alpha-Q-sum}), break up the range of summation $m_0=1,\ldots,\alpha Q$
into blocks of length $Q$ (there are $\alpha$ such blocks). Each block contributes
the same amount to~(\ref{alpha-Q-sum}) because 
$\prod_{q \leq q_{a-1}} f_q(m_0,\ldots,m_{k-1},d)$ depends only on the values 
modulo $Q$ of its arguements. Next, we show by induction on $a$ that
\begin{equation}
   \label{Q-sum}
   \sum_{m_0=1}^{q_1\cdot \ldots \cdot q_{a-1}} \prod_{q \leq q_{a-1}} f_q(m_0,\ldots,m_{k-1},d) = Q.
\end{equation}
If $a-1=1$, then our sum is
\begin{equation}
   \label{q_1-sum}
   \sum_{m_0=1}^{q_1} f_{q_1}(m_0,\ldots,m_{k-1},d) 
\end{equation}
Using the notation of~(\ref{w_q}), we find that~(\ref{q_1-sum}) sums to
\begin{displaymath}
    w_{q_1}\frac{1}{1-1/q_1} +
   (q_1-w_{q_1})\frac{1-(w_{q_1}+1)/q}{(1-w_{q_1}/q_1)(1-1/q_1)} = q_1.
\end{displaymath} 
Now say that~(\ref{Q-sum}) has been proven for $a-1$ and consider the $a$ case
\begin{displaymath}
   \sum_{m_0=1}^{q_1\cdot \ldots \cdot q_a} 
       \prod_{q \leq q_a} f_q(m_0,\ldots,m_{k-1},d).
\end{displaymath}
Group the $m_0$'s according to their values modulo $q_a$
\begin{displaymath}
   \sum_{n_0=1}^{q_a} \sum_{n=0}^{q_1\cdot \ldots \cdot q_{a-1}-1}
        \prod_{q \leq q_a} f_q(nq_a+n_0,m_1,\ldots,m_{k-1},d).
\end{displaymath}
Now, because $f_{q_a}$ only depends on its values modulo $q_a$, the above is
\begin{displaymath}
   \sum_{n_0=1}^{q_a} f_{q_a}(n_0,m_1,\ldots,m_{k-1},d)
   \sum_{n=0}^{q_1\cdot \ldots \cdot q_{a-1}-1}
        \prod_{q \leq q_{a-1}} f_q(nq_a+n_0,m_1,\ldots,m_{k-1},d).
\end{displaymath}
But as $n$ runs from $0$ to $q_1\cdot \ldots \cdot q_{a-1}-1$, $nq_a+n_0$ runs
over the complete set of residues modulo $q_1\cdot \ldots \cdot q_{a-1}$
(because $q_a$ is relatively prime to $q_1\cdot \ldots \cdot q_{a-1}$).
Hence the inner sum is, by our induction hypothesis, equal to 
$q_1\cdot \ldots \cdot q_{a-1}$, so the above is 
\begin{displaymath}
   q_1\cdot \ldots \cdot q_{a-1}
   \sum_{n_0=1}^{q_a} f_{q_a}(n_0,m_1,\ldots,m_{k-1},d)
   = q_1\cdot \ldots \cdot q_{a-1} q_a = Q.
\end{displaymath}
\end{pf}

%xxx Note to myself: the weakness in the above proof
%lies between equations (\ref{S}) and (\ref{almost-there}). We could
%do better with summation by parts, but to get a siginificant
%improvement (i.e. the truth) we need to get a grip on the errors as we 
%do in Corollary 1. This is hard because of 'partial tuples'.

\begin{rems}
In~\cite{Gallagher}, Gallagher studied the combinatorics of a related
problem, essentially that of the asymptotics of the sum
$\sum_{d \leq M} A_{d,k}$. His method can be adapted for our
problem (with messier combinatorics).
The remainder
term obtained grows very quickly with $k$ (though for small $k$, his
method provides a stronger result). On the other hand,
Theorem~\ref{T:ratios} can be 
used, along with Corollary~\ref{cor_1} below and summation by parts, 
to obtain the asymptotics of $\sum_{d \leq M} A_{d,k}$ (though, they 
are not needed for the Champions problem). 
\end{rems}

To establish Corollary~\ref{cor_1} we first 
give a general counting formula which is useful for averaging
certain types of products.
\begin{theorem}
   \label{T:sieve}
   Let $S:=\{a\}$ be a set of pairwise relatively prime positive integers,
   and let $f$ be a complex valued function on this set.
   Then
   \begin{displaymath}
       \sum_{d=1}^{M} \prod\limits_{{a|d} \atop {a \in S}} f(a) = 
       M \prod\limits_{{a \leq M} \atop {a \in S}}
                          \left(
                              1 + \frac{1}{a}(f(a)-1)
                          \right)
       - \sum_{\sigma} \left\{
                           \frac{M}{\prod_{a \in \sigma} a}
                       \right\}
                       \prod_{a \in \sigma}(f(a)-1)
   \end{displaymath}
   where $\sigma$ ranges over all finite non-empty subsets of $S$
   whose elements are all $\leq M$, and where 
   $\{x\}=x-\lfloor x \rfloor$ denotes the fractional part of x.
   Empty products are taken to be 1.
\end{theorem}
This formula can be derived using an inclusion-exclusion argument as 
in the sieve of Eratosthenes.

In particular
\begin{cor}
  \label{cor_1}
  \begin{displaymath}
      \sum_{d=1}^{M} A_{d,1} = 2M\prod_{q>M}\frac{q(q-2)}{(q-1)^2}
      -A_{1,1} \sum_{i=1}^{\pi(M)-1} 
               \sum_{q_1<\ldots<q_i \leq M} 
               \left\{\frac{M}{q_1 \ldots q_i}\right\} \frac{1}{(q_1-2)
                               \ldots (q_i-2)}.
  \end{displaymath}
This implies
  \begin{displaymath}
      \sum_{d=1}^{M} A_{d,1} = 2M + O(\log M).
  \end{displaymath}
\end{cor}
The first part of the corollary follows from Theorem \ref{T:sieve},
(\ref{A_d_k}), and (\ref{2-tuple}).

The second part follows by noting that
\begin{displaymath}
   \prod_{q>M} \frac{q(q-2)}{(q-1)^2} = 1 + O(M^{-1}),
\end{displaymath}
and
\begin{displaymath}
   0 \leq
         \sum_{i=1}^{\pi(M)-1} \sum_{q_1<\ldots<q_i \leq M}
         \left\{\frac{M}{q_1 \ldots q_i}\right\} \frac{1}{(q_1-2) \ldots (q_i-2)}
     < \prod_{q \leq M} \left( 1 + \frac{1}{q-2} \right)
     = O(\log{M}).
\end{displaymath}

The above Corollary was also proven in~\cite[page 10]{Bombieri} but with
$O(\log^2(M))$ instead of $O(\log M)$ for the remainder, and, with
the correct remainder, in~\cite[Lemma 17.4]{Montgomery}.
%*******************************************************************
\section{Tables and Graphs}

\begin{table}[p]
\begin{center}
\begin{tabular}{c|c||c|c}
$x$ & Champions for $x$ & $x$ & Champions for $x$ \\ \hline 
            5   &       1           2&
          421   &       2           6\\
            7   &       2&
          431   &       2           6\\
           11   &       2&
          433   &       2\\
          $\vdots$&$\vdots$&
          439   &       2           6\\
           97   &       2&
          443   &       2           6\\
          101   &       2           4&
          449   &       6\\
          103   &       2&
          457   &       6\\
          107   &       2           4&
          461   &       6\\
          109   &       2&
          463   &       2           6\\
          113   &       2           4&
          467   &       2           4           6\\
          127   &       2           4&
          479   &       2           4           6\\
          131   &       4&
          487   &       2           4           6\\
          137   &       4&
          491   &       4\\
          139   &       2           4&
          $\vdots$&$\vdots$\\
          149   &       2           4&
          541   &       4\\
          151   &       2&
          547   &       4           6\\
          157   &       2&
          557   &       4           6\\
          163   &       2&
          563   &       6\\
          167   &       2           4&
          $\vdots$&$\vdots$\\
          173   &       2           4&
          937   &       6\\
          179   &       2           4           6&
          941   &       4           6\\
          181   &       2&
          947   &       6\\
          $\vdots$&$\vdots$&
          953   &       6\\
          373   &       2&
          967   &       6\\
          379   &       2           6&
          971   &       6\\
          383   &       2           6&
          977   &       6\\
          389   &       6&
          983   &       6\\
          397   &       6&
          $\vdots$   & $\vdots$  \\
          401   &       6&
         $1.7427\cdot10^{35}$ &  ? 30 ? \\
          409   &       6&
          $\vdots$   & $\vdots$  \\
          419   &       6&   
         $10^{425}$ &  ? 210 ? \\
\hline
\end{tabular}
\end{center}
\caption{Champions for small $x$}
\label{initial-champions}
\end{table}


\begin{figure}[p]
\centerline{
\hspace{-1in}
\rotatebox{270}{
\psfig{file=fig1a.ps,width=4.5in}
}}
\caption{$x$ v.s. $N(x,d)\log^2(x)/x$, for $2d=2,4,\ldots$ (only $2d \leq 6$ are labeled).
The $x$ axis is on a logarithmic scale.
The picture shows $6$ dominating as Champion for $x>941$, presumably until roughly
$x=1.7427\cdot10^{35}$.  The two lines in bold are for $2d=6$ and
$2d=30$, with only the former labeled, and the latter rising in the
lower right-hand corner.
The $\log^2(x)/x$ factor was included for graphing purposes.}
\label{fig-initial-champions}
\end{figure}

\begin{figure}[p]
\centerline{
\hspace{-1in}
\rotatebox{270}{
\psfig{file=fig2.ps,width=5.5in}
}}
\caption{A plot showing the dependence of $N(x,d)$ (vertical axis) on $2d$ (horizontal
axis), at $x=2^{20},2^{22},\ldots,2^{44}$. The values of $N(x,d)$ are represented by
small circles. Note that the vertical axis is on a logarithmic scale. 
Integrating~(\ref{N-asymptotics2}) by parts, and taking logarithms, we see that,
for fixed $x$, $\log{N(x,d)}$ should follow a straight line (with respect to $d$)
with small pertubations of size $\log{A_{d,1}}$. Both these traits (linearity and
pertubations) can be seen in the above figure. Notice, at $2d=210$, a prominent pertubation
which reflects the relatively large size of $A_{105,1}$.}
\label{irregular-regular}
\end{figure}



\begin{figure}[p]
\centerline{\psfig{file=fig3.ps,width=6.5in}}
\caption{A figure substantiating the remark made following~(\ref{recursion}). Here
we have drawn the graph of $d$ vs 
$\left(\frac{1}{k}+\frac{1}{2d}\frac{A_{d,k+1}}{A_{d,k}} \right)\frac{d}{\log{d}}$,
for $k=1,2,3$ (there are 3 graphs superimposed in the above figure). According to the
remark, these graphs should all be bounded. This picture not only shows them 
to be bounded, but suggests that they fluctuate about some constant value.
For fixed $d$, as $k$ varies, the fluctuations seem to be proportional to $1/k$.}
\label{fig_A_d_k}
\end{figure}

\begin{table}[p]
{\scriptsize
\begin{center}
\begin{tabular}{c||c|c|c||c||c|c|c||}
$d$ & $N(10^{12},d)$ & (\ref{N-asymptotics}) with $M=4$ &
(\ref{N-asymptotics2}) &$d$ & $N(10^{12},d)$ 
& (\ref{N-asymptotics}) with $M=4$ & (\ref{N-asymptotics2}) \\ \hline \hline
1  &1870585221 & 1870559866. & 1734571973. &
26 & 299020127 & 19357608. & 287761502. \\
2  &1870585458 & 1870559866. & 1608489045. &
27 & 511589763 & -117485659.&  489342519. \\
3  &3435528229 & 3435458600. & 2983176210. &
28 & 276101593 & -190236598.&  272337270. \\
4  &1573331564 & 1573293311. & 1383199071.&
29 & 238482555 & -159446866.&  218306665. \\
5  &2052293026 & 2052377278. & 1710267841. &
30 & 521616486 & -872270696.&  520705710. \\
6  &2753597777 & 2753698149. & 2379035785. &
31 & 173395125 & -542475987.&  187370709. \\
7  &1556469349 & 1556538305. & 1323739864.&
32 & 174696822 & -466395227.&  168010801. \\
8  &1202533145 & 1202481778. & 1023002316.&
33 & 337881160 & -1472349367.&  346327794. \\
9  &2246576317 & 2246300116. & 1897433561.&
34 & 144475047 & -901708546.&  154203810. \\
10 & 1298682892&  1297504207.&  1173113388.&
35 & 209257685 & -1446734637.&  214563934. \\
11 & 1105634145&  1104842257.&  906625819.&
36 & 225244356 & -2345640221.&  248794573. \\
12 & 1754011594&  1748689938.&  1513472556.&
37 & 112410088 & -1279821387.&  118692508. \\
13 & 866077378 & 860228350. & 765617165.&
38 & 103953673 & -1562442677.&  113342851. \\
14 & 946685406 & 940272873. & 781065469.&
39 & 202872036 & -3480363786.&  216657899. \\
15 & 1803413614&  1768917778.&  1609765148.&
40 & 109107891 & -2536053455.&  122824166. \\
16 & 596278790 & 571983719. & 559868265. &
41 & 79287666  &-2097549341. & 87646234. \\
17 & 629634308 & 602935653. & 553874113. &
42 & 169541709 & -5569989899.&  190259148. \\
18 & 1069300358&  994461819.&  963192792.&
43 & 63992940  &-2740157702. & 75335519. \\
19 & 520188423 & 469051756. & 472946539.&
44 & 67022921  &-3106662564. & 75804586. \\
20 & 626694626 & 549365467. & 552378496.&
45 & 141957467 & -8653244845.&  168777258. \\
21 & 979052296 & 757589403. & 922195739.&
46 & 49878328  &-3851360864. & 61511925. \\
22 & 414087760 & 277381704. & 395992947.&
47 & 46375798  &-3982359526. & 55682088. \\
23 & 366906343 & 217998577. & 346302520.&
48 & 83989444  &-8412724248. & 101068993. \\
24 & 651790197 & 305395231. & 613209321.&
49 & 45681754  &-5553974513. & 56258792. \\
25 & 386726111 & 71637118. & 379182356.&
50 & 48416676  &-6460114606. & 57992596. \\
\hline
\end{tabular}
\end{center}
}
\caption{A comparison of two different estimates for $N(x,d)$. Here we
have chosen $x=10^{12}$. The first estimate was computed 
using~(\ref{N-asymptotics}) with $M=4$. The second estimate was computed
using~(\ref{N-asymptotics2}). The table shows that the higher terms
in~(\ref{N-asymptotics}) are important for estimating $N(x,d)$ if
$d$ is allowed to grow (notice that the middle column gives a good
approximation roughly up to $d=18$). This is a fact that Brent observes 
in~\protect\cite{Brent} . His computations also show that taking all the terms
in~(\ref{N-asymptotics}) gives numbers that agree very well with
$N(x,d)$. This is what~(\ref{N-asymptotics2}) attempts to do
(in closed form). However, $d$ needs to be large for~(\ref{N-asymptotics2})
to be a good approximation and $x$ has to be large compared to $d$
(though, even for small $d$ and $x$ not too huge, the table reveals 
that~(\ref{N-asymptotics2}) gives a decent, uniform approximation
to $N(x,d)$).}
\label{N_x_d}
\end{table}

%xxx Note: at 10^12 Brent's formula predicts: 1803390042.66 gaps of size 2d=30
%which agrees to within sqrt(x) with our table.


\begin{landscape}
\begin{table}[p]
{\tiny
\vspace{-1in}
\begin{center}
\begin{tabular}{c||c|c|c|c|||c||c|c|c|c|||c||c|c|c|c||}
$2d$ & $g_{2d}(30)$ & $g_{2d}(40)$ & $g_{2d}(400)$ & $g_{2d}(450)$ &
$2d$ & $g_{2d}(30)$ & $g_{2d}(40)$ & $g_{2d}(400)$ & $g_{2d}(450)$ &
$2d$ & $g_{2d}(30)$ & $g_{2d}(40)$ & $g_{2d}(400)$ & $g_{2d}(450)$  \\ \hline
2 & 2769 & 1539 & 25 & 11 & 82 & 932 & 654 & 12 & 12 & 162 & 509 & 582 & 27 & 16 \\ \hline 
4 & 2772 & 1473 & 20 & 29 & 84 & 1982 & 1582 & 44 & 20 & 164 & 264 & 297 & 16 & 13 \\ \hline 
6 & 5278 & 3120 & 32 & 26 & 86 & 882 & 674 & 18 & 12 & 166 & 252 & 247 & 11 & 15 \\ \hline 
8 & 2630 & 1520 & 17 & 13 & 88 & 835 & 652 & 12 & 8 & 168 & 619 & 622 & 44 & 24 \\ \hline 
10 & 3462 & 1998 & 15 & 19 & 90 & 2119 & 1664 & 49 & 29 & 170 & 328 & 389 & 8 & 8 \\ \hline 
12 & 5016 & 2761 & 37 & 28 & 92 & 769 & 634 & 13 & 11 & 172 & 247 & 235 & 13 & 12 \\ \hline 
14 & 2900 & 1644 & 19 & 18 & 94 & 813 & 609 & 12 & 12 & 174 & 466 & 550 & 28 & 25 \\ \hline 
16 & 2392 & 1397 & 20 & 13 & 96 & 1452 & 1101 & 19 & 22 & 176 & 242 & 239 & 17 & 11 \\ \hline 
18 & 4578 & 2681 & 27 & 17 & 98 & 804 & 648 & 25 & 14 & 178 & 225 & 233 & 9 & 15 \\ \hline 
20 & 2866 & 1760 & 23 & 11 & 100 & 916 & 706 & 27 & 16 & 180 & 526 & 641 & 27 & 26 \\ \hline 
22 & 2450 & 1460 & 14 & 22 & 102 & 1392 & 1118 & 27 & 18 & 182 & 255 & 273 & 20 & 16 \\ \hline 
24 & 4305 & 2544 & 25 & 24 & 104 & 692 & 559 & 10 & 9 & 184 & 205 & 211 & 10 & 7 \\ \hline 
26 & 2241 & 1315 & 23 & 12 & 106 & 672 & 532 & 21 & 9 & 186 & 372 & 386 & 29 & 19 \\ \hline 
28 & 2410 & 1472 & 21 & 10 & 108 & 1207 & 1047 & 33 & 15 & 188 & 180 & 206 & 11 & 10 \\ \hline 
30 & 5060 & 3209 & 50 & 26 & 110 & 884 & 705 & 18 & 21 & 190 & 240 & 279 & 13 & 16 \\ \hline 
32 & 1828 & 1217 & 17 & 13 & 112 & 707 & 631 & 15 & 19 & 192 & 342 & 413 & 22 & 16 \\ \hline 
34 & 1938 & 1257 & 18 & 9 & 114 & 1145 & 967 & 24 & 15 & 194 & 161 & 186 & 11 & 10 \\ \hline 
36 & 3518 & 2268 & 19 & 22 & 116 & 567 & 432 & 16 & 14 & 196 & 215 & 243 & 13 & 9 \\ \hline 
38 & 1758 & 1129 & 17 & 15 & 118 & 512 & 471 & 22 & 4 & 198 & 323 & 423 & 33 & 40 \\ \hline 
40 & 2260 & 1397 & 20 & 19 & 120 & 1285 & 1162 & 40 & 30 & 200 & 207 & 234 & 13 & 16 \\ \hline 
42 & 3718 & 2536 & 25 & 24 & 122 & 447 & 439 & 17 & 12 & 202 & 130 & 154 & 7 & 6 \\ \hline 
44 & 1798 & 1124 & 13 & 13 & 124 & 463 & 436 & 13 & 5 & 204 & 305 & 354 & 36 & 21 \\ \hline 
46 & 1655 & 1066 & 6 & 14 & 126 & 1051 & 1011 & 28 & 22 & 206 & 151 & 170 & 12 & 5 \\ \hline 
48 & 2919 & 1974 & 32 & 21 & 128 & 466 & 408 & 8 & 6 & 208 & 152 & 190 & 11 & 16 \\ \hline 
50 & 1968 & 1255 & 18 & 12 & 130 & 647 & 595 & 14 & 17 & 210 & 438 & 512 & 33 & 34 \\ \hline 
52 & 1475 & 1068 & 19 & 9 & 132 & 892 & 831 & 25 & 23 & 212 & 112 & 159 & 8 & 7 \\ \hline 
54 & 2748 & 1826 & 23 & 21 & 134 & 380 & 367 & 11 & 10 & 214 & 121 & 155 & 14 & 12 \\ \hline 
56 & 1557 & 1051 & 18 & 14 & 136 & 406 & 361 & 10 & 15 & 216 & 212 & 301 & 27 & 25 \\ \hline 
58 & 1312 & 924 & 11 & 11 & 138 & 765 & 802 & 18 & 16 & 218 & 99 & 149 & 10 & 6 \\ \hline 
60 & 3305 & 2269 & 38 & 30 & 140 & 598 & 543 & 19 & 17 & 220 & 173 & 208 & 24 & 14 \\ \hline 
62 & 1270 & 825 & 15 & 8 & 142 & 369 & 345 & 10 & 8 & 222 & 222 & 300 & 14 & 24 \\ \hline 
64 & 1214 & 863 & 13 & 8 & 144 & 662 & 664 & 32 & 16 & 224 & 139 & 156 & 14 & 14 \\ \hline 
66 & 2588 & 1739 & 29 & 17 & 146 & 333 & 318 & 9 & 9 & 226 & 113 & 131 & 11 & 11 \\ \hline 
68 & 1107 & 816 & 8 & 14 & 148 & 336 & 361 & 15 & 15 & 228 & 216 & 292 & 28 & 27 \\ \hline 
70 & 1658 & 1231 & 21 & 18 & 150 & 876 & 833 & 37 & 29 & 230 & 129 & 169 & 19 & 11 \\ \hline 
72 & 2008 & 1456 & 25 & 25 & 152 & 311 & 332 & 15 & 15 & 232 & 95 & 103 & 15 & 4 \\ \hline 
74 & 984 & 785 & 14 & 13 & 154 & 398 & 418 & 20 & 13 & 234 & 184 & 251 & 20 & 20 \\ \hline 
76 & 1036 & 777 & 13 & 8 & 156 & 650 & 629 & 26 & 23 & 236 & 87 & 116 & 14 & 15 \\ \hline 
78 & 2130 & 1588 & 28 & 25 & 158 & 286 & 302 & 10 & 12 & 238 & 97 & 160 & 14 & 10 \\ \hline 
80 & 1238 & 940 & 25 & 15 & 160 & 364 & 369 & 17 & 12 & 240 & 211 & 276 & 33 & 23 \\ \hline 
\end{tabular}
\end{center}
}
\caption{A table showing the number of gaps of size $2 \leq 2d \leq 240$ in the intervals
$[10^{u},10^{u}+10^{7}]$, $u=30,40,400,450$. Here 
$g_{2d}(u)=$"$N(10^{u}+10^{7},d)-N(10^{u},d)$" (in quotes, since Maple's
{\em probable} prime function was used to generate this table). Note that, when $u=30$,
$g_{6}(30)=5278$ dominates $g_{30}(30)=5060$, but that $g_{30}(40)=3209$ beats $g_{6}(40)=3120$.
Furthermore, $g_{30}(400)=50$, $g_{210}(400)=33$, but $g_{30}(450)=26$, $g_{210}(450)=34$.
These numbers are consistent with our predictions that 30 begins to beat 6 as Champion
near $x=10^{35}$, and that 210 first beats 30 near $x=10^{425}$. Note, however, that,
at $x=10^{450}$, the apparent Champion seems to be $2d=198$ which shows up 40 times!
Such are the dangers of working with small samples.
}
\label{transitions}
\end{table}

\end{landscape}

%****************************************************************************
\begin{thebibliography}{9}

\bibitem{Bombieri} E. Bombieri and H. Davenport: Small differences
between prime numbers, {\em Proc. Royal Soc.} {\bf A293} (1966), 1--18

\bibitem{Brent} R. P. Brent: The distribution of small gaps between succesive 
primes, {\em Math. Comp.} {\bf 28} (1974), 315--324.

\bibitem{Brent2}  R. P. Brent: Irregularities in the distribution of primes 
and twin primes, {\em Math. Comp.} {\bf 29} (1975), 43--56.

\bibitem{ES} P. \Erdos and E. G. Straus: Remarks on the differences between
consecutive primes, {\em Elem. Math} {\bf 35} (1980), 115--118.

\bibitem{Gallagher} P. X. Gallagher: On the distribution of primes in
short intervals, {\em Mathematika} {\bf 23} (1976), 4--9.

\bibitem{Gallagher_2} P. X. Gallagher: Corrigendum to distribution of primes in
short intervals, {\em Mathematika} {\bf 28} (1981), 86.

\bibitem{Guy} R. K. Guy: {\em Unsolved Problems in Number Theory}, 2nd ed., Springer-Verlag, 1994.

\bibitem{Harley}  R. Harley: Some estimates by Richard Brent applied to
the ``high jumpers'' problem, unpublished manuscript, available at
$\langle$http://pauillac.inria.fr/$\sim$harley/wnt.html$\rangle$.

\bibitem{HL} G. H. Hardy and J. E. Littlewood: Some problems of 'partitio 
numerorum': III: On the expression of a number as a sum of primes, 
{\em Acta Math.} 44 (1922), 1-70.  
Reprinted in {\em Collected Papers of G. H. Hardy,}
vol. 1, pp. 561-630, Oxford Univ. Press, 1966.

\bibitem{HR} H. Halberstam and H. -E. Richert: {\em Sieve Methods}, Academic Press 1974. 

\bibitem{Ingham} A. E. Ingham: {\em The Distribution of Prime Numbers}, 
Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1990, Reprint of the 
1932 original, With a foreword by R. C.  Vaughan.

\bibitem{Montgomery}  H.L. Montgomery: {\em Topics in
Multiplicative Number Theory}, Lecture Notes in Mathematics {\bf 227},
Springer-Verlag, 1971.

\bibitem{Nelson} H. Nelson: Problem 654, {\em J. Rec. Math.} {\bf 11} (1978-79), 231. 

\end{thebibliography}

\end{document}