<none>

[N. J. A. Sloane]

Here is a preprint from Richard Guy that i think will be
of great interest to sequence fans.  Richard, you are on this mailing 
list: can you tell us where it will appear?  Is it available
on the web?
NJAS

\documentstyle[12pt,amsfonts]{article} %or 11pt (default 10pt)

\input cyracc.def
\def\cyr{\family{UWCyr}\series{m}\shape{n}\selectfont\cyracc }
\def\cyrit{\family{UWCyr}\series{m}\shape{it}\selectfont\cyracc }
\def\cyrsc{\family{UWCyr}\series{m}\shape{sc}\selectfont\cyracc }
\def\cyrbf{\family{UWCyr}\series{b}\shape{n}\selectfont\cyracc }
\def\cyrss{\family{UWCyss}\series{m}\shape{n}\selectfont\cyracc }

\textwidth=470pt
\textheight=580pt
\hoffset=-55pt
\voffset=-30pt
\parindent=12pt
\parskip=6pt
\def\Erd{Erd\H{o}s}
\def\Cre{{\it J.~reine angew.\ Math.}, }
\def\MaT{{\it Math.\ Comput.}, }
\def\JCA{{\it J.~Combin.\ Theory Ser.\ A}, }
\def\JCB{{\it J.~Combin.\ Theory Ser.\ B}, }
\begin{document}
\title{What's Left?}
\author{Richard K. Guy}
\maketitle

Your editor recently asked me: `After Fermat's Last Theorem, what's
left?'

Paradoxically, even more than there was before.  With most good
mathematical problems, the more you solve, the more new problems are
propagated.

What people are asking is: are there any more problems out there like
Fermat's Last Theorem?  What was it that made FLT particularly capture
the imagination?  Three things: it appears to involve only simple
arithmetic; it held out so long against the efforts of generations of
famous mathematicians; Fermat said that he had a proof.  There aren't
too many problems which have this third quality.  Kempe thought that
he'd proved the Four Color Theorem, but in that case he published his
proof for all to see and it was only a dozen years before it was found
to have a hole in it.

But there are plenty of problems which have been around as long as FLT
and much longer and there are plenty which seem only to involve simple
arithmetic.  What is difficult to estimate is how much {\bf mathematics}
there is in them.

{\bf Only simple arithmetic?}  Here are a couple of questions that
probably don't contain any mathematics, and (perhaps for that reason?)
seem unlikely to be answered in the foreseeable future, even though
we `know' that the answers are ``No!''
$$2^{86}=77371252455336267181195246$$
is a power of two which contains no zeros in its decimal representation.
Are there any larger such powers?

If we start with a number, say 89, and reverse it, 98, and add, we get
187.  If we reverse that, 781, and add, we get 968. Reverse and add
again, 1837.  Again, 9218.  Again, 17347.  Then 91718.  Then 173437.
After seventeen more steps, if we've both done our arithmetic correctly,
we arrive at the {\bf palindromic} number 8813200023188, i.e., a
number which reads the same backwards and forwards.  The same thing
seems to happen with most numbers.  But Sprague and Trigg and others
have asked: if we start with 196, will we ever come to a palindromic
number?  John Walker, Tim Irvin and others have pushed this to millions
of digits without finding one.

And here's a problem where we seem quite unable even to do the arithmetic!
Lionel Levine suggested the array: \\
1 1 \\
1 2 \\
1 1 2 \\
1 1 2 3 \\
1 1 1 2 2 3 4 \\
1 1 1 1 2 2 2 3 3 4 4 5 6 7 \\
$\ldots\quad\ldots\quad\ldots\quad\ldots$\\
where each row is found by reading the previous row from {\bf right to
left}, e.g., the last row is got by reading the previous row backwards:
`four 1s, three 2s, two 3s, two 4s, one 5, one 6, one 7'. Neil Sloane
knows fifteen members of the sequence of last numbers in each row:
1, 2, 2, 3, 4, 7, 14, 42, 213, 2837, 175450, 139759600, 6837625106787,
266437144916648607844, 508009471379488821444261986503540, and wonders
if anyone will ever calculate the 20th term.

{\bf Don't try this at home!}  These problems don't seem to have much
mathematics in them (though it's very difficult to tell such things),
but there are others where at least one new good idea is needed.  There's
the infamous $3x+1$ problem: if a number is odd, multiply by 3 and add 1;
if it's even, divide by two; do we always get to 1 ?
$$7,\,22,\,11,\,34,\,17,\,52,\,26,\,13,\,40,\,20,\,10,\,5,\,16,\,8,\,4,\,2,\,1$$
Half a century ago, Erd\H{o}s said, ``Mathematics may not yet be ready
for such problems''.  He might have said the same about FLT, but
mathematics was rapidly in the process of getting ready!

Here's a very similar problem, perhaps even more intriguing.  Conway
has looked at the permutation
$$3n\leftrightarrow2n\qquad3n\pm1\leftrightarrow4n\pm1$$
which is neater in that you can go either way.  Forwards: if it divides
by 3, take off a third; if it doesn't, add a third (to the nearest
whole number).  Backwards: if it's even, add 50\%; if it's odd, take off
a quarter.  If we start with 1 we get 1, 1, 1, 1, 1, $\ldots$; if we start
with 2 or 3 we get 2, 3, 2, 3, 2, 3, $\ldots$; and if we start with 4 we get
4, 5, 7, 9, 6, 4, 5, 7, 9, $\ldots$ .  And try starting with 44.  But if we start
with 8:
$$8\rightarrow11\rightarrow15\rightarrow10\rightarrow13\rightarrow17
\rightarrow23\rightarrow31\rightarrow41\rightarrow55\rightarrow73
\rightarrow97\rightarrow\ldots$$
or, if we go backwards from 8:
\small
$$\ldots\leftarrow48\leftarrow32\leftarrow43\leftarrow57\leftarrow38
\leftarrow51\leftarrow34\leftarrow45\leftarrow30\leftarrow20
\leftarrow27\leftarrow18\leftarrow12\leftarrow8$$
\normalsize
the sequences never seem to finish.  We have the curious paradox that when
we go `forwards', a third of the time we multiply by 2/3 and two-thirds of
the time we multiply by (roughly) 4/3; on the average, in three steps we
multiply by 32/27.  But when we go `backwards', half the time we multiply
by 3/2 and half the time by (roughly) 3/4; on average two steps multiply
by 9/8.  We increase either way!  This is certainly borne out by
experiment.  Note that, when going backwards, each successor to an
even number is a multiple of 3 --- half the numbers are multiples of
three!  Does the chain with 8 in it close up to form a loop or is it
infinite in each direction?  The first number we haven't seen is 14.
Does it form a different chain?  Are 40, 64, 80, 82, 104, 136, 172, 184,
$\ldots$, each in different chains or loops?  Are there infinitely many
such chains?  Are there any more loops?  Again, there are many more
questions than answers.

If you want an old problem, then perfect numbers go back to the ancient
Greeks.  6=1+2+3 and 28=1+2+4+7+14 are the sum of their `aliquot parts',
the divisors other than the number itself.  Euclid discovered a rule
for giving even perfect numbers, that $2^{p-1}(2^p-1)$ is perfect when
$2^p-1$ is prime, and Euler showed that these are the only ones.  Are
there any odd perfect numbers?  Are there infinitely many perfect numbers?

In fact the Greeks classified numbers as deficient, perfect or
abundant, according as the sum of the aliquot parts is less than, equal to,
or greater than, the number.  Another problem that goes back a century and
a half is that of `aliquot sequences'.  If we start with a number, and sum
its aliquot parts, then sum the aliquot parts of the result, and continue,
where do we get to?  If you try small numbers you'll soon finish up with 1,
or a perfect number, or perhaps an `amicable pair', such as 220 and 284,
each the sum of the aliquot parts of the other.  (Are there infinitely many
such pairs?)  Catalan and Dickson thought that this always happened.  But
John Selfridge and I believe that infinitely many numbers, perhaps almost
all even numbers, give sequences which go to infinity.  The smallest number
for which there is doubt is 276, which leads to the sequence:
$$276,\,396,\,696,\,1104,\,1872,\,3770,\,3790,\,3050,\,2716,\,2772,\,5964,
\,10164,\,19628,\,19684,\,\ldots, $$
which, after the efforts of generations of calculators, Catalan, Dickson,
Poulet, the Lehmers, Godwin, Selfridge, Wunderlich, Devitt, Struppeck,
Wolfram, Dickerman, Peter Montgomery, te Riele, Bosma, Creyaufm\"uller and
many others that I've forgotten, is known to have terms with more than 100
digits.  The trouble with aliquot sequences is that they plunge up and down
erratically, and there seems to be no way of telling where they'll be a
thousand terms from now.

{\bf Addition and multiplication don't mix!}  For the last few questions
we need to know just a bit more than simple arithmetic.  We need to know
what a prime number is.  And when you start mixing multiplication and
addition, we soon find some very hard problems indeed.

Goldbach conjectured, not so very long after Fermat's time, that every
even number is the sum of two primes (he counted 1 as a prime).  The
nearest we have got to settling this is Vinogradov's {\it tour de force}
that every sufficiently large odd number is the sum of three primes.
Even so, `sufficiently large' is well out of computer range until someone
has a new idea.  Matti Sinisalo has checked the conjecture up to
$4\times10^{11}$ and Chen Jing-Run \& Wang Tian-Ze have shown that
Vinogradov's theorem is true for odd numbers exceeding
$e^{114}\approx 3.23274\times10^{49}$, under the assumption of the
generalized Riemann hypothesis (and there's another fairly old, very famous,
and seemingly impossibly hard problem for you).

And is every even number the difference of two primes?  In infinitely
many ways?  Take the difference 2, for example: are there infinitely many
twin primes: (3,5), (5,7), (11,13), (17,19), (29,31), $\ldots$ ?  Of course
there are, but who is going to prove it?  Are there infinitely many
sets of primes in more general patterns, such as $p-4$, $p$ and $p+2$;
or $p-2$, $p$ and $p+4$ ?  (Of course, $p-2$, $p$ and $p+2$ can't all
three be prime, unless they're 3, 5 and 7.)

Can you find arbitrarily many primes in arithmetic progression?
In 1993 Paul Pritchard coordinated an effort which discovered 22 primes
in arithmetic progression, starting with $a=11410337850553$ and having
common difference $d=4609098694200$. $a+21d=108201410428753$.  Another
example, which starts later, but finishes earlier, is given by
$a=28383220937263$, $d=1861263814410$.

Are there in fact arbitrarily many {\bf consecutive} primes in
arithmetic progression?  In November 1997 Harvey Dubner, Tony Forbes,
Nik Lygeros, Michel Mizony \& Paul Zimmermann joined forces to find 8
consecutive primes in A.P., $p_0=mn+x$ and $p_k=p_0+210k$, $1\leq k\leq7$,
where $m$ is the product of the primes up to 193, $n=220162401748731$ and
\small
$$x=191319589789918126908578516774396766834509691048718767292658692385206295221291.$$
\normalsize

[There was a stop press at this point, announcing the 9 and 10 result.]

{\bf Sums of two powers.}  It was another of Fermat's theorems that
paved the way to finding numbers which are the sum of two squares in
many different ways.  If you form the product of $k+1$ different
primes of shape $4n+1$, it will be the sum of two squares in $2^k$ ways:
$$5\cdot13\cdot17=1105=4^2+33^2=9^2+32^2=12^2+31^2=23^2+24^2$$

For sums of two cubes there's the famous Hardy-Ramanujan taxicab
number: the smallest number expressible as the sum of two
cubes in two different ways is $1729=1^3+12^3=9^3+10^3$, known to
Fr\'enicle de Bessy 340 years ago.  Three hundred years later Leech
found the smallest number expressible as the sum of two cubes in three
different ways:
$$87539319=167^3+436^3=228^3+423^3=255^3+414^3$$
and six years ago Rosenstiel, Dardis \& Rosenstiel found 6963472309248 =
$$2321^3+19083^3=5436^3+18948^3=10200^3+18072^3=13322^3+15530^3$$
It's known that there are numbers expressible as the sum of two cubes
in as many ways as you like, but the least such for five ways isn't
yet known.  Euler knew that $$635318657=133^4+134^4=59^4+158^4$$
but no-one knows of three equal sums of fourth powers.

Are there equal sums of two fifth powers?

{\bf The abc-conjecture.}  Perhaps the nearest problem to FLT is that
of settling the abc-conjecture.  An important step in the proof of FLT
was Frey's elliptic curve,
$$y^2=x(x-A)(x+B).$$
The roots of the cubic are 0, $A$, $-B$, and their absolute
differences are $A$, $B$ and $A+B=C$, say, so that the discriminant
is $A^2B^2C^2$.  Put $A=a^p$, $B=b^p$, $C=c^p$ so that $$a^p+b^p=c^p$$
and the discriminant is $a^{2p}b^{2p}c^{2p}$.  The trick was to show
that you couldn't have such an elliptic curve with comparatively
small prime factors in its {\bf conductor}, a number which has the
same prime factors as the discriminant.

Roughly stated, the abc-conjecture says that if $A+B=C$ with $A$, $B$,
$C$ having no common factor, then some of the prime factors of $ABC$
must be `fairly large'.  Define the {\bf radical} $R$ as the product
of all the different primes which divide $A$, $B$ or $C$ and the
{\bf power} $P$ by $C=R^P$, then the conjecture is that
for a given $\eta>1$, there are only finitely many triples $(A,B,C)$
with $P>\eta$. The record $P=1.62991$ was found by Reyssat with
$$2+3^{10}\cdot109=23^5$$
where $R=2\cdot3\cdot23\cdot109$.  This is closely followed by de Weger's
$$11^2+3^2\cdot5^6\cdot7^3=2^{21}\cdot23$$
where $R=2\cdot3\cdot5\cdot7\cdot11\cdot23$, the product of the primes which
are one less than the divisors of 24, and for which $P=1.62599$.

The Catalan relation, $1+2^3=3^2$, does comparatively poorly with
$P=1.22629$; although 2 and 3 are small primes, they're not very small
compared with 9.  The Catalan conjecture, that 8 and 9 are the only powers
differing by 1, has been settled by Tijdeman for `sufficiently large'
numbers, but once again, completion of this is well beyond computer range
until a new idea comes up.

A particular case of the abc-conjecture is the Beal conjecture, which
you read about in {\it Math Horizons} in the last issue.

So there's plenty left: and that's only a corner of number theory, and
then there's the whole of mathematics -- which is increasing every day!

{\bf Reference}

Richard K.~Guy, {\it Unsolved Problems in Number Theory}, 2nd edition,
Springer-Verlag, 1994.

\end{document}