## Tuesday, 14 August 2018

### On Descartes Numbers

A number is said to be Perfect if it is equal to the sum of its proper positive factors, i.e. the sum of its factors excluding the number itself.  Summing all of the factors of a number $$n$$ — i.e. including the number $$n$$ itself — is known as the sum-of-divisors function:

$\sigma \left( n \right) = \sum\limits_{d\left| n \right.} d$
A number $$n$$ is thus said to be Perfect when $$\sigma \left( n \right)$$ = 2n.  For example, the factors of 28 — 1, 2, 4, 7, 14 and 28 — sum to 28 + 28 = 56, thus $$\sigma \left( {28} \right)$$ = 2 $$\times$$ 28 and so 28 is a Perfect number.  In contrast, and by way of illustration, the factors of 42 — 1, 2, 3, 6, 7, 14, 21 and 42 — sum to 96, or 2.2857... $$\times$$ 42, thus $$\sigma \left( {42} \right) \ne$$ 2 $$\times$$ 42 and so 42 is not a Perfect number.  In fact, 42 is said to be an Abundant number because the sum of its proper positive divisors is greater than the number itself, i.e. $$\sigma \left( n \right) > 2n$$.  When the sum of a number's proper positive divisors is less than the number itself, i.e. $$\sigma \left( n \right) < 2n$$, the number is said to be Deficient.  For example, the factors of 50 — 1, 2, 5, 10, 25 and 50 — sum to 93, or 1.86 $$\times$$ 50, and thus $$\sigma \left( {50} \right)$$ < 2 $$\times$$ 42.  As such:

$\begin{array}{l}\sigma \left( n \right) < 2n \Rightarrow n\;{\rm{is}}\;{\rm{deficient}}\\\sigma \left( n \right) = 2n \Rightarrow n\;{\rm{is}}\;{\rm{perfect}}\\\sigma \left( n \right) > 2n \Rightarrow n\;{\rm{is}}\;{\rm{abundant}}\end{array}$
Perfect numbers have intrigued us since Euclid, who observed via Proposition 36 in Book IX of his Elements that a number of the form (2$$^{p - 1}$$)(2$$^p$$ − 1) is a perfect number whenever 2$$^p$$ − 1 is prime (i.e. what subsequently became known as a Mersenne prime) [1].  The fact that every even perfect number is of this type, i.e. that every even perfect number can be written in the form (2$$^{p - 1}$$)(2$$^p$$ − 1) whenever 2$$^p$$ − 1 is prime, was proposed by René Descartes in his famed correspondence with Marin Mersenne (specifically in his letter to Mersenne of 15 November 1638) [2], and later proven in 1849 by Leonhard Euler [3].  Descartes was, indeed, 'among the first to consider the existence of odd perfect numbers' (Greathouse and Weisstein, 2012).

As of writing, of the fifty perfect numbers that have been found, all are even, and it is not known if there are infinitely many or, indeed, whether any odd perfect numbers exist — although Pascal Ochem and Michaël Rao showed (2012) that no number up to 10$$^{1500}$$ is an odd perfect number.

One number has been found, however, that would have been an odd perfect number if only one of its factors was prime rather than a 'spoof prime' (i.e. a composite number wrongly assumed to be prime).  This number — 198,585,576,189 — was found in 1638 by Descartes, documented in his 15 November letter to Mersenne, and is known as a Descartes Number, or, as an 'odd spoof perfect number' (note that the spoof prime in question is 22021, i.e. 19$$^2$$ $$\times$$ 61).

$198,585,576,189 = {3^2} \times {7^2} \times {11^2} \times {13^2} \times 22021$
Descartes showed that if 22021 was prime, the proper factors of 198,585,576,189 [4] would sum to 198,585,576,189 — making it the only odd perfect number ever found.  As it is, because 22021 is not prime, or because 22021 is a spoof prime, the proper factors of 198,585,576,189 do not sum to 198,585,576,189 (they actually sum to 227,441,894,589).  This makes 198,585,576,189 an odd spoof perfect number, which in itself is the only such number ever found!

To elaborate: Descartes showed that an equivalence to the sum-of-divisors function using the prime factorisation of a number is the following [5]:

$\sigma \left( n \right) = \prod\limits_{{p^a}\left\|{\;n} \right.} {\frac{{{p^{a + 1}} - 1}}{{p - 1}}} {\rm{ }}$
where $$p$$ is a distinct prime factor.  This means that a number's factors can be summed using only the number's prime factors.  Taking 28 again as an example, we have seen that it is a perfect number because

$\sigma \left( 28 \right) = \sum\limits_{d\left| 28 \right.} d = 1 + 2 + 4 + 7 + 14 + 28 = 56 = 2n$
We can also observe this result using the prime factors of 28, i.e. 2$$^2 \times$$ 7:

$\prod\limits_{{p^a}\left\|{\;n} \right.} {\frac{{{p^{a + 1}} - 1}}{{p - 1}}} = \frac{{{2^{2 + 1}} - 1}}{{2 - 1}} \times \frac{{{7^{1 + 1}} - 1}}{{7 - 1}} = \frac{7}{1} \times \frac{{48}}{6} = 56 = 2n$
And so, similarly, the sum of the divisors of Descartes' number:

\begin{array}{c}\begin{align}\sigma \left( 198,585,576,189 \right) &= \prod\limits_{{p^a}\left\| {\;n} \right.} {\frac{{{p^{a + 1}} - 1}}{{p - 1}}} \\ \\&= \frac{{{3^{2 + 1}} - 1}}{{3 - 1}} \times \frac{{{7^{2 + 1}} - 1}}{{7 - 1}} \times \frac{{{{11}^{2 + 1}} - 1}}{{11 - 1}} \times \frac{{{{13}^{2 + 1}} - 1}}{{13 - 1}} \times \frac{{{{22021}^{1 + 1}} - 1}}{{22021 - 1}}\\ \\&= 13 \times 57 \times 133 \times 183 \times 22022\\ &= 13 \times \left( {3 \times 19} \right) \times \left( {7 \times 19} \right) \times \left( {3 \times 61} \right) \times \left( {2 \times 7 \times 11 \times 11 \times 13} \right)\\ &=2 \times {3^2} \times {7^2} \times {11^2} \times {13^2} \times \left( {{{19}^2} \times 61} \right)\\ &= 2 \times {3^2} \times {7^2} \times {11^2} \times {13^2} \times 22021\\ &= 2 \times 198,585,576,189\end{align}\end{array}
Hence, if 22021 were prime rather than 19$$^2$$ $$\times$$ 61, Descartes' number 198,585,576,189 would  be an odd perfect number because $$\sigma \left( n \right)$$ = 2n.

[1] The first four perfect numbers — 6, 28, 496 and 8128 — were known to early Greek mathematics. See this for a full list of known Perfect numbers.  See also these typically lovely Numberphile videos with Matt Parker on 'Perfect Numbers and Mersenne Primes' and 'Perfect Number Proof'.

[2] Descartes wrote: 'Mais je pense pouvoir démontrer qu'il n'y en a point de pairs qui soient parfaits, excepté ceux d'Euclide; et qu'il n'y en a point aussi d'impairs, si ce n'est qu'ils soient composés d'un seul nombre premier, multiplié par un carré dont la racine soit composée de plusieurs autres nombres premiers. Mais je ne vois rien qui empêche qu'il ne s'en trouve quelques-uns de cette sorte: car, par exemple, si 22021 était nombre premier, en le multipliant par 9018009, qui est un carré dont la racine est composée des nombres premiers 3, 7, 11 et 13, on aurait 198.585.576.189, qui serait nombre parfait. Mais, quelque méthode dont on puisse user, il faut beaucoup de temps pour chercher ces nombres, et peut-être que le plus court a plus de 15 ou 20 notes.'

And in English: 'But I think I can show that there are no perfect peers except those of Euclid; and that there are no other odd ones, except that they are composed of a single prime number, multiplied by a square whose root is composed of several other prime numbers. But I do not see anything that prevents some of this kind from occurring: for example, if 22021 was prime number, multiplying it by 9018009, which is a square whose root is made up of numbers first 3, 7, 11 and 13, we would have 198,585,576,189, which would be perfect number. But, whatever method you can use, it takes a long time to look for these numbers, and perhaps the shorter one has more than 15 or 20 notes.'

For an English translation of selected excerpts from Descartes' 29 page 15 November 1638 letter to Mersenne click here (p88-91), For more of the correspondence of René Descartes, including links to transcripts, browse Early Modern Letters Online catalogue here.

[3] This theorem is now known as the Euclid-Euler Theorem.  For an outline of the proof, see, for example, Voight (1998, p5).

[4] If you're interested, the factors of 198,585,576,189 are: 1, 3, 7, 9, 11, 13, 19, 21, 33, 39, 49, 57, 61, 63, 77, 91, 99, 117, 121, 133, 143, 147, 169, 171, 183, 209, 231, 247, 273, 361, 363, 399, 427, 429, 441, 507, 539, 549, 627, 637, 671, 693, 741, 793, 819, 847, 931, 1001, 1083, 1089, 1159, 1183, 1197, 1281, 1287, 1463, 1521, 1573, 1617, 1729, 1859, 1881, 1911, 2013, 2223, 2299, 2379, 2527, 2541, 2717, 2793, 2989, 3003, 3211, 3249, 3477, 3549, 3843, 3971, 4389, 4693, 4697, 4719, 4851, 5187, 5551, 5577, 5733, 5929, 6039, 6897, 7007, 7137, 7381, 7581, 7623, 8113, 8151, 8281, 8379, 8723, 8967, 9009, 9633, 10241, 10309, 10431, 10647, 11011, 11913, 12103, 12749, 13013, 13167, 14079, 14091, 14157, 15067, 15561, 16093, 16653, 16731, 17689, 17787, 19019, 20449, 20691, 21021, 22021, 22143, 22477, 22743, 24339, 24453, 24843, 26169, 26901, 27797, 28899, 29887, 30723, 30927, 32851, 32879, 33033, 35321, 35739, 36309, 38247, 38857, 39039, 42237, 42273, 43681, 45201, 48279, 49959, 51623, 51667, 53067, 53361, 56791, 57057, 61009, 61061, 61347, 63063, 66063, 66429, 67431, 72163, 73017, 74529, 77077, 78507, 83391, 89243, 89661, 91091, 92169, 92781, 95953, 98553, 98637, 99099, 105469, 105963, 108927, 112651, 113399, 114741, 116571, 117117, 131043, 133133, 135603, 140239, 143143, 144837, 154147, 154869, 155001, 157339, 159201, 165737, 170373, 171171, 183027, 183183, 184041, 194579, 195871, 198189, 202293, 209209, 216489, 229957, 231231, 242231, 247247, 250173, 267729, 268983, 273273, 286273, 287859, 295659, 295911, 305767, 316407, 317889, 337953, 340197, 349713, 361361, 361669, 388531, 393129, 399399, 420717, 427063, 427427, 429429, 462441, 464607, 465003, 472017, 497211, 505141, 511119, 549081, 549549, 567853, 583737, 587613, 624701, 627627, 649467, 671099, 671671, 689871, 693693, 726693, 738283, 741741, 793793, 803187, 819819, 858819, 863577, 917301, 949221, 981673, 1002001, 1013859, 1020591, 1079029, 1084083, 1085007, 1160159, 1165593, 1198197, 1247389, 1262151, 1281189, 1282281, 1288287, 1371097, 1387323, 1416051, 1464463, 1491633, 1515423, 1695617, 1703559, 1730729, 1751211, 1762839, 1823107, 1874103, 1882881, 2003911, 2013297, 2015013, 2069613, 2140369, 2154581, 2180079, 2214849, 2225223, 2381379, 2529527, 2576457, 2664541, 2719717, 2751903, 2945019, 2989441, 3006003, 3149003, 3237087, 3252249, 3255021, 3480477, 3496779, 3721549, 3742167, 3843567, 3846843, 3974971, 4113291, 4393389, 4546269, 4697693, 4701697, 5086851, 5110677, 5192187, 5469321, 5556551, 5622309, 6011733, 6039891, 6045039, 6421107, 6463743, 6644547, 6871711, 7144137, 7382089, 7588581, 7993623, 8121113, 8159151, 8731723, 8835057, 8968323, 9018009, 9447009, 9597679, 9711261, 10441431, 11164647, 11226501, 11869319, 11924913, 12339873, 12761749, 13180167, 14027377, 14093079, 14105091, 15082067, 15260553, 15576561, 16407963, 16669653, 18035199, 18651787, 19038019, 19263321, 19391229, 20615133, 22043021, 22146267, 22765743, 23700391, 23980869, 24363339, 24477453, 26050843, 26195169, 26904969, 27824797, 28341027, 28793037, 32883851, 33493941, 34639033, 35607957, 35774739, 38285247, 40937039, 42082131, 42279237, 42315273, 45246201, 50008959, 51674623, 55955361, 57114057, 61122061, 61845399, 66129063, 66438801, 71101173, 73090017, 78152529, 78585507, 83474391, 86379111, 89332243, 98651553, 103917099, 105574469, 106823871, 114855741, 122811117, 126246393, 130562509, 135738603, 154301147, 155023869, 165902737, 167866083, 171342171, 182355901, 183366183, 198387189, 213303519, 234457587, 242473231, 250423173, 267996729, 286559273, 295954659, 311751297, 316723407, 361722361, 368433351, 391687527, 450307429, 462903441, 465071607, 497708211, 547067703, 550098549, 727419693, 803990187, 859677819, 950170221, 1085167083, 1161319159, 1175062581, 1350922287, 1388710323, 1493124633, 1641203109, 1697312617, 2005914911, 2182259079, 2579033457, 3152152003, 3255501249, 3483957477, 4052766861, 5091937851, 6017744733, 9456456009, 10451872431, 15275813553, 18053234199, 22065064021, 28369368027, 66195192063, 198585576189.  (Found using this Wolfram Alpha Widget.)

Abundant Number (n.d.).  In Wikipedia.  Retrieved August 2018 from https://en.wikipedia.org/wiki/Abundant_number

Banks, W.D., Guloglu, A.M., Wesley Nevans, C., Saidak, F.  (2008).  Descartes Numbers.  Retrieved July 2018 from
https://pdfs.semanticscholar.org/cb02/869f21a4dddd9dacb2c8a31ff3672bdbfff1.pdf

Deficient Number (n.d.).  In Wikipedia.  Retrieved August 2018 from https://en.wikipedia.org/wiki/Deficient_number

Divisor Function (n.d.).  In Wikipedia.  Retrieved August 2018 from https://en.wikipedia.org/wiki/Divisor_function

Descartes, R.  (1638).  Letter to Marin Mersenne dated 15 November 1638.  Circulation of Knowledge and Learned Practices in the 17th-century Dutch Republic Transcription.  Retrieved July 2018 from http://ckcc.huygens.knaw.nl/epistolarium/letter.html?id=desc004/3184

Euclid-Euler Theorem (n.d.).  In Wikipedia.  Retrieved August 2018 from https://en.wikipedia.org/wiki/Euclid%E2%80%93Euler_theorem

Euler, L. (1849).  'De numeris amicibilibus', Commentationes arithmeticae Vol. 2, pp. 627-636.  Retrieved July 2018 from http://eulerarchive.maa.org//docs/originals/E798.pdf

Greathouse, C. and Weisstein, E.W. "Prime Counting Function." From MathWorld--A Wolfram Web Resource.  Retrieved February 2018 from http://mathworld.wolfram.com/OddPerfectNumber.html

Joyce, D.E.  'Euclid's Elements: Book IX, Propostion 36', Department of Mathematics and Computer Science, Clark University.  Retrieved August 2018 from
https://mathcs.clarku.edu/~djoyce/elements/bookIX/propIX36.html

List of Perfect Numbers (n.d.).  In Wikipedia.  Retrieved August 2018 from https://en.wikipedia.org/wiki/List_of_perfect_numbers

O'Connor, J.J. and Robertson, E.F.  (1998, September).  'Leonhard Euler', School of Mathematics and Statistics, University of St Andrews.  Retrieved August 2018 from hhttp://www-history.mcs.st-and.ac.uk/Biographies/Euler.html

O'Connor, J.J. and Robertson, E.F.  (1999, January).  'Euclid of Alexandria', School of Mathematics and Statistics, University of St Andrews.  Retrieved August 2018 from http://www-groups.dcs.st-and.ac.uk/history/Biographies/Euclid.html

O'Connor, J.J. and Robertson, E.F.  (2005, August).  'Marin Mersenne', School of Mathematics and Statistics, University of St Andrews.  Retrieved July 2018 from http://www-groups.dcs.st-and.ac.uk/history/Biographies/Mersenne.html

O'Connor, J.J. and Robertson, E.F.  (2014, November).  'René Descartes', School of Mathematics and Statistics, University of St Andrews.  Retrieved July 2018 from http://www-history.mcs.st-andrews.ac.uk/Biographies/Descartes.html

O'Connor, J.J. and Robertson, E.F.  (2018, January).  'Perfect Numbers', School of Mathematics and Statistics, University of St Andrews.  Retrieved July 2018 from http://www-groups.dcs.st-and.ac.uk/history/HistTopics/Perfect_numbers.html

Voight, J.  (1998).  Perfect Numbers: An Elementary Introduction. Retrieved July 2018 from https://math.dartmouth.edu/~jvoight/notes/perfelem.pdf