Archived

This topic is now archived and is closed to further replies.

Nibbles

is x a perfect number?

Recommended Posts

Hi, I''m trying to write a program that will check to see if the user inputed variable is a perfect number. this is basically what I have so far, but I''m getting weird results:
  
long number;
long i, j;
int d=0;
long divisor[] = new long[1000];

// loop through answers

for (j=1;j<number;j++)
{
	// loop through divisors

	for (i=1;i<number;i++)
	{
		if ((number / i) == j && j < number)
		{
			divisor[d] = j;
			d++;
		}
	}
}
  
All this does, is loop through all possible divisors, check to see if number divided by i will equal j, and if so, make divisor[d] = j. I''m not sure that makes too much sense, but if you think you might be able to help me, please do. Thanks, Scott

Share this post


Link to post
Share on other sites
You'll find some interesting information on Perfect numbers here. Pay special attention to the Euclidean theorem later completed by Euler that says

If 2k - 1 is prime, then 2k-1 (2k - 1) is perfect and every even perfect number has this form.

The existence of odd perfect numbers is still unconfirmed. If you find one, you might end up a celebrity.

Edit: formatting.

Edited by - Oluseyi on October 29, 2001 2:16:50 PM

Share this post


Link to post
Share on other sites
The following code determines the perfection of a number.

    
bool isPerfect (double x) {
double j, t = 1;
for (j = floor(sqrt(x)); j > 1; --j)
if (x == floor(x / j) * j)
t += j + floor(x / j);
if (t == x)
return true;
return false;
}


Note that the loop starts from sqrt(x). This makes the loop run in sqrt(n) time, rather than n time. When a divisor is found we add not only the divisor, but x/divisor. This is because if x is divisible by n, it must be divisible by x/n.

With 6, for example, the loop starts at 2, which 6 is divisible by, so we add 2 and 6/2 - 3 - to the total. The final result is 6. Thus, 6 is perfect.

It's pretty fast. I haven't done any proper timing tests on it, but it can determine the perfection of 8589869056.0 without any noticable pause.

I'd be interested to know why you need to test the perfection of a number.

'Nuff said. I'll enjoy watching you live, demon.

Edit: Fixed a barrel-load of typos.

Edited by - Mayrel on October 29, 2001 3:29:37 PM

Share this post


Link to post
Share on other sites
wow, that looks a lot better than I was doing it, however I''m using Java for this, and i''m not sure what the equivalent of floor is in java, whether it even exists.

I''m writing this for a computer science class. I''m basically just writing some functions of different math formulae/techniques that nobody likes doing by hand.

Thanks,
Scott

Share this post


Link to post
Share on other sites
Java has lots of commonly used math functions, including floor in the Math package. Floor is given by double Math.floor ( double ). See http://java.sun.com/j2se/1.3/docs/api/java/lang/Math.html

Share this post


Link to post
Share on other sites
In case anyone was wondering: floor(x) returns the nearest integer that is less than or equal to x. So floor(2.3) and floor(2.7) are both 2. The opposite is ceil(x), which returns the nearest integer that is greater than or equal to x. ceil(2.3) and ceil(2.7) are both 3.

Share this post


Link to post
Share on other sites
quote:
Original post by wojtos
I'm using Java for this, and I removed the floor functions, and it still works fine for any numbers I've tried.

but thanks, and good to know.
Scott


Wouldn't using the mod function be slightly easier? Perhaps more efficient?

Java:
  
boolean isPerfect(double x)
{
double check = 1;
for (double j = Math.floor(Math.sqrt(x)); j > 1; j--)
{
check += ((x % j) == 0) ? j + (x / j) : 0;
}

return (check == x);
}



Edited by - Spinal Confusion on October 29, 2001 4:56:58 PM

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
What is a perfect number?


A number is perfect if the sum of all of its divisors, excluding itself, is itself. ie:

6 has divisors of 1, 2, and 3.
6 = 1 + 2 + 3
6 is a perfect number

4 has divisors of 1 and 2
4 != 1 + 2
4 is not a perfect number

Share this post


Link to post
Share on other sites
quote:
Original post by Spinal Confusion
Wouldn't using the mod function be slightly easier? Perhaps more efficient?



Yes, you're right. On Java, that would be a good way to go. On C++, the long doesn't have enough range to check 8589869056. That's why I had to use doubles (oddly, it didn't work with singles, either). So, I had to use floor, since in truncating to a long I would have lost data, and the result would be wrong.

No, I think that the second floor isn't needed in C/C++, since sqrt(8589869056) will definately fit in a long. Although the sum variable would still need to be a double (but that doesn't effect the floor). And, of course, if you know that your compiler has a 64-bit integer, you can use that. (long long in gcc, __int64 in VC++, I think)

Ahem. Neither floor is needed in C/C++, since sqrt(8589869056) will definately fit in a long, so we can safely truncate in both cases. Doh

Java's long is much bigger (in fact, a whole 32-bits bigger) than C++'s long, so it'd work just fine with that. Indeed, you can get rid of the Math.floor that's still left in, by defining everything as a long.

Edit: Brainfart the First.
Edited by - Mayrel on October 30, 2001 7:18:11 AM

Edit: Brainfart the Second.

Edited by - Mayrel on October 30, 2001 7:20:25 AM

Share this post


Link to post
Share on other sites
quote:
Original post by Null and Void
You should try to avoid floor in C/C++. You can easily duplicate it by truncating to an integer, which takes much less time. On x86 CPU''s floor can take over 100 clockcycles due to alterations of the FPU''s rounding mode.



Surely the FPU is used to truncate the float when it''s cast to long or int or whatever? Indeed, since the FPU has to construct a integer when truncating, it seems to me that casting should take longer, because it''s a floor followed by a conversion.

Not that I don''t believe you; I''m quite familiar with the x86''s idiosynchronies, so it wouldn''t surprise me.

As an side, on gcc, integer shift is slower than integer division unless you have optimisation turned on. Whether that''s an x86 thing, a gcc thing or just a thing with my copy of gcc, I don''t know.

''Nuff said. I''ll enjoy watching you live, demon.

Share this post


Link to post
Share on other sites