Multiply Perfect Numbers

September 25, 2015

This is easy if you have all the machinery for factoring integers and computing divisor-sums:

> (do ((n 1 (+ n 1))) (#f)
(when (zero? (modulo (sigma 1 n) n))
(display n) (newline)))
1
6
28
120
496
672
8128
30240
32760
523776
...

You can run the program at http://ideone.com/jUw4Z6, where you will also see all of the functions that support the computation of sigma.

Advertisements

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s

%d bloggers like this: