Perfection in a number

It is of ten easy to find peculiar properties of small numbers that characterize themfor instance,3 is the only number that is the sum of all the previous numbers, while 2 is the only even prime(making it the oddest prime of all). The number 6 has a truly unique property in that it is both the sum and product of all of its smallerfactors:6=1+2+3=1×2×3.

The Pythagoreans called a number like 6perfect, meaning that the number is the sum of its proper factors, as we shall call them,which are the divisors strictly smaller than the number itself. This kind of perfection is indeed very rare. The first five perfect numbers are 6,28,496,8128, and 33,550,336. Alot is known about the even perfect numbers but, to this day, no one has been able to answer the basic question of the Ancients as to whether there are infinitely many of these special numbers. What is more,no one has found an odd one, nor proved that there are none.Any odd perfect number mustbe extremelylarge and there is a long list of special properties that such a number must possess in consequence of its odd perfection. However, all these restrictions have not as yet legislated such a number out of existenceconceivably, these special properties serve to direct our search for the elusive first odd perfect number, which may yet be awaiting discovery.The even perfects were known to Euclid to have a tight connection with a very special sequence of primes, known to us as the Mersenneprimes named after Marin Mersenne(1588–1648),a 17th-century French monk.

A Mersenne number mis one of the form 2p-1, where p is itselfa prime. If you take, by way of example, the first four primes,2,3,5,and 7, the first four Mersenne numbers are seen to be:3,7,31, and127, which the reader can quicklyv erify as prime. If p were not prime, suppose p=ab say, then m=2p-1 is certainly not prime either, as it can be verified that in these circumstances the number mhas 2a-1 as a factor. However, if p is prime then the corresponding Mersenne number is of ten a prime, or so it seems.

And Euclid explained, back in 300 BC, that once you have a prime Mersenne number then there is a perfect number that goes with it, that number being P=2p-1(2p-1). The reader can soon verify that the first four Mersenne primes do indeed give the first four perfect numbers listed above:for example, using the third prime 5 as our seed we get the perfect number P=24(25-1)=16×31=496, the third perfect number in the previous list.(The factors of P are the powers of 2 up to 2p-1, together with the same list of numbers multiplied by the prime 2p-1. It is now an exercise in summing what are known as geometric series(explained in Chapter 5)to check that the proper factors of P do indeed sum to P.)

What is more, in the 18th century the great Swiss mathematician Leonhard Euler(1707–83)(pronounced‘Oiler’)proved the reverse implication in that every even perfect number is of this type. In this way, Euclid and Euler together established a one-to-one match between the Mersenne primes and the even perfect numbers. However, the next natural question is, are all the Mersenne numbers prime? Sadly not, and failure is close at hand as the fifth Mersenne number equals 211-1=2,047=23×89.Indeed, we do not even know if the sequence of Mersenne primes runs out or not–perhaps after a certain point all the Mersenne numbers will turn out to be composite.

The Mersenne numbers are natural prime candidates all the same,as it can be shown that any proper divisor, if one exists, of a Mersenne number mhas the very special form 2kp+1. For example, when p=11, by dent of this result, we need only check for division by primes of the form 22k+1. The two prime factors,23 and 89, correspond to the values k=1 and k=4 respectively.This fact about divisors of Mersenne numbers also provides a bonus in that it affords us a second way of seeing that there must be infinitely many primes, for it shows that the smallest prime divisor of 2p-1 exceeds p, and so p cannot be the largest prime.

Since this applies to every prime p, we conclude that there is no largest prime and the prime sequence runs on forever.Since we have no way of producing primes at will, there is, at any one time, alargest known prime and nowadays the champion is always a Mersenne prime, thanks to the international GIMPS venture(Great Internet Mersenne Prime Search). This is a collaborative project of volunteers, which began in 1996. The project uses thousands of personal computers working in parallel,which test Mersenne numbers for primality using a specially devised cocktail of tailor-made algorithms. The current world champion, announced in August 2008, is 2p-1 where p=43,112,609, although a new Mersenne prime was found in April 2009 with p=42,643,801. These numbers have about 13million digits and would take thousands of pages to write down in ordinary base ten notation.

Less than perfect numbers

Traditional number lore of ten focused on individual numbers thought to have special, if not magical, properties such as those that are perfect. However, a numberpair with a similar trait is220 and 284, the first amicablepair, meaning that the proper factors of each sums to the other–a kind of perfection extended to a couple. The reknowned amateur French mathematician Pierre de Fermat(1601–65)found other amicable pairs, such as 17,296and 18,416, while Euler discovered dozens more. Surprisingly, they both missed the small pair of 1184 and 1210, found by 16-year-old NicolòPaganini in 1866. We can of course try to go beyond pairs and look for perfect triples, quadruples, and so on. Longer cycles are rare but do crop up.

We can begin with any number,find the sum of its proper divisors,and repeat the process, formingwhat is known as the number’s aliquotsequence. The result is often a little disappointing in that typically we get a chain that heads to 1 quite rapidly, at which point the process stalls. For example, even beginning with a promising-looking number such as 12, the chain is short:

12→(1+2+3+4+6)=16→(1+2+4+8)=15→(1+3+5)=9

9→(1+3)=4→(1+2)=3→1.

The trouble is, once you hit a prime, you are finished. The perfect numbers are of course exceptions, each giving us a little loop,while an amicable pair leads to a two-cycle:220→284→220→…. Numbers that lead to cycles longer than two are called sociable. They were not studied at all until the20th century as no one had ever found any. Even today, no number that leads to a three-cycle has been discovered, although there are now 120 known cycles of length four. The first examples were found by P. Poulet in 1918. The first is a five-cycle:

12,496→14,288→15,472→14,536→14,264→12,496.

Poulet’s second example is quite stunning, and to this day no other cycle has been found that comes close to matching it:starting with14,316 we obtain a cycle of length 28. All other known cycles have length less than 10. To the present day, there are no theorems on amicable and sociable numbers as beautiful as those of Euclid and Euler on perfect numbers. However, modern computing power has led to something of an experimental renaissance in this kind of topic and there is more that can be said.

We can divide all numbers into three types, deficient, perfect, and abundant according to whether the sum of their proper divisors is less than, is equal to, or exceeds the number itself. For example, as we have already seen,12 is an abundant number, as are 18 and 24as the respective sums of their proper divisors are 21 and 36.

A naive search for abundance among the integers mightlead you to guess that the abundant numbers are simply the multiples of 6.Certainly, any number greater than 6 of the form 6n is abundant,as the factors of 6n must include 1,2,3 together with n,2n, and3n, which sum to more than the original number 6n. This observation can be extended, however, to show that abundance is notjust about sixes as we can argue the same way for any perfect number k. The factors of nkwill include 1 together with all the factors of the perfect number k, each multiplied by n so that the sum of all the proper factors of nkwill add up to at least 1+nk,and therefore any multiple of a perfect number will be abundant.For example,28 is perfect and hence 2×28=56,3×28=84 etc.are all abundant.

And so we see that multiples of perfect numbers and indeed, by the same token, multiples of abundant numbers are themselves abundant. Having made this discovery, you still might guess that all abundant numbers are simply multiples of perfect numbers.However, you don’t have to look too much further to find the first exception to this conjecture, for 70 is abundant but none of its factors are perfect. Indeed,70 is the first so-called weird number,but not exactly for this reason(the source of this label is explained below).

Despite these discoveries, you might still think it likely that, just as there seem to be no odd perfect numbers, there are no odd abundant numbers either. In other words, our modified conjecture might be that all odd numbers are deficient. Calculation of the aliquot sums of the first few hundred odd numbers would seem to confirm this theory, but the claim is eventually debunked upon testing 945, which has 97s as the sum of its proper divisors. Now the floodgates open as any multiple of an abundant number is abundant, and in particular the odd multiples of 945 immediately supply us with infinitely many more odd abundant numbers.

If we act a little more shrewdly, however, we can discover this counter-example more quickly than if we unthinkingly test one odd number after another. For a number to have a large aliquot sum, it needs lots of factors and large factors at that, which themselves come from being paired with small factors. We can therefore build numbers with large aliquot sums by multiplying small primes together. If we are focusing on odd numbers only, we should look at those that are products of the first few odd primes,which are 3, 5, 7, etc. This rule of thumb would soon lead you to test 33×5×7=945 and thereby discover the abundance property among the odd numbers also.

It is not that unusual to find that the smallest example of a number with certain properties turns out to be rather large. This is especially true if the specified properties implicitly build a certain factor structure into the required numbers. The smallest example can then turn out to be gigantic, although not necessarily hard to find if we exploit the given properties in our quest for the solution.An example of a number riddle of this kind is to find the smallest number that is five times a cube and three times a fifth power. The answer is

7, 119, 140, 625 = 5×ll253=3×755

The reason why the smallest solution is in the billions, however, is not hard to see. Any solution n has to have the form 3r5s m for some positive powers r and s and where the remaining prime factors are collected together into a single integer m that is not divisible by 3 0r 5. If we first focus on the possible values of r, we observe that since n is 5 times a cube, the exponent r must be a multiple of 3, and since n is 3 times a 5th power, the number r-1has to be a multiple of　5. The smallest r that satisfies both these conditions simultaneously is r=6. In the same way, the exponent s has to be a multiple of 5, while s--1 has to be a mutiple of 3 and the least s that fits the bill is s=10. To make n as small as possible,we takem=1 andson=36×510=3(3×52)5=3×755,so that n is indeed 3 times a 5th power and at the same time n=5(32×53)3=5×11253, and so nis also 5 times a cube.

An even more extreme example is the celebrated Cattle Problem,attributed to Archimedes(287–212 BC), the greatest mathematician of antiquity. It was not solved until the 19. The smallest herd of cattle that satisfies all the imposed constraints in the original 44-line poem is represented by a number with over 200,000 digits!

A warning to be gleaned from all this is that numbers do not display their full variety until we move into the realms of the very large. For that reason, the mere fact that there are no odd perfect numbers with fewer than 300 digits does not in itselfgive grounds for saying that they‘probably’do not exist. All the same, it is the case that some leading experts in the field would be astonished if one ever turned up.

Returning once again to the general behaviour of aliquot sequences, there are still simple questions that may be put that no one can answer. What possibilities are open to aliquot sequences?Ifthe sequence hits a prime, it will immediately terminate thereafter at 1, and cannot do this in any other way. If this does not happen, the sequence could be cyclic and so represent a sociable number. There is, however, another related possibility that is revealed by calculating the aliquot sequence of 95:

95=5×19→(1+5+19)=25=5×5→(1+5)=6→6→6→….

What has happened here is that although 95 is not itselfa sociable number, its aliquot sequence eventually hits a sociable number(or more precisely in this case, the perfect number 6)and then goes into a cycle.

There is conceivably one possibility remaining, that being that the aliquot sequence of a number never hits a prime nor a sociable number, in which case the sequence must be an unending series of different numbers, none of which are either prime or sociable. Is this possible? Surprisingly, no one knows. What is more surprising is that there are small numbers whose aliquot sequence remain unknown(and thereby remain candidates for having such an infinite aliquot sequence). The first of these mysterious numbers is276, whose sequence begins:

276→396→696→1104→1872→3770→3790→

→3050→2716→2772→…

but no one knows exactly where it ends up.

It might well be that the reader would like to explore a little on their own, in which case I should let you in on the secret of how to calculate the so-called aliquotfunction a(n)from the prime factorization of n–take the product of all terms(pk+1-1)/(p-1),where pk is the highest prime power of the prime p that divides n,and then subtract n itself. For example,276=22×3×23 and so

as indicated by the second term in the aliquot sequence for 276listed above.

There is no end to the types of numbers that we can introduce by giving a name to the numbers n that bear a certain relationship to the aliquot function. As we have already mentioned, nisperfect if a(n)=nand abundantifa(n)〉n. Asemiperfectnumber nis one that is the sum of some of its proper divisors(those less than n), so it follows from the denition that all semiperfect numbers are either perfect or abundant. For example,18 is semiperfect as18=3+6+9. A number is called weird if it is abundant but not semiperfect, and the smallest weird number is 70.

One can take the view that the topic is becoming too miscellaneous in nature–bestowing names on rather arbitrarily dened classes of numbers does not of its own accord make them interesting. We should know when to stop. That said, it is worth appreciating that the underlying strategies used to tackle these new questions are yet reminiscent of what Euclid and Euler showed us in relation to perfect numbers. You will recall that what Euclid proved was that if a Mersenne number was prime then another number was even and perfect. Euler then proved conversely that all even perfect numbers arise from this approach. In the 9th century, the Persian mathematician Thabit ibn Qurra introduced for any number na triple of numbers which, if all prime, allowed the construction of an amicable pair. Thabit’s construction was generalized further by Euler in the 18th century, but even this enhanced formulation only seems to yield a few amicable pairs and there are many amicable pairs that do not arise from this construction.(There are now nearly 12 million known pairs of amicable numbers.)In modern times, a similar approach by Kravitz gives a construction of weird numbers from certain numbers should they happen to be prime,and this formula has successfully found a very large weird number with more thanfty digits.

These last two chapters have served to familiarize the reader with factors and factorization of the natural numbers, or positive integers are they are also known, illustrated through a variety of examples. This will stand you in good stead for the upcoming chapter, in which you will learn how those ideas are applied to contemporary cryptography, the science of secrets.