Triperfect Numbers
April 23, 2019
We have another exercise today based on a Numberphile video:
A perfect number is a number n that is equal to the sum of its divisors, excluding itself; in other words, a perfect number n satisfies the equation σn = 2n, where σ is the divisor-sum function. A triperfect number is a number n such that σn = 3n. It is believed that there are six, and only six, triperfect numbers.
Your task is to compute the six triperfect numbers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Oh, com.informatimago.common-lisp.arithmetic.primes:divisors is found in https://github.com/informatimago/lisp/blob/master/common-lisp/arithmetic/primes.lisp
Here’s a solution in C that uses trial division to find factors. It would seemingly take a long time using this implementation to find the six triperfect numbers.
@programmingpraxis, can you elaborate on your “pre-qualify” filter? Your solution says “all of the multiperfect numbers are highly composite”, but the second triperfect number, 672, is not a highly composite number (according the the Wikipedia definition of highly composite, aka “anti-prime”, numbers).
Output:
@Daniel: I will answer for @programmingpraxis. All the triperfect numbers are similar to highly composite numbers. They all look like 2^nprime1prime2….. with all primes below 160. The triperfect numbers are no hcn though. Knowing this you can factorise the numbers with low prime numbers only (prequalify). Another trick is to search the sequence a, 2a, 3a, 4a, .. with a=2^n. In this way you can find even the highest triperfect numbers very quickly. I feel it is kind cheating though, as long as you cannot proof mathematically that triperfect numbers should behave like that.