2
\$\begingroup\$

Perfect numbers are strictly positive whole numbers of which the sum of their positive divisors equals a multiple of the number itself. An example of a 3-perfect number is 120. The sum of all divisors of 120, namely 1+2+3+4+5+6+8+10+12+15+20+24+30+40+60+120 = 360 equals three times 120.

My code does work, but it's not really efficient (if you have 2 very large number, it will take a very long time). Is there a more elegant way to solve this problem?

public class Main {

    public static void main(String[] args) {
        int number1 = 10;
        int number2 = 50;
        boolean found = false;
        int perfectNumber = 0;
        int multiplier = 0;
        for(int i = number1; i<=number2 && !found;i++){
            if(i%2==0){
                int somDivisors = lookSomeDivisors(i);
                if(somDivisors%i==0){
                    perfectNumber = i;
                    multiplier = somDivisors/i;
                    found=true;
                }
            }
        }
        System.out.println("Number1: " + number1 + " Number2: " + number2);
        System.out.println("PerfectNumber: " + perfectNumber + " Multiplier: " + multiplier);
    }

    private static int lookSomeDivisors(int number) {
        int som = 0;
        for(int i=1;i<=number;i++){
            if(number%i==0){
                som+= i;
            }
        }return som;
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ If the number is even, you could see if it has the form p*(p+1)/2 where p is a Mersenne prime. See en.wikipedia.org/wiki/Perfect_number. Of course that could be considered cheating. \$\endgroup\$ – ajb Dec 23 '14 at 16:35
3
\$\begingroup\$

Well, if you are interested in number-theoretical solutions, take a look at the wiki page referenced in one of the comments to your question. It does not apply directly to your problem, but you can lift some useful insights from it.

As to your "brute force" solution, first of all, note, that, when looking for divisors you only need to test values up to Math.sqrt(number), there is no need to go higher, because everything you can find there can be obtained easier by diving number by one of the divisors found so far.
Further, if a number is odd, it cannot have any even divisors, so once a test for number % 2 fails, there is no need to test 4 or 6 or 8 ... Same goes for other divisors: once you test and fail for number % 3, you can exclude 6, 9, 12 etc.

What this boils down to is that to find all divisors of a number you only need to test its divisibility by every prime number between 1 and Math.sqrt(number). If you find and hardcode a large enough list of first N primes, your program can be much faster, at least, for input numbers up to the last of your primes squared.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

From Wikipedia:

In number theory, a perfect number is a positive integer that is equal to the sum of its proper positive divisors, that is, the sum of its positive divisors excluding the number itself (also known as its aliquot sum).

The first perfect number is 6, because 1, 2, and 3 are its proper positive divisors, and 1 + 2 + 3 = 6. Equivalently, the number 6 is equal to half the sum of all its positive divisors: ( 1 + 2 + 3 + 6 ) / 2 = 6. The next perfect number is 28 = 1 + 2 + 4 + 7 + 14. This is followed by the perfect numbers 496 and 8128.

If you were to implement that algorithm the following can be used:

public boolean isPerfect(int number) {
    int sum = IntStream.rangeClosed(1, number - 1).filter(n -> number % n == 0).sum();
    return number == sum;
}

@Test
public void testPerfectNumber() {
    Assert.assertFalse(isPerfect(1));
    Assert.assertFalse(isPerfect(2));
    Assert.assertFalse(isPerfect(3));
    Assert.assertFalse(isPerfect(4));
    Assert.assertFalse(isPerfect(5));
    Assert.assertTrue(isPerfect(6));
    Assert.assertTrue(isPerfect(28));
    Assert.assertFalse(isPerfect(29));


    Assert.assertFalse(isPerfect(1000000));
}

Edit: added the code for the 3-perfect number.

So, to create the 3-perfect number the following code could be used:

public boolean isPerfect(int number, int divisor) {
    int sum = IntStream.rangeClosed(1, number).parallel().filter(n -> number % n == 0).sum();
    return sum / divisor == number;
}

The parallel-section can possibly make it faster depending on how many cores etc that is available on the computing machine.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ that's more or less exactly what he is doing ... \$\endgroup\$ – Dima Dec 23 '14 at 16:53
  • \$\begingroup\$ @Dima - yes, thanks - I forgot to add the parallel-part which is still a brute force solution but possibly faster. \$\endgroup\$ – wassgren Dec 23 '14 at 17:00
1
\$\begingroup\$

I'm a little confused as to why you did number1 and number2, but by following your logic I will define this as the problem:

"Find the first magic number between the range of two integers."

    public static void main(String[] args) {
        int number1 = 10;
        int number2 = 50;

        int firstPerfectNumber = findFirstPerfectNumber(number1, number2);
        //Found a perfect number, print it out
        if(firstPerfectNumber > 0){
            int multiplier = findSumOfDivisors(firstPerfectNumber) / firstPerfectNumber);
            System.out.println("First Perfect Number in range [" 
                + number1 + ", " + number2 + "] is " + firstPerfectNumber 
                + " Multiplier: " + multiplier); 
        }
        //No perfect number found, print Error
        else{
            System.out.println("Did not find a perfect number in range [" 
                + number1 + ", " + number2 + "]);
        }
    }

    public static int findFirstPerfectNumber(int begin, int end){
        int found = -1;
        //Make sure the starting index is even.  You cannot have odd perfect numbers
        if(begin % 2 == 1){
           begin++;
        } 
        //Only check even numbers, (i+=2 instead of i++)
        for(int i = begin; i <= end; i += 2){
            int sumOfDivisors = findSumOfDivisors(i);
            if(sumOfDivisors % i == 0){
                return i;
            }
        }
        //No perfect number found within this range, return -1
        return -1;
    }

    private static int findSumOfDivisors(int number) {
        int sum = 0;
        for(int i = 1; i <= number / 2; i++){
            if(number % i == 0){
                sum += i;
            }
        }
        return sum + number;
    }
}

Notes:

  • I made it a static function that returns an int for the first magic number. It returns -1 to indicate if not found. This function can be reused in many cases now, even outside of this class
  • You cannot have an odd Perfect Number, so I reflected the logic to do so. See how I stepped by 2 instead of one each time. This reduces loop overhead and avoids unnecessary calculations/if statements.
  • In findSumOfDivisors(int number), I improved your logic to make it more efficient. The next divisor after "number / 2" is that number. I excluded checking the range of (number / 2, number), and added the number to the resulting sum.
  • WORD CHOICE!: som: the basic monetary unit of Kyrgyzstan. some: an unspecified amount or number of. sum: the total amount resulting from the addition of two or more numbers. Understandable error if you are not a native English speaker, they are homophones (sound alike, different spelling and meaning).
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.