Our website would like to use cookies to store information on your computer. You may delete and block all cookies from this site, but parts of the site will not work as a result. Find out more about how we use cookies.
 Keyword Search: Advanced Search

 Finding weird numbers
 by Hugo van der Sanden at 15:19 03/06/05 (Blogs::Hugo)
 In which our intrepid hero discovers (once again) the difference between arithmetic (and arithmetical computation) and mathematics.
 Let's have some definitions: a "factor" (or "divisor") of some positive integer n is any integer that divides it. The factors always include n itself, and 1. A "proper divisor" is any divisor other than n itself. The sum of the factors of n is called σ(n) ("sigma n"). n is "perfect" if the sum of its proper divisors equals n itself, ie if σ(n) = 2n. When σ(n) > 2n, n is called "abundant", and its abundance is σ(n) - 2n. In this case, if n can be expressed as the sum of some of its factors it is called "pseudoperfect" (or "semiperfect"), and if not it is called "weird". An abundant n can be expressed as a sum of its proper divisors if and only if its abundance can be - since if some proper divisors sum to n, precisely the ones you didn't use will sum to the abundance. The smallest weird number is 70 = 2 . 5 . 7 since σ(70) = 1 + 2 + 5 + 10 + 7 + 14 + 35 + 70 = 144, so its abundance is 144 - 2 . 70 = 4, and there is no way to select some of the 7 proper divisors such that they sum to 4. Weird numbers are not common, but they turn up regularly enough. However, all the known weird numbers are even, and it is not currently known whether there even exists such a thing as an odd weird number. Brushing the details under the carpet, a program to check for odd weird numbers is pretty simple:``` for n = 1 to infinity step 2 abundance = sigma(n) - 2 * n if abundance > 0 if not pseudoperfect(n) print n ``` As it happens, the first abundant odd number is 945, and the first one that isn't also divisible by 3 is much higher still - more than 5 billion. (To be precise 5^2 . 7 . 11 . 13 . 17 . 19 . 23 . 29.) So we can speed things up a bit by changing that first line:``` for n = 945 to 5,391,411,025 step 6 ```.. and worry about the large numbers later. But all the calculations take a long time: after 12 days of processing time, it had only got as far as 170 million, and no weird number found yet. So I thought I'd better check up on what it was doing. Now σ(n) is easy to calculate once you know the prime factors of n since it is a "multiplicative function". An integer function f(n) is multiplicative if f(x . y) = f(x) . f(y) whenever x and y are "relatively prime", ie they share no common prime factor (or alternatively, gcd(x, y) = 1). You can see this in the pattern of factors of 70 above: ``` σ(70) = 1 + 2 + 5 + 10 + 7 + 14 + 35 + 70 = (1 + 2 + 5 + 10) + 7 . (1 + 2 + 5 + 10) = (1 + 2 + 5 + 10) . (1 + 7) = (1 + 2) . (1 + 5) . (1 + 7) ``` With any multiplicative function, you just need to calculate the function for the prime powers of your target number and multiply them together. For σ(n) the contribution for a prime p is p + 1 if p appears once, p^2 + p + 1 if it appears twice, and so on. So since 70 = 2 . 5 . 7, σ(70) = (2 + 1) . (5 + 1) . (7 + 1) = 3 . 6 . 8 = 144. Since σ(n) is multiplicative, so is σ(n) / n, and that provides another way to think about these things - n is perfect when σ(n) / n = 2, and abundant when σ(n) / n > 2, and the contributions of the prime powers look like (2 + 1)/2, (5 + 1)/5 etc. So small prime factors contribute much more towards pushing a number to abundance than large prime factors, and this also makes it obvious that any multiple of an abundant number will also be abundant. I took the last number my program had checked, 171,120,495 = 3 . 5 . 7^2 . 13 . 17909, and found its abundance 4 . 6 . (7^2 + 7 + 1) . 14 . 17910 - 2 . 171120495 = 771,330. Because it has one large prime factor and some small ones, I reasoned that to get that sum I'd have to make up the bulk from multiples of 17909, so I checked to find 771330 = 43 . 17909 + 1243. A bit of calculation later and I had 771330 = 17909 . (7 . 5 + 7 + 1) + 13 . (7^2 + 7 . 5 + 7 + 3 + 1) + 7 + 1, so no problems there. But it occurred to me that a) this pattern of "a few small primes and one big one" would be quite common, and b) as long as the big one was big enough, this would add an additional constraint - in the above example, I needed to find independent sums of 43 and 1243 out of the smaller factors, and if either of those two had failed I might well have found a weird number. By now the program had printed up some more, so I took another one: 171,169,515 = 3^2 . 5 . 11 . 17 . 20341. Good, another one of the same pattern. The abundance is (3^2 + 3 + 1) . 6 . 12 . 18 . 20342 - 2n = 382986 = 18 . 20341 + 16848. Now, 16848 is quite large - do the smaller factors even contribute enough to make that possible? Hmm, well the most they can contribute is (3^2 + 3 + 1) . 6 . 12 . 18 = 16848. Ooh, what a strange coincidence - it is exactly enough! So let's get this right: 171,169,515 is pseudoperfect, because its abundance is 382,986, and that can be expressed as 18 . 20341 + 16848, which is 17 . 20341 + 1 . 20341 + σ(3^2 . 5 . 11 . 17), and that last element is defined precisely as the sum of the factors of 3^2 . 5 . 11 . 17, so we have the factors we need (26 of them all told). And that coincidence feels like way too much of a coincidence to be a coincidence, if you see what I mean - it feels like a pattern. Except the other number I tried didn't follow anything like the same pattern. So why didn't it? Well in the first case we had the large prime 17909, and we expressed the abundance as 43 . 17909 + 1243, and 43 isn't much like 18 - 43 is odd, and prime, while 18 is even, and the product of several small primes. In fact, 18 is much more like 42 than 43. Hmm, can we do anything with 42? Well let's see: we had an abundance of 771,330, which works out to 42 . 17909 + 19152. So let's check σ(3 . 5 . 7^2 . 13) = 4 . 6 . (7^2 + 7 + 1) . 14 = (... tappity tap ...) 19152! So let's recapitulate. For brevity I'll write δ(n) ("delta n") for the abundance, σ(n) - 2n. We have:``` δ(9555 . 17909) = 42 . 17909 + σ(9555) δ(8415 . 20341) = 18 . 20341 + σ(8415) ```That's clearly a pattern now, and the bit we don't know is where the 18 and 42 come from. Hmm, I wonder if those small factors are themselves abundant? They almost certainly will be - those big primes are only contributing a multiplier of (p + 1)/p to the σ(n) / n calculation. But it seems a bit unlikely that I'd get an abundance as low as 18 (if so small an abundance were common I'd expect to have seen a weird number much sooner), so I'll check that one first:``` δ(8415 = 3^2 . 5 . 11 . 17) = (3^2 + 3 + 1) . 6 . 12 . 18 - 2 . 8415 = 18 ```Well fancy that. :) I'm pretty confident now, but let's check the other one to be sure:``` δ(9555 = 3 . 5 . 7^2 . 13) = 4 . 6 . (7^2 + 7 + 1) . 14 - 2 . 9555 = 42 ``` And we now have:``` δ(9555 . 17909) = δ(9555) . 17909 + σ(9555) δ(8415 . 20341) = δ(8415) . 20341 + σ(8415) ```so can we prove that it had to be so? Well, as we saw above, σ(x . y) = σ(x) . σ(y) as long as gcd(x, y) = 1, which is clearly the case here with that isolated large prime. So here we have:``` δ(x . p) = σ(x . p) - 2xp = σ(x) . σ(p) - 2xp # gcd(x, p) = 1 = σ(x) . (p + 1) - 2xp = p . (σ(x) - 2x) + σ(x) = p . δ(x) + σ(x) ``` Of course this algebraic identity isn't enough, be need to be sure that we're following the rules - we're supposed to be adding up a set of distinct, proper divisors, are we sure that's the case here? Well that turns out to be pretty easy - the second part is σ(x), which is the sum of the divisors of x. That does include x itself, which isn't a proper divisor of x, but it is a proper divisor of x . p. And because of that gcd requirement, we know that none of those divisors are divisible by p. And the first part p . δ(x), what about that? Well here's the trick - we're looking for the first odd weird number, so if we've got as far as checking x . p we've already checked x, and found that it isn't weird. So we know that we can express δ(x) as a sum of some proper divisors of x. And if we take each of them and multiply by p we'll have a set of proper divisors of x . p, all divisible by p (and therefore distinct from the ones we used for that σ(x) component) which sum to p . δ(x) This is great: we've shown that when we find an abundant odd number m . n, we don't need to do any further checks on it if it's divisible by a smaller abundant number m. Er, as long as gcd(m, n) = 1. Oh, and we've only shown it when n is itself a prime. Hmm, well can we strengthen it? What happens if the additional factor isn't required to be prime?``` δ(m . n) = σ(m . n) - 2mn = ??? ``` Well we won't get very far unless we at least require gcd(m, n) = 1, so let's assume that:``` δ(m . n) = σ(m . n) - 2mn = σ(m) . σ(n) - 2mn # gcd(m, n) = 1 = ??? ``` Hmm, not sure how to split that up to get as nice an expression as we had before. When the cofactor was prime we could express it as σ(p) = p + 1 which made life a lot easier. But still, we hope to split it up into some multiple of δ(m) and something else, so let's go there first:``` δ(m . n) = σ(m . n) - 2mn = σ(m) . σ(n) - 2mn # gcd(m, n) = 1 = (δ(m) + 2m) . σ(n) - 2mn = δ(m) . σ(n) + 2m(σ(n) - n) = ??? ``` Well that doesn't look good - we're dealing with odd numbers, so that 2m factor is going to cause problems. Let's try starting from the other end:``` δ(m . n) = σ(m . n) - 2mn = σ(m) . σ(n) - 2mn # gcd(m, n) = 1 = σ(m) . σ(n) + n . (-2m) = σ(m) . σ(n) + n . (σ(m) - 2m) - n . σ(m) = n . δ(m) + σ(m) . (σ(n) - n) ``` That looks a bit better, so let's see if it works out. That bit on the right expands to "(the sum of all the factors of m) times (the sum of all the factors of n, except for n itself)". So that's a cross-product of two discrete sets of factors, none divisible by n itself (and therefore also guaranteed to be proper divisors). And the ones on the left are all divisible by n, and so guaranteed to be different from the ones on the right, and they're multiplied by δ(m) - and as we saw in the simpler x . p case, we know δ(m) is expressible as a sum of proper divisors of m. Huzzah, we have managed to prove the stronger result, and we can therefore refine the program to discard all abundant numbers m . n that are divisible by a smaller abundant number m as long as gcd(m, n) = 1. So that's what mathematics is about. Of course you'll never see that - if you look in a textbook, it'll tell you something like: When gcd(m, n) = 1. since δ(mn) = nδ(m) + σ(n)(σ(m) - m), mn is pseudoprime if m is. .. and leave the rest to you. [Later] I was going back through this article adding some links, and found this text in one of them: Every multiple of a semiperfect number is semiperfect. .. with no additional justification. Which, after a little thought to try and understand why it might need no justification, led me to the realisation that I'd gone down completely the wrong path. Since a weird number is most likely to turn up for some n that is only barely abundant - that is, where σ(n) is only slightly more than 2n - for computational purposes it makes sense to focus on finding a way to express the abundance as a sum of factors, rather than trying to express n itself: the smaller the number you are trying to handle, the faster it is to prove or disprove the possibility. When looking at the mathematics of it, though, size doesn't matter, so I should have looked again at what I might be able to prove as regards expressing n itself as a sum of factors. And as soon as I considered this, it was immediately clear that a much stronger result can be proved much more simply. Consider some m that can be expressed as a sum of proper divisors of itself - let's take 6 as an example, which is 1 + 2 + 3. Well, if you multiply that list of factors by another number n - let's say 12 by way of example - then each of those factors will be a factor of m.n (ie 12, 24 and 36 are all factors of 6 . 12 = 72), and the sum of those factors will be exactly m . n. So, just as the reference suggests, any multiple of a pseudoperfect number will be quite trivially pseudoperfect, and the search for a first odd weird number can happily skip any multiple of an abundant number. Which in a way is kind of embarrassing in a failing-to-see-the-wood-for-the-trees kind of way. Even so, the proof above however unnecessarily complex in approach and however weak in its result is nevertheless still perfectly valid. I suspect this illustrates something else quite deep about the nature of mathematics, but I haven't quite worked out what it is yet. Hugo Finding weird numbers Hugo van der Sanden - 3/06 Re: Finding weird numbers David Crowson - 3/06 Re: Finding weird numbers Hugo van der Sanden - 3/06 Re: Finding weird numbers Steve - 3/06 Re: Finding weird numbers Bruce Ure - 4/06 Re: Finding weird numbers Bruce Ure - 4/06 Re: Finding weird numbers Hugo van der Sanden - 4/06 Re: Finding weird numbers Bruce Ure - 4/06 Re: Finding weird numbers David Crowson - 4/06 Re: Finding weird numbers David Crowson - 4/06