%------------------------------------------------------------------------------
% Beginning of gaps3h.tex
%
% AMS-LaTeX2e source file for the manuscript
%
% ``New prime gaps between 10^15 and 5*10^16'',
%
% originally titled
%
% ``First Occurrence Prime Gaps in 10^15 < p < 5*10^16'',
%
% by Bertil Nyman and Thomas R. Nicely.
%
% Original submission 10 February 2003 to Journal of Integer Sequences.
%
% This revision submitted 13 August 2003 to Journal of Integer Sequences.
%
%------------------------------------------------------------------------------
\documentclass[12pt,reqno]{amsart}
\usepackage[usenames]{color}
\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{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}
% \tolerance=250
\renewcommand{\,}{\hskip.03em\relax}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{xca}[theorem]{Exercise}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\abs}[1]{\lvert#1\rvert}
\newcommand{\ul}{\underbar}
\newcommand{\blankbox}[2]{%
\parbox{\columnwidth}{\centering
\setlength{\fboxsep}{0pt}%
\fbox{\raisebox{0pt}[#2]{\hspace{#1}}}%
}%
}
\def\NNB{1.598508912\times10^{15}}
\def\CFKO{10884}
\def\GFKO{233822}
\def\NV{4.5\times10^{15}}
\def\TILDE{\raise0.5ex\hbox{$\sim$}}
\def\tmark{\tiny\raise1.5ex\hbox{T\kern-0.1em{M}}\normalsize}
\def\rmark{\raise1.3ex\hbox{\tiny\kern0.2em{R}%
\kern-0.92em\scriptsize\mathhexbox20D}\normalsize}
\def\cplusplus{{C}\raise0.4ex\hbox{\tiny{++}}\normalsize}
\def\A{\approx}
\def\S{\slash}
\def\D{\ddag}
\DeclareMathOperator{\Li}{Li}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\begin{center}
\vskip 1cm {\LARGE\bf New prime gaps between $\bf 10^{15}$ and $\bf 5\times10^{16}$}
\vskip 1cm
\large
Bertil Nyman\\
SaabTech Systems AB \\
Uppsala \\
Sweden \\
\href{mailto:bertil.nyman@saabtech.se}{\tt bertil.nyman@saabtech.se}\\
\ \\
Thomas R. Nicely\footnote[1]{Corresponding author.}\\
1113 Dandridge Drive \\
Lynchburg, VA 24501-2231 \\
USA\\
\href{mailto:trnicely@hotmail.com}{\tt trnicely@hotmail.com}\\
\href{http://www.trnicely.net}{\tt http://www.trnicely.net}\\
\end{center}
\vskip .2 in
\begin{center}
{\bf Abstract}
\end{center}
The interval from $10^{15}$ to $5\times10^{16}$ was searched for first
occurrence prime gaps and maximal prime gaps. One hundred and twenty-two
new first occurrences were found, including four new maximal gaps,
leaving $1048$ as the smallest gap whose first occurrence remains uncertain.
The first occurrence of any prime gap of $1000$ or greater was found
to be the maximal gap of $1132$ following the prime $1693182318746371$.
A maximal gap of $1184$ follows the prime $43841547845541059$. More
extensive tables of prime gaps are maintained at
\href{http://www.trnicely.net}{\tt http://www.trnicely.net}.
\smallskip
\section{Introduction}
We restrict our discussion to the positive integers. Let $Q$ denote
the sequence of prime numbers,
$Q = \{2,3,5,7,11,\ldots,q_k,q_{k+1},\ldots\}$, and $D$ the
sequence of differences of consecutive prime numbers,
$D = \{1,2,2,4,\ldots,q_{k+1}-q_k,\ldots\}$.
A {\it prime gap} $G$ is the interval bounded by two consecutive prime
numbers $q_k$ and $q_{k+1}$. The {\it measure} (size, magnitude) $g$
of a prime gap $G$ is the difference $g=q_{k+1}-q_k$ of its bounding primes.
A prime gap is often specified by its measure $g$ and its initial prime
$p_1=q_k$, and less often by the measure $g$ and the terminal prime
$p_2=q_{k+1}$. A prime gap of measure $g$ contains $g-1$ consecutive
composite integers. The measures of the prime gaps are the successive
elements of the sequence $D$. Since $2$ is the only even prime, every
prime gap is of even measure, with the sole exception of the prime gap of
measure $1$ following the prime $2$.
In illustration, a gap of measure $g=6$ (or simply a gap of $6$) follows
the prime $p_1=23$, while a gap of $10$ follows the prime $139$.
It is elementary that gaps of arbitrarily large measure exist, since,
as observed by Lucas \cite{Lu}, for $n > 0$ the integer $(n+1)! + 1$ must
be followed by at least $n$ consecutive composites, divisible successively
by $2, 3, \ldots, n+1$; however, $n+1$ represents only a lower bound on
the measure of such gaps.
The {\it merit} $M$ of a prime gap of measure $g$ following the prime
$p_1$ is defined as $M=g/\ln(p_1)$. It is the ratio of the measure
of the gap to the ``average'' measure of gaps near that point; as a
consequence of the Prime Number Theorem, the average difference between
consecutive primes near $x$ is approximately $\ln(x)$.
A prime gap of measure $g$ is considered a {\it first occurrence prime
gap} when no smaller consecutive primes differ by exactly $g$, i.e., when
this is the first appearance of the positive integer $g$ in the sequence
$D$. Thus, the gap of $4$ following $7$ is a first occurrence, while
the gap of $4$ following $13$ is not. Note that this usage of the
compound adjective {\it first occurrence} carries no implication whatsoever
regarding historical precedence of discovery. Multiple instances of gaps
of $1048$ are known, but none is yet known to be a first occurrence, even
though one of them bears an earliest historical date of discovery. This
terminology follows that of Young and Potler \cite{YP}, and produces more
concise phrasing than some past and present alternative nomenclature.
A prime gap of measure $g$ is titled {\it maximal} if it strictly exceeds
all preceding gaps, i.e., the difference between any two consecutive
smaller primes is $\, < g$, so that $g$ exceeds all preceding elements of
$D$. Thus the gap of $6$ following the prime $23$ is a maximal prime gap,
since each and every smaller prime is followed by a gap less than $6$
in measure; but the gap of $10$ following the prime $139$, while a first
occurrence, is not maximal, since a larger gap (the gap of $14$ following
the prime $113$) precedes it in the sequence of integers. Maximal prime
gaps are {\it ipso facto} first occurrence prime gaps as well.
Furthermore, the term {\it first known occurrence prime gap} is used to
denote a prime gap of measure $g$ which has not yet been proven to be
(and may or may not be) the true first occurrence of a gap of measure
$g$; this situation arises from an incomplete knowledge of the gaps (and
primes) below the first known occurrence. Thus, Nyman discovered a
gap of $1048$ following the prime $88089672331629091$, and no smaller
instance is known; but since his exhaustive scan extended only to
$5\times10^{16}$, this gap remains for the moment merely a first
known occurrence, not a first occurrence. First known occurrences serve
as upper bounds for first occurrences not yet established.
The search for first occurrence and maximal prime gaps was previously
extended to $10^{15}$ by the works of Glaisher \cite{Gl},
Western \cite{We}, Lehmer \cite{Le}, Appel and Rosser \cite{AR}, Lander
and Parkin \cite{LP}, Brent \cite{Br73,Br80}, Young and Potler \cite{YP},
and Nicely \cite{Ni99}. The present work extends this upper bound to
$5\times10^{16}$. The calculations are currently being continued beyond
$5\times10^{16}$ by Tom\'as Oliveira e Silva \cite{Silva}, as part of a
project generating numerical evidence for the Goldbach conjecture.
\section{Computational Technique}
The calculations were carried out over a period of years,
distributed asynchronously among numerous personal computers,
taking advantage of otherwise idle CPU time. Nyman
accomplished the bulk of the computations; employing as many
as eighty systems from 1998 to 2002, he accounted for the
survey of the region from $\NNB$ through
$5\times10^{16}$. Nicely's enumerations of prime gaps began in
the summer of 1995, but the portion reported here was
carried out from 1997 to 1999, over the interval from
$10^{15}$ to $\NNB$, the number of systems in use
varying from about five to twenty-five. The algorithms employed
the classic sieve of Eratosthenes, with the addition of a few
speed enhancing optimizations, to carry out an exhaustive
generation and analysis of the differences between consecutive
primes. More sophisticated techniques for locating large prime
gaps, such as scanning through arithmetic progressions, were
rendered impractical by the fact that the search for first
occurrences was being carried out concurrently with other tasks;
Nicely was enumerating prime constellations, while Nyman was gathering
comprehensive statistics on the frequency distribution of prime gaps.
Among the measures taken to guard against errors (whether
originating in logic, software, or hardware), the count $\pi(x)$
of primes was maintained and checked periodically against known
values, such as those published by Riesel \cite{Ri94}, and
especially the extensive values computed recently by Silva
\cite{Silva}. In addition, Nicely has since duplicated Nyman's
results through $\NV$.
\section{Computational Results}
Table \ref{Table1} lists the newly discovered first occurrence prime
gaps resulting from the present study; maximal gaps are indicated by
a double dagger (\D). Each table entry shows the measure $g$ of the
gap and the initial prime $p_1$. The fifteen gaps between $10^{15}$
and $\NNB$ are due to Nicely; all the rest were discovered by Nyman.
\begin{table}[ht]
\label{Table1}
\begin{center}
\vskip 1pc
\begin{small}
\begin{tabular}{||r|r||r|r||r|r||}
\hline
Gap&Following the prime&Gap&Following the prime&Gap&Following the prime\\
\hline
796& 1271309838631957& 928& 10244316228469423& 1010& 21743496643443551\\
812& 1710270958551941& 930& 3877048405466683& 1012& 22972837749135871\\
824& 1330854031506047& 932& 10676480515967939& 1014& 13206732046682519\\
838& 1384201395984013& 934& 8775815387922523& 1016& 25488154987300883\\
842& 1142191569235289& 936& 2053649128145117& 1018& 37967240836435909\\
846& 1045130023589621& 938& 3945256745730569& 1020& 24873160697653789\\
848& 2537070652896083& 940& 9438544090485889& 1022& 10501301105720969\\
850& 2441387599467679& 942& 10369943471405191& 1024& 22790428875364879\\
852& 1432204101894959& 944& 4698198022874969& 1026& 14337646064564951\\
854& 1361832741886937& 946& 8445899254653313& 1028& 16608210365179331\\
856& 1392892713537313& 948& 5806170698601659& 1030& 21028354658071549\\
858& 1464551007952943& 950& 5000793739812263& 1032& 19449190302424919\\
864& 2298355839009413& 952& 3441724070563411& 1034& 11453766801670289\\
866& 2759317684446707& 954& 8909512917643439& 1036& 36077433695182153\\
868& 1420178764273021& 956& 7664508840731297& 1038& 28269785077311409\\
870& 1598729274799313& 958& 6074186033971933& 1040& 46246848392875127\\
874& 1466977528790023& 960& 5146835719824811& 1042& 33215047653774409\\
876& 1125406185245561& 962& 9492966874626647& 1044& 7123663452896833\\
878& 2705074880971613& 964& 5241451254010087& 1046& 25702173876611591\\
882& 3371055452381147& 966& 5158509484643071& 1050& 13893290219203981\\
884& 1385684246418833& 968& 19124990244992669& 1054& 26014156620917407\\
886& 4127074165753081& 970& 10048813989052669& 1056& 11765987635602143\\
888& 2389167248757889& 972& 4452510040366189& 1058& 28642379760272723\\
890& 3346735005760637& 974& 10773850897499933& 1060& 15114558265244791\\
892& 2606748800671237& 976& 14954841632404033& 1062& 15500910867678727\\
894& 2508853349189969& 978& 12040807275386881& 1064& 43614652195746623\\
896& 3720181237979117& 980& 19403684901755939& 1068& 23900175352205171\\
898& 4198168149492463& 982& 18730085806290949& 1072& 40433690575714297\\
900& 2069461000669981& 984& 11666708491143997& 1074& 33288359939765017\\
902& 1555616198548067& 986& 34847474118974633& 1076& 20931714475256591\\
904& 3182353047511543& 988& 11678629605932719& 1084& 41762363147589283\\
908& 2126985673135679& 990& 2764496039544377& 1098& 25016149672697549\\
910& 1744027311944761& 992& 4941033906441539& 1100& 21475286713974413\\
912& 2819939997576017& 994& 3614455901007619& 1102& 39793570504639117\\
914& 3780822371661509& 996& 14693181579822451& 1106& 29835422457878441\\
\D 916& 1189459969825483& 998& 11813551133888459& 1108& 43986327184963729\\
918& 2406868929767921& 1000& 22439962446379651& 1120& 19182559946240569\\
920& 4020057623095403& 1002& 14595374896200821& 1122& 31068473876462989\\
922& 4286129201882221& 1004& 7548471163197917&\D1132& 1693182318746371\\
\D 924& 1686994940955803& 1006& 37343192296558573&\D1184& 43841547845541059\\
926& 6381944136489827& 1008& 5356763933625179& & \\
\hline
\end{tabular}
\end{small}
\end{center}
\vskip .1in
{\bf Table 1. First occurrence prime gaps between $\bf 10^{15}$
and $\bf 5\times10^{16}$. {\rm $\D$} denotes a maximal gap}
\end{table}
\section{Observations}
As a collateral result of his calculations, Nyman has computed for
the count of twin primes the value $\pi_2(5\times10^{16})=47177404870103$,
the maximum argument for which this function has been evaluated. Nyman
also obtained $\pi(5\times10^{16})=1336094767763971$ for the
corresponding count of primes; this is the largest value of $x$ for
which $\pi(x)$ has been determined by direct enumeration, and confirms
the value previously obtained by Del\'eglise and Rivat \cite{DR}, using
indirect sieving methods. Nyman has also generated frequency tables for
the distribution of all prime gaps below $5\times10^{16}$.
Listings of the $423$ previously known first occurrence prime gaps
(including $61$ maximal gaps), those below $10^{15}$, have been
published collectively by Young and Potler \cite{YP} and Nicely
\cite{Ni99}, and are herein omitted for brevity.
A comprehensive listing of first occurrence and maximal prime
gaps, annotated with additional information, is available at Nicely's
URL. Nicely also maintains at his URL extensive lists of first known
occurrence prime gaps, lying beyond the present upper bound of
exhaustive computation, and discovered mostly by third parties,
notably Harvey Dubner \cite{Du}. These lists exhibit specific gaps
for every even positive integer up to $\CFKO$, as well as for other
scattered even integers up to $\GFKO$; for some of the gaps exceeding
$8000$ in magnitude, the bounding integers have only been proved strong
probable primes (based on multiple Miller's tests).
The largest gap herein established as a first occurrence is the
maximal gap of $1184$ following the prime $43841547845541059$,
discovered $31$ August $2002$ by Nyman. The smallest gap whose first
occurrence remains uncertain is the gap of $1048$.
The maximal gap of $1132$ following the prime $1693182318746371$,
discovered $24$ January $1999$ by Nyman, is the first occurrence of any
``kilogap'', i.e., any gap of measure 1000 or greater. Its maximality
persists throughout an extraordinarily large interval; the succeeding
maximal gap is the gap of $1184$ following the prime $43841547845541059$.
The ratio of the initial primes of these two successive maximal gaps
is $\A 25.89$, far exceeding the previous extreme ratio of $\A 7.20$ for
the maximal gaps of $34$ (following $1327$) and $36$ (following $9551$),
each discovered by Glaisher \cite{Gl} in $1877$. Furthermore, the gap
of $1132$ has the greatest merit ($\A 32.28$) of any known gap; the maximal
gap of $1184$ is the only other one below $5\times10^{16}$ having a merit
of $30$ or greater.
The gap of $1132$ is also of significance to the related conjectures
put forth by Cram\'er \cite{Cr} and Shanks \cite{Sh64}, concerning the
ratio $g/\ln^2(p_1)$. Shanks reasoned that its limit, taken over all
first occurrences, should be 1; Cram\'er argued that the limit superior,
taken over all prime gaps, should be 1. Granville \cite{Gr}, however,
provides evidence that the limit superior is
$\ge 2e^{-\gamma} \A 1.1229$. For the $1132$ gap, the ratio is
$\A 0.9206$, the largest value observed for any $p_1 > 7$,
the previous best being $\A 0.8311$ for the maximal gap of $906$
following the prime $218209405436543$, discovered by Nicely \cite{Ni99}
in February, $1996$.
Several models have been proposed in an attempt to describe the
distribution of first occurrence prime gaps, including efforts by Western
\cite{We}, Cram\'er \cite{Cr}, Shanks \cite{Sh64}, Riesel \cite{Ri94},
Rodriguez \cite{LR}, Silva \cite{Silva}, and Wolf \cite{MW}. We simply
note here Nicely's empirical observation that all first occurrence and
maximal prime gaps below $5\times10^{16}$ obey the following relationship:
\vskip -10pt
\begin{equation}\label{G1}
0.122985\cdot\mskip-2mu\sqrt{g}\cdot\exp{\sqrt{g}} \mskip9mu < \mskip8mu
p_1 \mskip4mu < \mskip8mu 2.096\cdot g\cdot\exp{\sqrt{g}} \quad .
\end{equation}
\vskip 2pt
The validity of \eqref{G1} for {\it all} first occurrence prime gaps
remains a matter of speculation. Among its corollaries would be the
conjecture that every positive even integer represents the difference
of some pair of consecutive primes, as well as a fairly precise estimate
for the answer to the question posed in 1964 by Paul A. Carlson to Daniel
Shanks \cite{Sh64}, to wit, the location of the first occurrence of one
million consecutive composite numbers. The argument $g=1000002$ entered
into \eqref{G1} yields the result
$2.4 \times 10^{436} < \mskip4mu p_1 < \mskip2mu 4.2 \times 10^{440}$,
which is near the middle of Shanks' own estimate of
$10^{300} < \mskip4mu p_1 < \mskip2mu 10^{600}$.
\section{Acknowledgments}
Nyman wishes to thank \hbox{SaabTech} Systems~AB for providing excellent
computing facilities.
\bibliographystyle{amsplain}
\begin{thebibliography}{29}
\bibitem {AR} Kenneth I. Appel and J. Barkley Rosser,
Table for estimating functions of primes, IDA-CRD
Technical Report Number 4 (1961). Reviewed in
RMT \textbf{55}, \textit{Math. Comp.} \textbf{16} (1962), 500--501.
\bibitem {Br73} Richard P. Brent, The first occurrence of large
gaps between successive primes, \textit{Math. Comp.} \textbf{27} (1973),
959--963. MR \textbf{48\#}8360.
\bibitem {Br80} Richard P. Brent, The first occurrence of certain
large prime gaps, \textit{Math. Comp.} \textbf{35} (1980),
1435--36. MR \textbf{81g:}10002.
\bibitem {Cr} Harald Cram\'er, On the order of magnitude of the
difference between consecutive prime numbers, \textit{Acta Arith.}
\textbf{2} (1936), 23--46.
\bibitem {DR} Marc Del\'eglise and Jo\"el Rivat, Computing $\pi(x)$:
the Meissel, Lehmer, Lagarias, Miller, Odlyzko method,
\textit{Math. Comp.} \textbf{65} (1996), 235--245. MR \textbf{96d:}11139.
\bibitem {Du} Harvey Dubner, e-mail communications to Nicely (1995--2003).
\bibitem {Gl} J. W. L. Glaisher, On long successions of composite
numbers, \textit{Messenger of Mathematics} \textbf{7} (1877), 102--106,
171--176.
\bibitem {Gr} Andrew Granville, Unexpected irregularities in the
distribution of prime numbers, in \textit{Proceedings of the
International Congress of Mathematicians, Vol. I (Z\"urich, 1994)},
Birkh\"auser, Basel, 1995, pp. 388--399. MR \textbf{97d:}11139.
\bibitem {LP} L. J. Lander and Thomas R. Parkin, On first
appearance of prime differences, \textit{Math. Comp.} \textbf{21} (1967),
483--488. MR \textbf{37\#}6237.
\bibitem {Le} Derrick Henry Lehmer, Tables concerning the distribution
of primes up to 37 millions (1957). Copy deposited in the UMT file
and reviewed in \textit{MTAC} \textbf{13} (1959), 56--57.
\bibitem {Lu} Fran\c{c}ois \'Edouard Anatole Lucas,
\textit{Th\'eorie des Nombres}, Vol. 1, Gauthier-Villars, Paris,
1891, p. 360. Reprinted by A. Blanchard, Paris, 1961.
MR \textbf{23\#}A828.
\bibitem {Ni99} Thomas R. Nicely, New maximal prime gaps and first
occurrences, \textit{Math. Comp.} \textbf{68} (July, 1999), 1311--1315.
MR \textbf{99i:}11004.
\bibitem {Rib} Paulo Ribenboim, \textit{The New Book of Prime Number
Records}, 3rd ed., Springer-Verlag, New York, 1996, pp. 248--258.
MR \textbf{96k:}11112.
\bibitem {Ri94} Hans Riesel, \textit{Prime Numbers and Computer Methods
for Factorization}, 2nd ed., Birkh\"auser, Boston, 1994, pp. 78--82,
380--383. MR \textbf{95h:}11142.
\bibitem {LR} Luis Rodriguez (AKA Luis Rodriguez Abreu/Torres), e-mail
communications to Nicely (15--18 January 1999).
\bibitem {Sh64} Daniel Shanks, On maximal gaps between successive
primes, \textit{Math. Comp.} \textbf{18} (1964), 646--651.
MR \textbf{29\#}4745.
\bibitem{Silva} Tom\'as Oliveira e Silva, electronic documents
available (August, 2003) at
\href{http://www.ieeta.pt/~tos/hobbies.html}{\tt http:/{\S}www.ieeta.pt{\S}{\TILDE}tos{\S}hobbies.html}.
\bibitem {We} A. E. Western, Note on the magnitude of the
difference between successive primes, \textit{J. London Math. Soc.}
\textbf{9} (1934), 276--278.
\bibitem {MW} Marek Wolf, First occurrence of a given gap between
consecutive primes, preprint (April, 1997). Available (August, 2003)
at \href{http://www.ift.uni.wroc.pl/~mwolf}{\tt http:/{\S}www.ift.uni.wroc.pl{\S}{\TILDE}mwolf}.
\bibitem {YP} Jeff Young and Aaron Potler, First occurrence prime
gaps, \textit{Math. Comp.} \textbf{52} (1989), 221--224.
MR \textbf{89f:}11019.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11A41; Secondary 11-04, 11Y55.
\noindent \emph{Keywords:} Prime gaps, maximal gaps, first occurrences,
prime numbers, kilogaps, maximal prime gaps.
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received February 10, 2003;
revised version received August 13, 2003.
Published in {\it Journal of Integer Sequences},
August 13, 2003.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.
\vskip .1in
\end{document}