Finding perfect numbers (optimization)

Question

I coded up a program in C# to find perfect numbers within a certain range as part of a programming challenge . However, I realized it is very slow when calculating perfect numbers upwards of 10000. Are there any methods of optimization that exist for finding perfect numbers? My code is as follows:

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleTest
{
 class Program
 {
  public static List<int> FindDivisors(int inputNo)
  {
   List<int> Divisors = new List<int>();
   for (int i = 1; i<inputNo; i++)
   {
    if (inputNo%i==0)
     Divisors.Add(i);
   }
   return Divisors;
  }

  public static void Main(string[] args)
  { 
   const int limit = 100000;

   List<int> PerfectNumbers = new List<int>();
   List<int> Divisors=new List<int>();
   for (int i=1; i<limit; i++)
   {
    Divisors = FindDivisors(i);
    if (i==Divisors.Sum())
     PerfectNumbers.Add(i);
   }

   Console.Write("Output =");

   for (int i=0; i<PerfectNumbers.Count; i++)
   {
    Console.Write(" {0} ",PerfectNumbers[i]);
   }

   Console.Write("\n\n\nPress any key to continue . . . ");
   Console.ReadKey(true);
  }
 }
} 

Execration

Calculating perfect numbers is like calculating how many days there are in each week. The results never change, so don't calculate them. Look them up. – Gridley

@ Daniel Dyson - The poster indicated it was some sort of programming challenge and I doubt he'll be happy with an array of pre-calculated answers =) – Chemulpo

@ paradox - You also have another problem that, because perfect numbers are so sparse, you'll quickly break your int limits if your program goes seriously searching for perfect numbers. – Chemulpo

@Joel Goodwin. That is a fair point, but if I was setting such a challenge to one of my team, I would expect them to come up with the answer that these should be stored and not calculated. After all, the way I read it, the challenge is "to find perfect numbers" not necessarily to "calculate" them. If they have all already been calculated within that range, why calculate them again? Programming is about coming up with the best solution. And that is not always an algorithm. – Gridley

@Daniel Dyson. If I needed them in a real world problem, the solutions would definitely be stored - but to me the spirit of this question was "how could you optimise this algorithm?" It's a nasty thing to go searching for, though, as they are spread so thinly, even compared to prime numbers. – Chemulpo

My apologies I tend to only deal in the real world. :) – Gridley

Answer 1

Use the formula

testPerfect = 2n-1(2n - 1)

to generate possiblities then check wether the number is in fact perfect.

try this for some bedtime reading

Negrillo

+1, but note that this wouldn't find any odd perfect numbers (should such numbers exist). Not a problem in this case, though. – Fluorspar

@Fluorspar how did you get the superscript? – Negrillo

Look at the source: <sup> is one of the whitelisted HTML tags, but you have to use <pre> instead of a 4-space-indent code block, since the latter shows HTML tags literally – Fluorspar

I used that generation formula coupled with a check for number % 9 == 1; :) Thanks! – Execration

for those interested about balpha's comment an odd perfect number has a lower bound of 10**1500. If that isn't hard enough to deal with they also have a crazy list of requirements they would need to meet see en.wikipedia.org/wiki/Perfect_number#Odd_perfect_numbers. – Jermainejerman

Answer 2

Do perfect numbers change? No. Look here. Surely, they should be calculated once and then stored. In your case, the only results will be

6
28
496
8128

The next one is 33550336. Outside your range.

Gridley

Answer 3

Just the obvious one from me: you don't need to check every divisor. No point looking for divisors past inputNo/2. That cuts down half of the calculations, but this is not an order of magnitude faster.

Chemulpo

Answer 4

One way to solve things like this involves building a huge array in memory of every number, and then crossing numbers out.

Hoenack

Answer 5

if your still looking for something to calculate perfect numbers. this goes through the first ten thousand pretty quick, but the 33 million number is a little slower.

public class Perfect {
private static Perfect INSTANCE = new Perfect();

public static Perfect getInstance() {
    return INSTANCE;
}

/**
 * the method that determines if a number is perfect;
 * 
 * @param n
 * @return
 */
public boolean isPerfect(long n) {
    long i = 0;
    long value = 0;
    while(++i<n){
        value = (0 == n%i?value+i:value);
    }
    return n==value;
}
}

Taliesin

Answer 6

For anyone interested in a LINQ based approach, the following method worked quite well and efficiently for me in determining whether or not a caller supplied integer value is a perfect number.

bool IsPerfectNumber(int value)
{
    var isPerfect = false;

    int maxCheck = Convert.ToInt32(Math.Sqrt(value));
    int[] possibleDivisors = Enumerable.Range(1, maxCheck).ToArray();
    int[] properDivisors = possibleDivisors.Where(d => (value % d == 0)).Select(d => d).ToArray();
    int divisorsSum = properDivisors.Sum();

    if (IsPrime(divisorsSum))
    {
        int lastDivisor = properDivisors.Last();
        isPerfect = (value == (lastDivisor * divisorsSum));
    }

    return isPerfect;
}

For simplicity and clarity, my implementation for IsPrime(), which is used within IsPerfectNumber(), is omitted.

Cortez

Answer 7

To continue from Charles Gargent's answer there is a very quick way to check if a Mersenne Number a.k.a. 2^n - 1 is prime. It is called the Lucas-Lehmer test The basic pseudocode though (taken from the Wikipedia page) is:

// Determine if Mp = 2p − 1 is prime for p > 2
Lucas–Lehmer(p)
    var s = 4
    var M = 2p − 1
    repeat p − 2 times:
        s = ((s × s) − 2) mod M
    if s == 0 return PRIME else return COMPOSITE

Almatadema