perfect number contest

[php_brian]

Here's is a contest I'm proposing to everyone. I haven't managed to pull off a script that will do it, so I'm wondering what others can do in many different langauges. I probably can do it easily with PHP, but a compiled language would be much quicker. I've attempted it with C and C++, but failed LOL.

Goal: Write a program that will find all perfect numbers within a set range. The range will always begin at 1 and can go as high as you want. For this contest the high range will be 1,000,000.

Objective: For your program to be as fast possible and with the most accuracy.

If you don't know what a perfect number is then let me explain. A perfect number is a number that all of its factors excluding itself add up to the number. So for example the first and most simple perfect number is 6. Factors of 6 include 1, 2, and 3. 1+2+3=6.

Ok, so I've given you one perfect number. I'm not sure of how many there are between 1 and 1,000,000. That's for your script to find out. I only know of 4 perfect numbers, but a computer can calculate them much faster.

[rambo6376]

Hey, I'm new here. I read the sticky on contests but how do you submit them? like do you just post the solution here? Anybody already figure this out?

[php_brian]

Yeah, I do believe you copy and paste your code to the board. Since there hasn't been many repiles, I'm wondering if this a difficult problem or people just are not participating?

[MJPhill]

Here's some messy Java for you:

    public class PerfectNumbers {
    
       public static long perfect(int k) {
         boolean isPrime = false;
         long number = (long)Math.pow(2, k) - 1;
         if (number % 2 == 1) {
            isPrime = true;
            for (int i = 3; i < number; i+=2) {
               if ((number % i) == 0) {
                  i = (int)number;
                  isPrime = false;
               }
            }
         }
         if (isPrime) {
            return (long)(Math.pow(2, k-1))*(long)(Math.pow(2, k)-1);
         }
         else {
            return -1;
         }
      }
   
       public static void main(String args[]) {
         System.out.println("Perfect numbers up to 1000000:");
         long perfectNum;
         for (int k = 2; k <= 20; k++) {
            perfectNum = perfect(k);
            if (perfectNum != -1) {
               System.out.print(perfectNum + "\t");
            }
         }
      }
   }

[brendandonhue]

I wrote PHP that can check if a number is a perfect number, but its crappy code (I won't bother posting it). If ya looped it up to 1,000,000, the server would probably crash.

[MJPhill]

I did that as well initially and then realized just how poor and inefficient my approach was :P.

[php_brian]

My attempted approach to this was to loop 1 to 1 million. Dynamically create an array to hold factors, call a function to find all the factors of the numbers store them in that array. Then add them and check if it is equal to the number. Then it would delete the array and when it looped over again it would re-create the array using dynamic memory allocation. seems logically.

[brendandonhue]

Mine was much less efficient
Ill be back on that comp this weekend, ill post the code for laughs. But don't look at the code if you have a weak stomach, im warning you its really bad.

[DNAunion2000]

php_brian: Goal: Write a program that will find all perfect numbers within a set range. The range will always begin at 1 and can go as high as you want. For this contest the high range will be 1,000,000.

...

If you don't know what a perfect number is then let me explain. A perfect number is a number that all of its factors excluding itself add up to the number. So for example the first and most simple perfect number is 6. Factors of 6 include 1, 2, and 3. 1+2+3=6.

/*DNAunion*/ Those seem like contradictory specifications to me. The only factor of 1 is itself - 1 - but we aren't to include the number itself in the list of factors of the number, so there are no factors. 1 is the only number this problem occurs for. Then why should the range of numbers to check for "perfection" begin at 1? I started at 2.

Checking up through 10000 my code found the following four perfect numbers:

6
28
496
8,128

lnMaxNumb = 10000

CLOSE ALL
CLEAR
CREATE CURSOR c_factors (factor N(10))
FOR lnLcv = 2 TO lnMaxNumb
	DELETE FROM c_factors
	GetAllFactors(lnLcv)
	CALCULATE SUM(factor) TO lnSumOfFactors
	IF (lnSumOfFactors = lnLcv)
		? lnLcv
	ENDIF
ENDFOR
CLOSE ALL


FUNCTION GetAllFactors(lnNumber)
	LOCAL lnDivisor
	FOR lnDivisor = 1 TO FLOOR(lnNumber / 2)
		IF (lnNumber % lnDivisor = 0)
			INSERT INTO c_factors (factor) VALUES (lnDivisor)
		ENDIF
	ENDFOR
ENDFUNC

/*DNAunion*/ Oh yeah, that Visual FoxPro code. And yeah, the algorithm for GetAllFactors() could probably be coded more efficiently, but at this point I was more interested in finding perfect numbers than in creating the perfect algorithm.

[DNAunion2000]

/*DNAunion*/ MJPhill, I spent a couple of minutes looking over your code and I am not sure how it is supposed to be a solution to the problem posed. Could you explain its logic?

[MJPhill]

I used Euclid's algorithm for finding perfect numbers:

For some k>1, (2^(k-1))*(2^(k)-1) is a perfect number if 2^(k)-1 is prime.

So I basically check to see if (2^(k)-1) is prime and if it is I return the multiplied result. I was pretty tired when I coded this though and did end up making an error in my driver, I calculated the values of the first 7 perfect numbers up to 137438691328 .

[DNAunion2000]

/*DNAunion*/ Oh yeah, that Visual FoxPro code. And yeah, the algorithm for GetAllFactors() could probably be coded more efficiently, but at this point I was more interested in finding perfect numbers than in creating the perfect algorithm.

/*DNAUnion*/ I “independently rediscovered” an optimization for finding all factors of a number n.

In the original method, I realized there is no need to check numbers larger than n / 2.

(1) If a number (> 2) is divisible by 2, then the largest factor of that number (other than itself) is n / 2. For example, 100 is divisible by 2 so the greatest factor of 100 (not including itself) is 100 / 2 = 50. So there’s no need to check numbers above 50.

(2) If a number (> 2) is not divisible by 2, then the largest factor of that number (other than itself) is < n / 2.

Or to put it another way, factors come in pairs (hey, sounds like Mendel!). Since the smallest factor we need to look at is 2 (ignoring 1, which is a special case), the largest factor we need to look at is its complement n / 2.

Thus, my loop started 1 and processed every integer up to n / 2. This is an optimization over trying every number less than n.

However, as I was trying to go to sleep, I tried to figure out an optimization on the original. First I thought about the rules for divisibility. For example, a number is divisible by 3 if the sum of its digits is itself divisible by 3. That’s how we humans quickly tell whether a number like 352671 is divisible by 3…it’s quicker than dividing and checking the remainder. However, this doesn’t work for code. First, the number would have to be parsed into its individual digits, which would likely be done by performing % 10 once for each digit in the number, then all of those digits would have to be summed, then that result would itself have to be checked to see if it was divisible by 3: recursion. That all would take many more steps and more time to do than simply testing number % 3 = 0. Furthermore, all of that logic would work only for divisibility by 3. Furthermore, conditional branching would need to be used in order to determine which rule to use for the potential factor currently being examined. Furthermore, the rule for divisibility by 6 is that a number is divisible by 6 if it is divisible by both 2 and 3, which means that the results of previous divisibility tests would need to be stored and a search performed through that list of factors for both 2 and 3. That too would take more time than just trying number % 6 = 0. Finally, what’s the shortcut rule for divisibility by 13, or 17, or 23, or 57?

So I concluded that there is no way to optimize the determination for individual potential factors…the loop simple must run from 1 to "x" testing each value: number % potentialfactor = 0. The only possible optimization is reducing the range of numbers - lowering "x" - that needs to be checked. And that’s where the little light bulb went off: PAIRS of factors.

Instead of saving as a factor only the number being tested, the algorithm should store both it and its complement factor. What’s the benefit? Let’s look at 100.

In the original, I would try from 1 to 100 / 2. That’s 50 tests. But in reality only 10 are needed. Notice the trend in the following factor pairs.

1 100
2 50
4 25
5 20
10 10

While the first number – the potential factor being checked – increases, the second number – its complement factor – decreases: they approach each other. At some point, the two either meet or pass one another. At that point, there is no need to check any more numbers. For example, there is no need to check 11 because if 100 were divisible by 11 we would already know that from the second numbers since 11 would be within the second number’s range. So when we check every number less than x, the we are also implicitly checking every number > x, where x is some number where the two expanding factor lists meet or spill over into the each other. What then is x? It’s the square root of number.

Thus the optimization is:

1) Store both the factor being checked and its corresponding complementary factor
2) Only check potential factors up through and including floor(number^-2)

This is a big savings when dealing with numbers like 1,000,000. In the original method, n / 2 = 1000000 / 2 = 500,000 potential factors need to be checked. In the optimized version, only n^-2 = 1,000,000^-2 = 1,000 potential factors need to be checked.

By the way, although I deduced this strictly from logic, once I had I realized that the conclusion is well known in math. That’s why I said that I “independently rediscovered” the concept. Another similarity with Mendel's work????

So here’s the new, optimized solution.

lnMaxNumb = 10000

CLOSE ALL
CLEAR
CREATE CURSOR c_factors (factor N(10))
FOR lnLcv = 2 TO lnMaxNumb
	DELETE FROM c_factors
	GetAllFactors(lnLcv)
	CALCULATE SUM(factor) TO lnSumOfFactors
	IF (lnSumOfFactors = lnLcv)
		? lnLcv
	ENDIF
ENDFOR
CLOSE ALL


FUNCTION GetAllFactors(lnNumber)
	LOCAL lnDivisor
	FOR lnDivisor = 1 TO FLOOR(SQRT(lnNumber))
		IF (lnNumber % lnDivisor = 0)
			INSERT INTO c_factors (factor) VALUES (lnDivisor)
			IF (lnDivisor != lnNumber / lnDivisor)
				INSERT INTO c_factors (factor) VALUES (lnNumber / lnDivisor)
			ENDIF
		ENDIF
	ENDFOR
ENDFUNC

/*DNAunion*/ I thought of one more optimization.

We don’t need a cursor or any method of storing the individual factors: that only wastes memory and CPU cycles. The values have to be stored, then later run through to get a sum, and then later discarded. Why not cut out the middle men and just accumulate the sum of the factors as they are found?

lnMaxNumb = 10000

CLOSE ALL
CLEAR
FOR lnLcv = 2 TO lnMaxNumb
	IF (SumAllFactors(lnLcv) = lnLcv)
		? lnLcv
	ENDIF
ENDFOR
CLOSE ALL


FUNCTION SumAllFactors(lnNumber)
	LOCAL lnDivisor, lnSum
	lnSum = 1
	FOR lnDivisor = 2 TO FLOOR(SQRT(lnNumber))
		IF (lnNumber % lnDivisor = 0)
			lnSum = lnSum + lnDivisor
			IF (lnDivisor != lnNumber / lnDivisor)
				lnSum = lnSum + (lnNumber / lnDivisor)
			ENDIF
		ENDIF
	ENDFOR
	RETURN lnSum
ENDFUNC

/*DNAunion*/ That’s my final form (kind of like Frieza!). It is MUCH MUCH faster than my original.

PS: I extended my search all the way up to the competitions maximum - 1,000,000. The only 4 perfect numbers for that range are as follows (the same ones I listed in my earlier post):

6
28
496
8,128

[php_brian]

It does matter if you start at 1 or 2. I said 1 becuase it's not 0.

[Tygur]

Is this contest still alive and well? No posts for several days..

I came up with some VB.NET code that eats up memory like there's no tomorrow, but I think it might be relatively quick, assuming you have the available memory. It took 85 seconds on my computer.

If 85 seconds is long, then I figure I won't bother posting it..

EDIT: I've gotten it down to 45 seconds..

[MJPhill]

My code computes the first 7 perfect numbers (up to 137438691328) in an average of 32 milliseconds on my computer.

[php_brian]

Tygur, please do post your code.

[Tygur]

Originally posted by MJPhill
My code computes the first 7 perfect numbers (up to 13743869132 in an average of 32 milliseconds on my computer.

I figured your code would be quite fast, because it uses what seems to be a very efficient algorithm.

I aimed to go the simpler route of outright checking the factors, but I wanted to find a quick way of doing that. I don't know if the code already here took the approach I'm about to decribe, but it seemed out-of-the-box enough to possibly be unique.

I looped through all the numbers that could be factors of the numbers in our range (1 through 1,000,000). That means looping through the numbers from 1 to 1,000,000/2. As I think someone might've already alluded to (not sure), any number greater than half of 1,000,000 cannot be a factor of 1,000,000 or anything less than it, because they would have to be multiplied by something less than two to arrive at 1,000,000. Basically, I was looping through the factors and determining what they were factors of. After that, It was a simple matter of looping through an array and adding factors to determine whether each number was "perfect". Each element of the array corresponded to a number from 1 to 1,000,000 and contained the factors for the associated number.

Another optimization I took advantage of was I didn't check any odd numbers for perfectness. This is because, upon research, I found out that there may not even be any odd perfect numbers, and if there are, they are greater than 1E+300 (a 1, followed by 300 zeros).

So, with that said, here it is. It's written as a VB.NET Console App:

Module Module1
    'method 1 is more efficient
    'method 2 makes poor use of the TestNumbers array in an effort to reduce the amount of calculations required
#Const METHOD = 1
    Const MaxTestNumber As Integer = 1000000
    Sub Main()
        Dim StartTime As DateTime = Now
        Const MaxFactor As Integer = MaxTestNumber \ 2
        'We will only test even numbers from 2 to MaxTestNumber as candidates for perfect numbers
#If METHOD = 1 Then
        'Index I in TestNumbers corresponds to the number (I+1)*2
        Dim TestNumbers((MaxTestNumber \ 2) - 1) As ArrayList
#ElseIf METHOD = 2 Then
        'Index I in TestNumbers corresponds to the number I
        Dim TestNumbers(MaxTestNumber) As ArrayList
#End If
        'fill TestNumbers with arraylists
        Console.WriteLine("Generating ArrayLists...")
        Dim I As Integer
#If METHOD = 1 Then
        For I = 0 To TestNumbers.Length - 1
#ElseIf METHOD = 2 Then
        For I = 2 To TestNumbers.Length - 1 Step 2
#End If
        TestNumbers(I) = New ArrayList()
        Next
        'ok, what we're gonna do is determine all the factors for all the testnumbers
        Console.WriteLine("Listing factors...")
        Dim Factor As Integer
        Dim FactorOf As Integer
        Dim EvenFactor As Boolean = True
        For Factor = 1 To MaxFactor
            EvenFactor = Not EvenFactor
            FactorOf = Factor + Factor
            If FactorOf Mod 2 = 1 Then
                FactorOf += Factor
            End If
            Do Until FactorOf > MaxTestNumber
#If METHOD = 1 Then
                TestNumbers(FactorOf \ 2 - 1).Add(Factor)
#ElseIf METHOD = 2 Then
                TestNumbers(FactorOf).Add(Factor)
#End If
                If EvenFactor Then
                    FactorOf += Factor
                Else
                    FactorOf += Factor * 2
                End If
            Loop
        Next
        'all factors are generated.  now let's find the perfect numbers
        Console.WriteLine("Seeking perfect numbers...")
        Dim TestNumber As Integer = 0
        Dim AddedFactors As Integer
#If METHOD = 1 Then
        For I = 0 To TestNumbers.Length - 1
#ElseIf METHOD = 2 Then
        For I = 2 To TestNumbers.Length - 1 Step 2
#End If
        TestNumber += 2
        AddedFactors = 0
        For Each Factor In TestNumbers(I)
            AddedFactors += Factor
        Next
        If AddedFactors = TestNumber Then
            Console.WriteLine("Perfect Number: " & TestNumber)
        End If
        Next
        Dim StopTime As DateTime = Now
        'we're done
        Console.WriteLine("Done.")
        'display the amount of time it took
        Dim Secs As Integer = DateDiff(DateInterval.Second, StartTime, StopTime)
        Console.WriteLine("It took " & Secs & " seconds.")
        Console.Write("Press ENTER to quit.")
        Console.ReadLine()
    End Sub
End Module

[MJPhill]

Another optimization I took advantage of was I didn't check any odd numbers for perfectness. This is because, upon research, I found out that there may not even be any odd perfect numbers, and if there are, they are greater than 1E+300 (a 1, followed by 300 zeros).

You may also be interested to know, for further optimization, that research shows that all perfect numbers end in either a 6 or an 8.

*******The following is something that I thought up pretty much out of the blue while reading Tygur's post. I know that the whole idea is really a rather dumb, novice coder thing probably, but I thought someone may find it interesting. I apologize for wasting your time if you find this completely moronic.*********

However, I think that it is probably good for one to deviate from standard mathematical algorithms designed to obtain certain numbers at times. After all, most algorithms are based on theroems that, although widely accepted as absolute truth, could potentially be proved false. At one time it was thought that the last digit in sequential perfect numbers alternated between 6 and 8, however it was later shown that there was no such pattern. Without someone's initial will to deviate from this once accepted theory, quite a few perfect numbers would never have been discovered.

So what I'm basically getting at here is my view of the word "effecient." While my algorithm may by the commonly accepted definition of the word, be more "efficient" than Tyger's, I think that its obvious that his algorithm is much more thorough. Potentially (though honestly unlikely), my algorithm could eventually compute a false perfect number or skip over one, as it never performs any tests other than Euclid's algorithm. Tygur's code on the other hand uses the true definition of a perfect number to test whether the number is one or not. Therefore, in my mind, his code is more efficient, as it iterates through the whole series of positive integers searching for all possible occurences of perfect numbers. My code is simply faster because it uses known shortcuts in the process of finding perfect numbers. By searching through the entire series, you are accounting for the fact that Euclid's algorithm could possibly ignore some instances of perfect numbers or even calculate incorrect occurences. Therefore, Tygur's program must be much more efficient at finding numbers that are truely perfect, while my program is much better at finding theoretical perfect numbers quickly.

[Tygur]

I took my previous code and made it much better. Method 2 wasn't offering much improvement, so I took it out. Also, I did away with the ArrayLists and made my own FactorList class. In doing so, I reduced the time down to 7 seconds.

Here is the new code:

Module Module1
    Const MaxTestNumber As Integer = 1000000
    Sub Main()
        Dim StartTime As DateTime = Now
        Const MaxFactor As Integer = MaxTestNumber \ 2
        'We will only test even numbers from 2 to MaxTestNumber as candidates for perfect numbers
        'Index I in TestNumbers corresponds to the number (I+1)*2
        Dim TestNumbers((MaxTestNumber \ 2) - 1) As FactorList
        'fill TestNumbers with FactorLists
        Console.WriteLine("Generating FactorLists...")
        Dim I As Integer
        For I = 0 To TestNumbers.Length - 1
            TestNumbers(I) = New FactorList()
        Next
        'ok, what we're gonna do is determine all the factors for all the testnumbers
        Console.WriteLine("Listing factors...")
        Dim Factor As Integer
        Dim FactorOf As Integer
        Dim EvenFactor As Boolean = True
        For Factor = 1 To MaxFactor
            EvenFactor = Not EvenFactor
            FactorOf = Factor + Factor
            If FactorOf Mod 2 = 1 Then
                FactorOf += Factor
            End If
            Do Until FactorOf > MaxTestNumber
                TestNumbers(FactorOf \ 2 - 1).Add(Factor)
                If EvenFactor Then
                    FactorOf += Factor
                Else
                    FactorOf += Factor * 2
                End If
            Loop
        Next
        'all factors are generated.  now let's find the perfect numbers
        Console.WriteLine("Seeking perfect numbers...")
        Dim TestNumber As Integer = 0
        Dim AddedFactors As Integer
        For I = 0 To TestNumbers.Length - 1
            TestNumber += 2
            AddedFactors = TestNumbers(I).GetSum
            If AddedFactors = TestNumber Then
                Console.WriteLine("Perfect Number: " & TestNumber)
            End If
        Next
        Dim StopTime As DateTime = Now
        'we're done
        Console.WriteLine("Done.")
        'display the amount of time it took
        Dim Secs As Integer = DateDiff(DateInterval.Second, StartTime, StopTime)
        Console.WriteLine("It took " & Secs & " seconds.")
        Console.Write("Press ENTER to quit.")
        Console.ReadLine()
    End Sub
End Module

Class FactorList
    Const InitialSize As Integer = 50
    Const SizeJump As Integer = 50
    Dim Size As Integer = InitialSize
    Dim Count As Integer
    Dim Factors(InitialSize - 1) As Integer
    Sub Add(ByVal I As Integer)
        If Count = Factors.Length Then
            Size += SizeJump
            ReDim Preserve Factors(Size - 1)
        End If
        Factors(Count) = I
        Count += 1
    End Sub
    Function GetSum() As Integer
        Dim I As Integer
        Dim Sum As Integer = 0
        For I = 0 To Count - 1
            Sum += Factors(I)
        Next
        Return Sum
    End Function
End Class

[DNAunion2000]

/*DNAunion*/ I translated my VFP code into C++, including manually "inlining" the function code to eliminate any overhead associated with 1,000,000 function calls (actually, I tried it both ways and they took the same amount of time). PS: After I pasted the code another optimization came to me, which shaved 3 seconds off the total (dropping from 17 seconds to 14).

#include <iostream>
#include <cmath>
#include <ctime>

using std::cout;
using std::endl;
using std::cin;

int main()
{
	const int maxNumb = 1000000;
	char userInput[80];
	int sum, largestFactor, divisor;
	double started, ended;

	started = time(0);
	for (int lcv = 2; lcv < maxNumb; ++lcv)
	{
		sum = 1;
		largestFactor = (int)sqrt((double)lcv);
		for (divisor = 2; divisor <= largestFactor; ++divisor)
		{
			if (lcv % divisor == 0)
			{
				sum += divisor;
				if (divisor * divisor != lcv)
					sum += (lcv / divisor);
			}
			if (sum > lcv) break;
		}
		if (sum == lcv) cout << lcv << endl;
	}
	ended = time(0);

	cout << "Process took " << ended - started << " seconds." << endl;
	cout << "Enter a character to quit." << endl;
	cin.getline(userInput, 1, '\n');
	return 0;
}

That took 14 seconds.

What I don't get is how tygur's VB code - which stores factors in a 500,000 element array and then later goes back and sums those factors, not to mention 500,000 class instantiations, and overall looks "bulky" - can be way more efficient than my low overhead C++ code. What am I missing? Or is it probably just a difference in PC throughput?