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 P₂ 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 P₃ 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.

Posted by programmingpraxis

Filed in Exercises

8 Comments »

8 Responses to “Multiply Perfect Numbers”

FA said

September 25, 2015 at 10:01 AM

As Scala stram. (Based on the previous implementation)

def multiplyPerfectNumbers(): Stream[BigDecimal] = bdStreamInf().filter(n => factors(n).sum%n == 0)
multiplyPerfectNumbers().take(5).foreach(println(_))
                                                  //> 1
                                                  //| 6
                                                  //| 28
                                                  //| 120
                                                  //| 496

Rutger said

September 25, 2015 at 10:08 AM

In Python. Optimized my ‘divisors’ algorithm from the exercise “Fermat’s Divisors Challenges” here couple of weeks ago.

def divisors(n):
	result = []
	for i in range(1, int(n**0.5)+1):
		if not n % i:
			result.append(i)
			if i*i != n:  # prevent duplicate, e.g. 3,3 for 9
				result.append(n/i)			# if i is a divisors of n, then so is n/i
	return result

def sum_divisors_is_perfect_multiple(n):
	return not sum(divisors(n)) % n

for i in range(1, 1000000):
	if sum_divisors_is_perfect_multiple(i):
		print i

# output
# 1
# 6
# 28
# 120
# 496
# 672
# 8128
# 30240
# 32760
# 523776

Francesco said

September 25, 2015 at 10:19 AM

Haskell

f n = filter (\\x -> sum (filter ((==0) . rem x) [1..x]) == x*n) [1..]

r. clayton said
September 26, 2015 at 3:43 AM
A solution in Guile Scheme.
Marijn said
September 28, 2015 at 1:34 PM
;;; 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…

cbrachyrhynchos said

October 2, 2015 at 9:27 PM

Creating a “sieve” of divisors was much faster for finding the series for me than factoring each one individually.


std::vector<int> aliquot_series (int limit)

{
  std::vector<int> results (limit + 1, 1);
  results[0] = 0;
  results[1] = 0;
  for (int i = 2; i <= limit; i++)
    {
      for (int j = i + i; j <= limit; j += i)
	{
	  results[j] += i;
	}
    }
  return results;

}

void list_perfect_sums2(int limit)
{
  std::vector<int> series = aliquot_series(limit);
  for (int i = 2; i <= limit; i ++)
    {
      if (series[i] % i == 0) std::cout << i << "\n"; 
    }
}

Mike said

October 3, 2015 at 1:42 AM

I uses a sieve-like method. In Python:

def multiply_perfect(limit=1000000):
	divisor_sum = [0]*limit
	for n in range(1, limit):
		for k in range(n, limit, n):
			divisor_sum[k] += n
		if divisor_sum[n] % n == 0:
			print(n, divisor_sum[n], divisor_sum[n]//n)

#test
multiply_perfect(5000000) 
1 1 1
6 12 2
28 56 2
120 360 3
496 992 2
672 2016 3
8128 16256 2
30240 120960 4
32760 131040 4
523776 1571328 3
2178540 8714160 4

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.

Mayur Lokare said
October 28, 2015 at 7:14 AM
#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

Programming Praxis