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.

Pages: 1 2

8 Responses to “Multiply Perfect Numbers”

  1. FA said

    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
    
  2. Rutger said

    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
    
  3. Francesco said

    Haskell

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

    A solution in Guile Scheme.

  5. Marijn said

    ;;; 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…

  6. 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"; 
        }
    }
    
  7. Mike said

    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.

  8. Mayur Lokare said

    #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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: