Multiply Perfect Numbers
September 25, 2015
As regular readers know, I greatly enjoy problems at the intersection of recreational mathematics and number theory. Today’s exercise is an example of that.
As was known to the ancient Greeks, perfect numbers such as 6 and 28 are equal to the sum of their aliquot divisors (those divisors less than the number itself); for instance, 6 = 1 + 2 + 3 and 28 = 1 + 2 + 4 + 7 + 14. Mathematicians refer to these as P2 numbers the sum of the divisors, including the number itself, is twice the number.
Multiply perfect numbers are numbers such that the sum of their divisors are some multiple of the number; perfect numbers have divisor-sums twice the number, triply perfect numbers P3 have divisor-sums thrice, the number, and so on.
Your task is to write a program that finds multiply perfect 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.
As Scala stram. (Based on the previous implementation)
In Python. Optimized my ‘divisors’ algorithm from the exercise “Fermat’s Divisors Challenges” here couple of weeks ago.
Haskell
A solution in Guile Scheme.
;;; the sum of divisors of a perfect number equals some multiple of that number
;;; example: 6 is 2-perfect, because 2*6 = 1+2+3+6
(define mod modulo)
(define (divisors num)
(let ((sqrt-num (sqrt num)))
(let loop ((d 1) (divs ‘()))
(if (<= d sqrt-num)
(loop (+ d 1)
(if (zero? (mod num d))
(if (= (* d d) num)
(cons d divs)
(cons (/ num d) (cons d divs)))
divs))
divs))))
(define (perfect candidate)
(if (zero? (mod (apply + (divisors candidate)) candidate))
(/ (apply + (divisors candidate)) candidate)
#f))
(let loop ((num 1))
(let ((p? (perfect num)))
(if p?
(begin
(display num)(display ": ")
(display p?)(newline))))
(if (<= num 1000000)
(loop (+ num 1))
#f))
output:
1: 1
6: 2
28: 2
120: 3
496: 2
672: 3
8128: 2
30240: 4
32760: 4
523776: 3
According to Wikipedia it is an open problem how many of these numbers exist…
Creating a “sieve” of divisors was much faster for finding the series for me than factoring each one individually.
I uses a sieve-like method. In Python:
A PhD thesis at https://opus.lib.uts.edu.au/research/bitstream/handle/2100/275/02Whole.pdf?sequence=2021
has lots of interesting history and information on multiperfect numbers. Like current minimum and maximum k-perfect numbers for 1 <= k <= 11. Also, there are no odd multiperfect numbers less than 10^70.
#include
int main()
{
int i,j,n=15,count=0,num;
printf(“Enter the length of sequance\n”);
scanf(“%d”,&num);
for(n=1;n<num;n++)
{
for(i=1;i<n;i++)
if(n%i==0)
count+=i;
if(count==n)
printf("%d is Perfect Number\n",n);
count=0;
}
}
o/p:
10000
6 is Perfect Number
28 is Perfect Number
496 is Perfect Number
8128 is Perfect Number