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 :sick:
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 :laugh:.

[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 137438691328) 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?

[DNAunion2000]

/*DNAunion*/ Well, I found that my code is faster than tygur's, if I too borrow someone else's knowledge.

You see, as I thought was appropriate for a competittion, I created my algorithm from scratch, completely by myself. I didn't let Euclid do most of the work and then simply coopt his method, nor did I investigate to see what mathematical shortcuts could be taken before coding. Not that either is cheating (on a job, there's surely no penalty for using outside information) it's just not what I thought the competition was about.

Anyway, after taking into account that odd numbers don't need to be checked, my C++ code completed in 5 seconds.

[Tygur]

I had an amazing revelation. I was doing it all wrong. The FactorList class wasn't even needed. I don't know why I didn't see this sooner. My code has now been modified so that it takes about 0.95 seconds on my computer. The key is to add the factors together right away instead of storing them up to be added later.

Here is the new code:
Module Module1
Const MaxTestNumber As Integer = 1000000
Sub Main()
Dim StartTime As Integer = Environment.TickCount
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 Integer
'ok, what we're gonna do is determine all the factors for all the testnumbers and add them in
Console.WriteLine("Listing and adding factors...")
Dim I As Integer
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) += 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
For I = 0 To TestNumbers.Length - 1
TestNumber += 2
If TestNumbers(I) = TestNumber Then
Console.WriteLine("Perfect Number: " & TestNumber)
End If
Next
Dim StopTime As Integer = Environment.TickCount
'we're done
Console.WriteLine("Done.")
'display the amount of time it took
Dim Secs As Single = (StopTime - StartTime) / 1000
Console.WriteLine("It took " & Math.Round(Secs, 2) & " seconds.")
Console.Write("Press ENTER to quit.")
Console.ReadLine()
End Sub
End Module

[MJPhill]

Well, I found that my code is faster than tygur's, if I too borrow someone else's knowledge. You see, as I thought was appropriate for a competittion, I created my algorithm from scratch, completely by myself. I didn't let Euclid do most of the work and then simply coopt his method, nor did I investigate to see what mathematical shortcuts could be taken before coding. Not that either is cheating (on a job, there's surely no penalty for using outside information) it's just not what I thought the competition was about.

To be honest with you, I did write code initially that resembled your own, DNAunion2000(I'd post it but I don't think it would be of any interest at all to anyone), but I did do research aftewards, revealing a much better algorithm for finding perfect numbers and ended up changing my algorithm accordingly. After all, is a competetion not about completing the task at hand in the fastest/best way possible.

Had someone already used this algorithm in solving this problem, I would have definately wrote code using a different approach, as I see no use in posting the same type of solution twice. While you may feel that my code is invalid as it uses unoriginal code, I felt that it was the best solution for the problem at hand at the time. In my mind, the best programmer is the laziest programmer, as there's no sense in reinventing the wheel if its already out there and has taken the test of time.

[DNAunion2000]

/*DNAunion*/ After further research, I found other numbers that don't need to be checked. My algorithm now takes 0 seconds to complete the task, and is 100% accurate!


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

using namespace std;

void isItAPerfectNumber(const int & lcv);

int main()
{
char userInput[80];
time_t started, ended;

started = time(0);
isItAPerfectNumber( 6 );
isItAPerfectNumber( 28 );
isItAPerfectNumber( 496 );
isItAPerfectNumber( 8128 );
ended = time(0);

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

void isItAPerfectNumber(const int & lcv)
{
int sum = 1, largestFactor;
largestFactor = (int)sqrt((double)lcv);
for (int divisor = 2; divisor <= largestFactor; ++divisor)
{
if (lcv % divisor == 0)
{
sum += divisor;
if (divisor * divisor != lcv)
sum += (lcv / divisor);
}
}
if (sum = lcv) cout << lcv << endl;
}

[MJPhill]

:biglaugh::biglaugh::biglaugh::biglaugh:


Holy crap, that is amazing. The human race is now in your debt for the ground breaking research you have done.

[Tygur]

Originally posted by DNAunion2000
/*DNAunion*/ After further research, I found other numbers that don't need to be checked. My algorithm now takes 0 seconds to complete the task, and is 100% accurate!
Well, I could presumably write some code that just writes the numbers out without even checking them first, because my research shows that those are them beyond any doubt.

I'm too lazy to write the code, but i was the first to present the algorithm, so it's mine :P


Seriously, tho, changing code to check odd numbers will prolly just double the time length for both codes, which won't change the results, so it's not really an issue, i think..

[DNAunion2000]

MJPhill: Holy crap, that is amazing. The human race is now in your debt for the ground breaking research you have done.

/*DNAunion*/ And I'm not even done yet!

Upon further research I found that a famous mathematician has already worked out an extremely effificient method of determining if a given number is a perfect number. And since the best programmer is the laziest programmer, my next optimization will be to be lazy and simply coopt his already worked out algorithm (instead of actually having to think out how to do it myself). That will make my program even faster!

[DNAunion2000]

Tygur: Well, I could presumably write some code that just writes the numbers out without even checking them first, because my research shows that those are them beyond any doubt.

/*DNAunion*/ That would be listing perfect numbers, not finding them (as required by the competition's parameters).

Besides, I don’t get it…are you complaining about my method of eliminating most even numbers from consideration? Why? You did the same thing for odd numbers, after all.

The logic behind “your” optimization was, “why spend time checking 500,000 numbers that we somehow already know aren’t perfect?”. The logic behind my optimization was, “why spend time checking 499,996 numbers that we somehow already know aren’t perfect?”. Doesn’t seem like a huge difference to me.

Tygur: I'm too lazy to write the code…

/*DNAunion*/ That’s good, because, according to MJPhill, being lazy is a part of being a great programmer.

Tygur: … but i was the first to present the algorithm, so it's mine

/*DNAunion*/ Smiley face or not, here are two reasons why that fails.

1) You’ve TWICE implicitly agreed that it is okay to use other people’s ideas
MJPhill co-opted Eulcid’s preexisting algorithm and used it as the ESSENTIAL CORE of his program, and I don’t seem to see any complaints about that by you. Not even after I brought up the point. So your silence in that instance indicates that co-opting someone else’s ideas is fine by you.

But there’s more to MJPhill's co-option vs mine: his involves a much greater degree than mine.

If you remove Euclid’s contribution from MJPhill's program, MJPhill's program completely breaks down and can't do squat as far as finding perfect numbers. In a sense, MJPhill's program IS Euclid's algorithm.

On the other hand, I added "Tygur's optimization" (or whoever's it actually belong to) to my already completely functional code as a SMALL, NONESSENTIAL part of my program. If you remove "Tygur's optimization" from my program, my code STILL works 100%.

Here's the simple logical change to my code, which involves a slight modification to a single statement in the for loop header: lcv += 1 became lcv += 2. That’s it. Go back to the original and the code still functions perfectly. Remove Euclid’s algorithm from MJPhill’s program and his program is dead in the water.

Now as far as the second time you've agreed that using other people's ideas is fine. As my next point shows, you used my ideas to improve your code, so surely you don’t consider co-opting others ideas as being negative.


2) You co-opted my idea too
Your first attempts stored factors in an array, but then you stopped doing that and summed them on the fly: an optimization that I was the first to present, so it’s mine! Here are the relevant quotes.

Tygur: The key is to add the factors together right away instead of storing them up to be added later.

/*DNAunion*/ Amazing, considering that just two posts above that I had said:

/*DNAunion*/ 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?

/*DNAunion*/ With my accompanying C++ code in that post summing factors on the fly instead of storing them in a data container and then later going back and summing them.

In fact, look at what I stated even earlier in the thread.

/*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?

/*DNAunion*/ And Tygur, you DID read that post…we know this because you commented on another part of it.

Tygur: 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.

/*DNAunion*/ And that I stated in my same post where I stated – i.e., was the first to state - that storing factors in an array is wasteful.

/*DNAunion*/ 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.

…

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?


/*DNAunion*/ Considering those two points, it would be quite hypocritical of you to now gripe about my last program.



***************************
Let’s spend a couple minutes more comparing “Tygur’s optimization” (or whoever he borrowed it from) and mine.

Now, no one complained about "Tygur's optimization" (or whoever he borrowed it from) that ruled out all odd numbers - yep, ruled out 500,000 numbers from needing to be checked - but at least two people have “complained” about my optimization that rules out most even numbers??? Seems odd....here's the logical difference.


// considered acceptable
for (int lcv = 2; lcv <= MaxNumber; ++lcv)
{
/* "Tygur's optimization" - eliminate all odd numbers from consideration */
if (lcv % 2 != 0) continue;

isItAPerfectNumber(lcv);
}




// not considered acceptable?!
for (int lcv = 2; lcv <= MaxNumber; ++lcv)
{
/* "Tygur's optimization" - eliminate all odd numbers from consideration */
if (lcv % 2 != 0) continue;

/* DNAunion's optimization - eliminate most even numbers from consideration */
if (lcv != 6 && lcv != 28 && lcv != 496 && lcv != 8128 ) continue;

isItAPerfectNumber(lcv);
}


/*DNAunion*/ I don’t see a material difference.

Perhaps the problem is that those “complaining” aren't sharp enough to realize that the code I used in the post people are complaining about (see next code fragment) is logically equivalent to the preceding code block, but simply omits the overhead associated with pointless loop and checks.


isItAPerfectNumber( 6 );
isItAPerfectNumber( 28 );
isItAPerfectNumber( 496 );
isItAPerfectNumber( 8128 );


Tygur: Seriously, tho, changing code to check odd numbers will prolly just double the time length for both codes, which won't change the results, so it's not really an issue, i think..

/*DNAunion*/ Why not try it? Make that change, post the code, and how much it changed the elapsed time.

But, you see, in general, simply doubling n does not mean the algorithm will take twice as long to complete. It depends upon the big theta (or big O) value for the algorithm. Some scale up linearly with increasing values for n, others don’t. You have to analyze the algorithm to figure out – in the worst case – how many times each statement is executed relative to n and then come up with a function that describes the relationship. For example, f(n) = n; or f(n) = 1; or f(n) = n^2; or f(n) = 2^n; or f(n) = log 2 n. That will tell you overall how the algorithm scales with increasing values of n.

******************************
Actually, it’s kind of sad to see a group of programmers judging their algorithms’ efficiencies by simply running them on their own computer and then reporting the elapsed times, which are then compared. That’s not how it’s supposed to be done. And here’s one good reason why.

Tygur: My code has now been modified so that it takes about 0.95 seconds on my computer.

/*DNAunion*/ Yes, ON YOUR COMPUTER, which is meaningless by itself.

Computers can have different CPU speeds; computers can have different CPU architectures; computers can have different amounts of RAM; computers can have different speeds of RAM; computers can have different types of RAM; computers can have different OS's running; and so on. Having each person run his code on his own computer and then comparing the reported results is like comparing apples to oranges: practically meaningless.

For example, I copied your VB code and pasted it into my .NET IDE and then ran it. It took 3.42 seconds on my computer.

In other words, your computer is about 3.5 times as fast as mine. So if we both created an algorithm for solving problem X and ran them on our own computers, I could create an algorithm that was twice as efficient as yours, but yours would still complete in less time, thereby giving the false impression of your algorithm being more efficient.

[DNAunion2000]

/*DNAunion*/ Okay, I created a new algorithm to solve the problem. I just did a Google search using "perfect number" and the first hit I got had the logic Euclid used. So I translated it into C++ code.

My program finds all perfect numbers up to 1 million in 0 seconds, even on my slower-than-Tygur's computer.


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

using namespace std;

bool primeNumber(const long & lcv);

int main()
{
long MaxNumber = 1000000;
char userInput[80];
time_t started, ended;

started = time(0);
long sum = 1;
for (long addend = 2; sum * addend <= MaxNumber; addend *= 2)
{
sum += addend;
if (primeNumber(sum)) cout << sum * addend << endl ;
}
ended = time(0);

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

bool primeNumber(const long & lcv)
{
long largestFactor = (long)sqrt((double)lcv);
bool prime = true;
for (long divisor = 2; prime && divisor <= largestFactor; ++divisor)
{
if (lcv % divisor == 0) prime = false;
}
return prime;
}

[Tygur]

/*DNAunion*/ That would be listing perfect numbers, not finding them (as required by the competition's parameters).

Besides, I don’t get it…are you complaining about my method of eliminating most even numbers from consideration? Why? You did the same thing for odd numbers, after all.

The logic behind “your” optimization was, “why spend time checking 500,000 numbers that we somehow already know aren’t perfect?”. The logic behind my optimization was, “why spend time checking 499,996 numbers that we somehow already know aren’t perfect?”. Doesn’t seem like a huge difference to me.

First off, I admit that my optimization was questionable. I was prepared to remove it if anyone voiced complaints. But when you decided to use it in your own code, I figured everyone was accepting it, and I stopped worrying.

I justified it in my own mind, because I read that there might very well be no odd perfect numbers at all. If there are none below that enormously huge number I posted before, then it is quite likely that there are none above it, either. I was thinking maybe there was some undiscovered reason for it. Sort of like how there are no even prime numbers (though the reason for that is obvious).

the problem with your "optimization" is that you went and found the numbers ahead of time and only checked those. Your program never "found" them either. It just verified an already-compiled list that you yourself found.

If you don't like my optimization, I'm prepared to remove it.


Me: … but i was the first to present the algorithm, so it's mine
DNAunion: Smiley face or not, here are two reasons why that fails.
DNAunion: 1) You’ve TWICE implicitly agreed that it is okay to use other people’s ideas
DNAunion: 2) You co-opted my idea too

Ok, first off, that post was intended as a joke, because I had assumed (and hoped) that the post it was in response to was also a joke.

Also, the algorithm I was presenting was so simple, there was no part of it that could be taken out and used to improve some other bit of code. It was either all or none. And if I took your entire algorithm and posted it as my own, I'm sure that would've bothered you.

It is true that MJPhill used Euclid's algorithm as the basis of his code. I didn't complain because his was one of the first posts to the thread, and nobody else said anything. So I just assumed it was ok. Also, Euclid is dead. He can't get upset if his algorithm is copied and used here. However, MPhill might have something to say if someone else tried using the same algorithm, because he came up with the original idea of using Euclid's algorithm and made the first such submission to this contest.


/*DNAunion*/ And that I stated in my same post where I stated – i.e., was the first to state - that storing factors in an array is wasteful.
To be perfectly honest with you, I had no idea you ever said that. I must've missed it. I came up with the idea of simply summing on the fly when I was playing around with my code and converting it to C++ in an effort to speed it up. In the process of converting the code, it dawned on me that I was being so wasteful.


Now, no one complained about "Tygur's optimization" (or whoever he borrowed it from) that ruled out all odd numbers - yep, ruled out 500,000 numbers from needing to be checked - but at least two people have “complained” about my optimization that rules out most even numbers??? Seems odd....here's the logical difference.
You didn't just rule out "most even numbers". You ruled out every number that isn't a perfect number. That is the job of the program, not the programmer. While my optimization may have crossed the line, yours crosses it without a shadow of a doubt.


/*DNAunion*/ Why not try it? Make that change, post the code, and how much it changed the elapsed time.

But, you see, in general, simply doubling n does not mean the algorithm will take twice as long to complete. It depends upon the big theta (or big O) value for the algorithm. Some scale up linearly with increasing values for n, others don’t. You have to analyze the algorithm to figure out – in the worst case – how many times each statement is executed relative to n and then come up with a function that describes the relationship. For example, f(n) = n; or f(n) = 1; or f(n) = n^2; or f(n) = 2^n; or f(n) = log 2 n. That will tell you overall how the algorithm scales with increasing values of n.
That is very true. I admit that I was just making a very uneducated guess. That's why I said "probably" and "i guess". I wasn't certain at all. It was just a guess. Your code apparently dropped from 14 down to 5 by halving the amount of numbers checked.


With both our algorithms removing odd numbers, mine is apparently quicker, according to your results.

[Tygur]

Here is my code, now modified to check every single number instead of skipping odd ones. Feel free to time it yourself. On my computer, it took 1.09 to 1.14 seconds (I ran it several times).
Module Module1
Const MaxTestNumber As Integer = 1000000
Sub Main()
Dim StartTime As Integer = Environment.TickCount
Const MaxFactor As Integer = MaxTestNumber \ 2
'Index I in TestNumbers corresponds to the number I-1
Dim TestNumbers(MaxTestNumber - 1) As Integer
'ok, what we're gonna do is determine all the factors for all the testnumbers and add them in
Console.WriteLine("Listing and adding factors...")
Dim I As Integer
Dim Factor As Integer
Dim FactorOf As Integer
For Factor = 1 To MaxFactor
FactorOf = Factor + Factor
Do Until FactorOf > MaxTestNumber
TestNumbers(FactorOf - 1) += Factor
FactorOf += Factor
Loop
Next
'all factors are generated. now let's find the perfect numbers
Console.WriteLine("Seeking perfect numbers...")
Dim TestNumber As Integer = 0
For I = 0 To TestNumbers.Length - 1
TestNumber += 1
If TestNumbers(I) = TestNumber Then
Console.WriteLine("Perfect Number: " & TestNumber)
End If
Next
Dim StopTime As Integer = Environment.TickCount
'we're done
Console.WriteLine("Done.")
'display the amount of time it took
Dim Secs As Single = (StopTime - StartTime) / 1000
Console.WriteLine("It took " & Math.Round(Secs, 2) & " seconds.")
Console.Write("Press ENTER to quit.")
Console.ReadLine()
End Sub
End Module

EDIT: I just found out that a comment remained in the code that still said odd numbers were getting skipped, so I took it out..

[Tygur]

Originally posted by DNAunion2000
/*DNAunion*/ Okay, I created a new algorithm to solve the problem. I just did a Google search using "perfect number" and the first hit I got had the logic Euclid used. So I translated it into C++ code.

My program finds all perfect numbers up to 1 million in 0 seconds, even on my slower-than-Tygur's computer.
Didn't MJPhill already use Euclid's algorithm? You'll have to compare your speed with his code, rather than mine. My original goal was to find the quickest way of doing it the direct way (adding factors), and I believe I have succeeded in that. I figured MJPhill probably already had the fastest code, so I didn't even bother trying to beat it.

[DNAunion2000]

Tygur: Didn't MJPhill already use Euclid's algorithm?

/*DNAunion*/ If you'll look at our code you will see that we implemented Euclid's logic differently. In fact, the presentation of Euclid's method that MJPhill and I read apparently differ because our methods are so different.

In short, my new program was created without any reference to MJPhill's.

[DNAunion2000]

/*DNAunion*/ Okay, here's how I see the competition so far.

"I did it all by myself" category

It looks like we have two main entries: DNAunion and Tygur.

For accuracy, it's a tie. Each program checks all values needed to be checked and returns the proper results.

For originality, Tygur wins.

For memory efficiency, DNAunion wins.

For speed efficiency, Tygur wins ("normalizing" the elapsed times - by dividing my values by 3.6 since Tygur's computer is about 3.6 times as fast than mine - gives about 3.89 seconds for mine and 1.10 seconds for Tygur's).

Overall winner thus far: Tygur.

"I ripped off Euclid" category

It looks like we have two entries here: MJPhill and DNAunion. The two entires are very different - their only commonality is that they both let Euclid do the hard work.

For originality, they both score pretty low. The cores for both programs were obtained by looking up "perfect number" (either on the web or in a mathematics text) and then co-opting a preexisting algorithm.

For space efficiency, a quick look shows neither program using any aggregate variables (no arrays, lists, queues, etc.) and so to a first approximation, they are equivalent.

For speed efficiency, well, I can't compare the speed efficiencies because I don't know how to get fractional seconds (such as milliseconds) in C++ (The C++ time_t data type has a granularity of seconds. I've done some looking in the index of 3 C++ books and in the .NET online help for standard C++ and have yet to see anything that gets me milliseconds).

**************************
PS: In a hurry...don't have time to review the thread...going off memory of the people who have posted code recently.

[php_brian]

I almost have a TI-83 Plus version of DNAunion2000's algorithm working. I have the user enter the number to stop at and it trys to find the perfect numbers between 2 and that number. When I put 30 it only finds 6 and not 28. And the weird thing is, is when I look at the looping variable value it's at 2,000+. If anyone wants to see the code, tell me.

[DNAunion2000]

php_brian: I almost have a TI-83 Plus version of DNAunion2000's algorithm working. I have the user enter the number to stop at and it trys to find the perfect numbers between 2 and that number. When I put 30 it only finds 6 and not 28. And the weird thing is, is when I look at the looping variable value it's at 2,000+. If anyone wants to see the code, tell me.

/*DNAunion*/ First question is, which of my programs is involved? I've ended up with two main programs, but they are different, and the first one has evolved through several revisions.

I did notice a while back that in one version of my first one I used a < where I should have technically used a <= (in the for header). Under the conditions specified by the competition, that oversight produced no problems: since 1,000,0000 is not a perfect number. In fact, it wouldn't make a difference except in an extremely small fraction of cases (i.e., were someone happened to use a perfect number as the upper limit). I don't think this oversight is what is causing your copy of my program to miss 28 since you are using 30: the less than sign would check up through 29, finding 28.

In the below, I have corrected that one problem (that's the only change I made to #1). Here are my two programs.

My “roll your own” program, sluggish as it is. I just copied it back into the .NET IDE, recompiled it, and ran it. It did find all 4 perfect numbers less than or equal to 1,000,000.


#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);
// this was incorrect in my post, using lcv < maxNumb
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;
}



And my much-faster (thanks to Euclid) one:


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

using namespace std;

bool primeNumber(const long & lcv);

int main()
{
long MaxNumber = 1000000;
char userInput[80];
time_t started, ended;

started = time(0);
long sum = 1;
for (long addend = 2; sum * addend <= MaxNumber; addend *= 2)
{
sum += addend;
if (primeNumber(sum)) cout << sum * addend << endl ;
}
ended = time(0);

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

bool primeNumber(const long & lcv)
{
long largestFactor = (long)sqrt((double)lcv);
bool prime = true;
for (long divisor = 2; prime && divisor <= largestFactor; ++divisor)
{
if (lcv % divisor == 0) prime = false;
}
return prime;
}

[DNAunion2000]

/*DNAunion*/ Okay, to try to figure out if MJPhill's or mine was faster, I did some analysis. At least for the algorithm that determines whether or not a number is prime, mine is more efficient.

DNAunion’s code for determining whether or not a number is prime.

bool primeNumber(const long & lcv)
{
long largestFactor = (long)sqrt((double)lcv);
bool prime = true;
for (long divisor = 2; prime && divisor <= largestFactor; ++divisor)
{
if (lcv % divisor == 0) prime = false;
}
return prime;
}



MJPhill’s code for determining whether or not a number is prime.

boolean isPrime = false;
if (number % 2 == 1) {
isPrime = true;
for (int i = 3; i < number; i+=2) {
if ((number % i) == 0) {
i = (int)number;
isPrime = false;
}
}
}


NOTE: I have taken the liberty of removing one statement from MJPhill’s code since it is not part of determining whether or not a number is prime.

Let’s determine the number of statements executed relative to n for both mine and MJPhill’s.

DNAunion
1)long largestFactor = (long)sqrt((double)lcv);
This statement always executes exactly 1 time.

2) bool prime = true;
This statement always executes exactly 1 time.

The for loop needs to be broken down into individual statements: basically, converted into a while loop.

3) long divisor = 2
This statement always executes exactly 1 time.

4) prime && divisor <= largestFactor
This statement executes at most n^(1/2) times, in the worst case (This loop condition is checked one time more than the loop body executes because a final check produces false).

5) if (lcv % divisor == 0)
This statement executes at most n^(1/2) – 1 times, in the worst case.

6) prime = false;
This statements is never executed in the worst case scenario.

7) ++divisor
This statement executes at most n^(1/2) – 1 times, in the worst case.

8 ) return prime
This statement executes exactly 1 time

Adding those individual values up gives a total of 3n^(1/2) + 2 for my algorithm, so:
f(n) = 3n^(1/2) + 2


***********************************

MJPhill
1) boolean isPrime = false;
This statement executes exactly 1 time.

2) if (number % 2 == 1)
This statement executes exactly 1 time.

3) isPrime = true;
This statement executes exactly 1 time.

The for loop need to be broken down into individual statements: basically, converted into a while loop.

4) int 1 = 3;
This statement executes exactly 1 time.

5) i < number
This statement executes at most n/2 times, in the worst case (This loop condition is checked one time more than the loop body executes because a final check produces false).

6) if ((number % i) == 0)
This statement executes at most n/2 – 1 times, in the worst case

7) i = (int)number;
This statement never executes in the worst case

8 ) isPrime = false:
This statement never executes in the worst case

9) i += 2;
This statement executes at most n/2 – 1 times, in the worst case

Adding those individual values up gives a total of (3/2)n + 2 for MJPhill’s algorithm, so:
f(n) = (3/2)n + 2

****************************

Comparison: DNAunion vs MJPhill
As a method of comparing the two functions, the difference between 3n^(1/2) + 2 and (3/2)n + 2 is pretty easy to calculate. First, we can eliminate the + 2 from each giving 3n^(1/2) and (3/2)n. Next, simply restate his as 3n/2. Then we can divide both by 3 giving n^(1/2) vs n/2.

n^(1/2) < n/2 for all integers greater than 4, and as n increases, the gap between the two increases rapidly. Thus, with the exception of finding out if 2, 3, or 4 are prime numbers, my algorithm is more efficient.

*******************************

Each Overlooked an Optimization the other Used
As I was calculating the algorithmic complexity of my function I realized that I check even numbers that I don’t have to. For example, if a number is divisible by 2 then it’s not prime and the function terminates. If the number is not divisible by 2, then it cannot be divisible by 4, 6, 8, 10, 12, 14, 16, … Yet I check those numbers for being factors. I was going to optimize my code by checking for divisibility by 2 followed bv checking only odd numbers from there on out. But I noticed that MJPhill’s algorithm already does that. So I missed that optimization that he found,

On the flip side, MJPhill continues to check numbers way past the limit he needs to. To determine whether or not a number is prime, the highest factor that needs to be checked is the square root of that number: but MJPhill’s code checks all odds numbers up to and including the number itself. For example, consider the number 101. The highest number that needs to be checked for being a factor is 101^(1/2) = 10.0, or simply 10. Yet his code checks 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, …, 101. Thus MJPhill overlooked an optimization I found.

The two should be put together to achieve optimal efficiency.

Combined

bool primeNumber(const long & number)
{
long largestFactor = (long)sqrt((double)number);
bool prime = false;
if (number % 2 == 1)
{
prime = true;
for (long divisor = 3; prime && divisor <= largestFactor; divisor += 2)
{
if (number % divisor == 0) prime = false;
}
}
return prime;
}


1) long largestFactor = (long)sqrt((double)number);
This statement is executed exactly 1 time

2) bool prime = true;
This statement is executed exactly 1 time

3) if (number % 2 == 1)
This statement is executed exactly 1 time

4) prime = true;
This statement is executed exactly 1 time in the worst case

5) long divisor = 3
This statement is executed exactly 1 time in the worst case

6) prime && divisor <= largestFactor;
This statement executes at most n^(1/2)/2 times in the worst case

7) if (number % divisor == 0) prime = false;
This statement is executed at most (n^(1/2)/2) – 1 times in the worst case

8 ) divisor += 2;
This statement is executed at most (n^(1/2)/2) – 1 times in the worst case

9) return prime;
This statement executes exactly 1 time

Adding up the individual values gives (3/2)n^(1/2) + 4 for the combined code, so
f(n) = (3/2)n^(1/2) + 4

*********************************

Comparing all three with two test prime numbers
DNAunion: 3n^(1/2) + 2
MJPhill: (3/2)n + 2
Combined: (3/2)n^(1/2) + 4

Let’s use 101 as the prime number, and use three significant digits.

DNAunion: 3(101)^(1/2) + 2 = 3(10.0) + 2 = 32
MJPhill: (3/2)101 + 2 = 152 + 2 = 154
Combined: (3/2)(101)^(1/2) + 4 = (3/2)(10.0) + 4 = 15 + 4 = 19


Now let’s use 100,069 as the prime number (truncating decimals places).

DNAunion: 3(100069)^(1/2) + 2 = 3(316) + 2 = 950
MJPhill: (3/2)100069 + 2 = 150103 + 2 = 150,105
Combined: (3/2)(100069)^(1/2) + 4 = (3/2)(316) + 4 = 478

[MJPhill]

Well done sir!

I can't believe I forgot to only check up to the highest factor.

[hackermx3]

i dont think i've seen any java in here so ....


public class PerfectNumbers
{
public static void main(String args[])
{
final int NUM_FIND = 6; //Number of Perfects to find
int m = 2;
long primeToCheck = 0;
long factor = 0;
int found = 0;

System.out.println("Perfect Numbers");

while (found < NUM_FIND)
{
primeToCheck = (long)(Math.pow(2,m) - 1);

for (long digit = primeToCheck; digit > 0; digit--)
{
if (primeToCheck % digit == 0)
factor++;
}

if (factor == 2)
{
System.out.println((long)(Math.pow(2,m-1) * (Math.pow(2,m) - 1)));
found++;
}

factor = 0;
m++;
}
}
}


heres the output

Perfect Number:
6
28
496
8128
33550336
8589869056
Press any key to continue...



any suggestions?

[php_brian]

The first submission was Java.

[hackermx3]

yea ... my bad i didn't see it till just now

[jce1975]

How would you also find all the factors of each perfect number (in C)? I've been trying to figure this out, but I can't get it ... Thanks.

James

[ChefNinja]

In python (sloooooooow and only to 10,000):

#!/usr/bin/python
import time

class perfectNumber:

def getFactor(self, number):
n = 1
l = []
while n < number:
if number % n == 0:
l.append(n)
n = n + 1

return l

def checkPerfect(self, list, number):
x = 0
for item in list:
x = x + int(item)

if x == number:
return 'perfect'

x = perfectNumber()
n = 1
start = time.time()
while n <= 10000:
if x.checkPerfect(x.getFactor(n), n) == 'perfect':
print n, "is a perfect number"

n = n + 1
finish = time.time()
time = finish - start
print "Took %d seconds" % time


and the output:

c-67-172-176-26:~/Documents kevinherron$ ./perfectnumber.py
6 is a perfect number
28 is a perfect number
496 is a perfect number
8128 is a perfect number
Took 54 seconds


no point in trying to optimize it... looks like i'd just be borrowing all of your guys' ideas at this point :P

[silk.odyssey]

Find perfect numbers implemented with Randall Hydes High Level Assembler ( HLA ).


/*Calculate the perfect numbers between 1 and 1000
implemented with HLA ( High Level Assembler )
*/

program PerfectNumber;

#include ("stdlib.hhf")

//Print factors for num

procedure PrintFactors
(
num : dword in ebx
);
@noframe;
@noalignstack;

begin PrintFactors;

push( ecx );
push( ebx );

for( mov( 1, ecx ); ecx < ebx; inc( ecx )) do

mov( ebx, eax );

/* if ((num % i) == 0 ) */

mov( 0, edx );
div( ecx );

// edx holds the remainder
// after the division

if ( edx == 0 ) then

stdout.put
(
(type uns32 ecx),
", "
);

endif;

endfor;

pop( ebx );
pop( ecx );

ret();

end PrintFactors;

// Determines if num is a
// perfect number and
// returns true or false
// in al

procedure isPerfectNumber
(
num : dword in ebx
);
@returns( "al");
@noframe;
@noalignstack;

begin isPerfectNumber;

// preserve registers
// for reuse

// edi = sum
// ebx = number to test
// ebx = counter

push( edi );
push( ebx );
push( ecx );

mov( 0, edi );

for( mov( 1, ecx ); ecx < ebx; inc( ecx )) do

// copy number to eax
// on each iteration
// because eax is modified
// by div

mov( ebx, eax );

// if ((num % i) == 0 )

mov( 0, edx );
div( ecx );

// edx holds the remainder
// after the division

if ( edx == 0 ) then

// add factor to sum

add( ecx, edi );

endif;

endfor;

// compare sum of factors
// with the original number
// if the sum == number, return
// true by setting al to 1

cmp( edi, ebx );
setz( al );

pop( ecx );
pop( ebx );
pop( edi );

ret();

end isPerfectNumber;

begin PerfectNumber;

for( mov( 1, ecx ); ecx < 1000; inc( ecx )) do

isPerfectNumber( ecx );

if ( al == true ) then

PrintFactors( ecx );

stdout.put
(
"= ",
(type uns32 ecx),
nl

);

endif;

endfor;

end PerfectNumber;