asked on

Printing Perfect numbers

I'm doing a science fair project to find out how to calculate and print at least the first 5 perfect numbers on java running on a MSDOS window. A perfect number is a positive integer n if it is equal to the sum of all of its positive divisors, excluding n itself. Euclid found the formula: If [(2^n)-1] is a prime number,
then [(2^n)-1] * 2^(n-1) is perfect.

My approach is
1. Start with 1, and then keep doubling this number
2. Every time and after each double, minus 1.
3. Check if the number that was minused 1 is a prime number
4. If the doubled number minus 1 is a prime number then multiply that prime number by the previously doubled number to obtain the perfect number.
5. The output should read: This number is perfect: 6
This number is perfect: 28 and etc.

For example; 1, 2, 4 (- 1) = 3 {which is prime}). So; 3 * {last doubled number} 2 = 6, which is the first perfect.
Some background information can be found at:
http://amicable.homepage.dk/perfect.htm
http://home1.pacific.net.sg/~novelway/MEW2/lesson1.html
Perfect numbers get large very quickly. The first few perfect numbers are:
1. 2^1*[(2^2)-1) = 6
2. 2^2*[(2^3)-1) = 28
3. 2^4*[(2^5)-1) = 496
4. 2^6*[(2^7)-1)] = 8128
5. 2^12*[(2^13)-1)] = 33550336
6. 2^16*[(2^17)-1)] = 8589869056
To date, there are 43 discovered perfect numbers.

At this point in my program I need a prime checker and I need to know how to multiply backwards. Please explain this to me and help me to understand where it should fit in my program and how and why it will work.
Attached is my program. Please help me the project is due Monday, January 2, 2006 and I have been struggling with this for many weeks. I am in the 8th grade and have taken two intro to programming classes.

Here is my program:

public class projecthelp {
      public static void main(String[] args) {
            int num = 10;
            int num2 = 1;
            int num3;
            int num4;
            while (num >=1) {
                  num2 = (num2*2);
                  num3 = num2-1;
                  System.out.println(num3+"\n"+num2+"\n");
                  num4 = num3*num2;
                  System.out.println("="+num4+"\n");
                  num--;
            }
      }
}

modsiw

This is homework, so I hope this isn't to much of an answer. You've put in the effort, so I personally feel it's deserved.

For reasonably small numbers, the following is a decent algorithm:

if n > 1
{
int index = 2
boolean isPrime = true
while (n / index => index and isPrime) //maybe do some recursion here if you have the time
{
if the remainder of n / index equal to 0 then isPrime is false //test each integer to see if it can devide it, if it can break the loop
increment index
}
}
return isPrime

The first part of the while loop test helps cut down on time. A square root type of test will also work.

PS:
If you want to see something really nifty, look up euclid's GCD fuction.

modsiw

"I need to know how to multiply backwards"

I don't understand what you are looking for? ( divide? >=) )

bloodredsun

There's also the BigInteger.isProbablePrime(int certainty) method which might be of use is you want to extend this into the larger numbers.

InteractiveMind

This will work for the first 5:

public class T
{
public static void main(String[]a)
{
int n = Integer.parseInt( a[0] ) ;
int m = 3 ;

int found = 0 ;
boolean done = false ;

while ( ! done )
{
if ( isPrime( m ) )
{
int r = (int ) (Math.pow( 2, m-1 ) * ( Math.pow( 2, m ) - 1 )) ;
System.out.println( r ) ;
found ++ ;
}
m++ ;
if ( found >= n )
done = true ;
}
}

public static boolean isPrime( int n )
{
for ( int i=2; i<n; i++ )
{
if ( ((double)n/(double)i) % 1 == 0 )
return false ;
}
return true ;
}

}

To run it, pass the number of perfect numbers you wish it to output, as a parameter--for example:

java T 5

To extend into numbers beyond the fifth perfect number, then look into bloodredsun's suggestion, of using BigInteger.

[If you need me to explain any of the logic behind my code, just say].

Good luck

tapion

ASKER

thank you all for your responses but im only a newby to Java (i think that personally). also i dont really want to change my code and use someone else's because im trying to do this for myself to see if i can do it. the problem im having really is that i am multiplying the wrong pairs of numbers. if u look in my code, each print out is grouped in a pair of two numbers and then under them is what they equal multiplied. my only problem (and what i men by "multiplied backwards") is that, for example, 3*4=12, but i dont want 3*4, i want 3*2 (thats the multiplying backwards part) cuz 3*2=6, which is the first perfect number.

I need the prime checker because, unlike what im doing now (which is just multiplying foward and multiplying every number) once i minus 1 from a number i need to check if that number is prime or not or else im just wasting time multiplying numbers together that wont equal a perfect number. only if its prime do i then multiply that number by the last doubled number to get a perfect number.

so can any body help me to make a SIMPLE prime checker and help me to "
multiply backwards" without changing the code i have now.

InteractiveMind

>> i need to check if that number is prime or not
You can use this method from my code:

public static boolean isPrime( int n )
{
for ( int i=2; i<n; i++ )
{
if ( ((double)n/(double)i) % 1 == 0 )
return false ;
}
return true ;
}

It will iterate through all positive integers, from 2 onwards. It will divide the given number by each number, and decide whether the result is an integer.

If it is an integer (a whole number), then mod 1 of it will equal 0--in which case, it's not a prime number, and false is returned.. otherwise, it'll return true.

tapion

ASKER

could i just input that right into my code? and if i can, does it matter where i do it? im not that experienced using methods. i have troubling getting them to work for me.

InteractiveMind

So long as it's within the class scope, and not within any other method--then yeah.

Your code with that method in, would look like:

public class projecthelp {
public static void main(String[] args) {
int num = 10;
int num2 = 1;
int num3;
int num4;
while (num >=1) {
num2 = (num2*2);
num3 = num2-1;
System.out.println(num3+"\n"+num2+"\n");
num4 = num3*num2;
System.out.println("="+num4+"\n");
num--;
}
}

public static boolean isPrime( int n )
{
for ( int i=2; i<n; i++ )
{
if ( ((double)n/(double)i) % 1 == 0 )
return false ;
}
return true ;
}
}

You've still got to make use of it, within your main method however.. but it's now available for use..

tapion

ASKER

how would i use that with in my main method. im really not the good at Java, like im a newb really, so could u maybe show me or explain to me how to use that within my code. like how to tie it all together? please

InteractiveMind

Well, an example of use:

int m = 32425 ;

if ( isPrime( m ) )
{
// It's a prime number
} else
{
// It's not a prime number
}

But I think that you need to sort the logic of this first:

int num = 10;
int num2 = 1;
int num3;
int num4;
while (num >=1) {
num2 = (num2*2);
num3 = num2-1;
System.out.println(num3+"\n"+num2+"\n");
num4 = num3*num2;
System.out.println("="+num4+"\n");
num--;
}

I don't entirely follow the logic of it...

tapion

ASKER

i dont want to sound annoying but im only in the 8th grade and im not really following some of the stuff ur writing out for me. sorry i dont want to be annoying.

ASKER CERTIFIED SOLUTION

InteractiveMind

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

tapion

ASKER

never mind. i got it now. thank you