I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler:Perfect Numbers

04.11.2013
| 3771 views |
  • submit to reddit

Thursday is code puzzler day here at DZone. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

Do you have code puzzlers that you'd like to share with the DZone community?  If so, please submit here. 

Find The First 20 Perfect Numbers

The definition of a perfect number, from Wikipedia, states:

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). Equivalently, a perfect number is a number that is half the sum of all of its positive divisors (including itself) i.e. σ1(n) = 2n.

So, the first perfect number is 6, since 1+2+3 = 6. 

With this information, your task is to write a method that will find the first 20 perfect numbers.


Catch up on all our previous puzzlers here.

 

Comments

Vijay Nathani replied on Thu, 2013/04/11 - 1:06pm

Groovy 

def isPerfect(number) { ((1..<number).sum { number % it? 0: it } ) == number }
assert isPerfect(6)

sun east replied on Thu, 2013/04/11 - 7:19pm in response to: Vijay Nathani

I think your code is too slow to solve the first 20 perfect numbers.

sun east replied on Thu, 2013/04/11 - 7:47pm

Here is my codes in scala using the known result that 2p−1(2p−1) is an even perfect number whenever 2p−1 is prime:


/**
pm: all prime numbers
pt: all perfect numbers
Give the first 20 perfect numbers take about 1 min.
*/
val pm: Stream[Int] = 2 #:: Stream.from(3).filter(n => pm.takeWhile(p => p*p <= n).forall(n%_ != 0))
val pt = for(p <- pm;x = BigInt(2).pow(p)-1;if x isProbablePrime 20) yield x*BigInt(2).pow(p-1)
for(p <- pt.take(20)) println(p)

Pieter van der Meer replied on Fri, 2013/04/12 - 10:20am

A long version in Java, can be optimized but result is verified.

public class PerfectNumber {

  public static void main(String[] args) {
  PerfectNumber perfectNumber = new PerfectNumber();

  List<Long> numbers = perfectNumber.get(20);

  System.out.println("perfectNumber = " + numbers);
  }

  public List<Long> get(final int size) {
  List<Long> numbers = new ArrayList<Long>();
  BigInteger p = BigInteger.ZERO.nextProbablePrime();
  while (numbers.size() < (size-1)) {
  if (isMersennePrime(p.longValue())) {
  System.out.println("Found factor for 'p' = " + p);
  numbers.add(calculate(p.intValue()));
  }
  p = p.nextProbablePrime();
  }

  return numbers;
  }

  long calculate(int p) {
  return (long) (Math.pow(2, p - 1) * (Math.pow(2, p) - 1));
  }

  boolean isMersennePrime(long p) {
  return lucasLehmer((int)p);
  }

  public static boolean lucasLehmer(int p) {
  BigInteger s = BigInteger.valueOf(4);
  BigInteger m = BigInteger.valueOf(2).pow(p).subtract(BigInteger.ONE);
  for (int i = 0; i < p - 2; i++)
  s = s.multiply(s).subtract(BigInteger.valueOf(2L)).mod(m);

  return s.equals(BigInteger.ZERO);
  }
}

Pieter van der Meer replied on Fri, 2013/04/12 - 10:26am in response to: sun east

 Did not run this one, but based on my own solution i think the at least 5th answer is incorrect. Just checking prime is not enough. p=11,23,29 and some more do not result in a perfect number :-(

sun east replied on Fri, 2013/04/12 - 11:39am in response to: Pieter van der Meer

Actually it is correct, you can look this page  for more information, and of course you can run my code yourself to check the result.

Eric Bennion replied on Thu, 2013/04/18 - 12:03pm in response to: Pieter van der Meer

When I ran your code, I verified that it found all 20 of the values of p.  What I then found was that once the numbers reached the limit of BigInteger, it repeated that number for the remaining values.  I made some adjustments and used BigDecimal and had success in matching the Wiki page of Perfect numbers.

import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

public class PerfectNumber {

	public static void main(String[] args) {
		long begin = System.currentTimeMillis();
		PerfectNumber perfectNumber = new PerfectNumber();

		List<BigDecimal> numbers = perfectNumber.get(20);

		System.out.println("perfectNumber = " + numbers);
		long end = System.currentTimeMillis();
		System.out.println((end-begin) / 1000 + " seconds");
	}

	public List<BigDecimal> get(final int size) {
		List<BigDecimal> numbers = new ArrayList<BigDecimal>();
		BigInteger p = BigInteger.ZERO.nextProbablePrime();
		while (numbers.size() < (size - 1)) {
			if (isMersennePrime(p.longValue())) {
				System.out.println("Found factor for 'p' = " + p);
				numbers.add(calculate(p.intValue()));
			}
			p = p.nextProbablePrime();
		}

		return numbers;
	}

	BigDecimal calculate(int p) {
		BigDecimal d = new BigDecimal(2);
		BigDecimal f1 = (d.pow(p - 1));
		BigDecimal f2 = (d.pow(p).subtract(new BigDecimal(1)));
		return (f1.multiply(f2));
	}

	boolean isMersennePrime(long p) {
		return lucasLehmer((int) p);
	}

	public static boolean lucasLehmer(int p) {
		BigInteger s = BigInteger.valueOf(4);
		BigInteger m = BigInteger.valueOf(2).pow(p).subtract(BigInteger.ONE);
		for (int i = 0; i < p - 2; i++)
			s = s.multiply(s).subtract(BigInteger.valueOf(2L)).mod(m);

		return s.equals(BigInteger.ZERO);
	}
}

Bob Beechey replied on Thu, 2013/04/25 - 5:56pm

Checking a sequence of numbers for their divisors would produce a program that would take days to run. Checking that any number n and 2^p - 1 are both prime takes an age using home-grown naïve prime tests but is an almost bearable time using probabilistic techniques (as in BigInteger library in Java or primepy in Python). The best times use the Lucas Lehmer test as in Eric Bennion and Peter van der Bier showed above. Here is the same algorithm in Python

from pyprimes import isprime
from time import clock

def lucas_lehmer(n,m):
    s = 4
    for j in range(1,n-1):
        s = ((s*s)-2)%m
    return s == 0
   
num = 3
result = 1
print(result, '=', 2, '-->', 6)
clock()
while result<20: 
    if isprime(num):
        calc1 = 2 ** (num - 1)
        calc2 = 2*calc1 - 1
        if lucas_lehmer(num,calc2):
            result += 1
            print(result, '=', num,  '-->', calc1 * calc2)
    num += 2
print (int(clock()), "seconds")

 

However, the exercise is then not really finding perfect numbers but rather finding Mersenne primes. If we assume knowledge of such primes, we get the fastest solution

 

result = 0
primelist = [2, 3, 5, 7, 13, 17, 19, 31,
             61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423]
for prime in primelist:
    calc = 2 ** (prime - 1)
    result += 1
    print(result, "-->", calc *(2 *calc - 1))

 

Wissem Belguidoum replied on Fri, 2013/05/03 - 9:46pm

In Java : 

/** 
  * Two rules are used to optimize the calculations: 
  *  - a divisor of a an odd number must be odd.
  *  - inside isPerfect() function, if the sum of divisors becomes superior than the number, then stop and return false.
  */
public class PerfectNumbers {
	private static final BigInteger TWO = BigInteger.valueOf(2l); 
	public static void main(String[] args) {
		
		int counter = 0;
		Long ms = System.currentTimeMillis();
		for (BigInteger n=TWO; counter < 20; n=n.add(BigInteger.ONE)) {
			if (isPerfect(n, isEven(n))) {
				System.out.println("Found : " + n +  " (" +  (System.currentTimeMillis() - ms) + " ms)");
				counter++;
				ms = System.currentTimeMillis();
			}
		}
	}
	
	private static boolean isPerfect(BigInteger n, boolean iseven) {
		BigInteger divisor = BigInteger.ONE;  
		BigInteger sum = BigInteger.ZERO; 

		while (divisor != null) {
			sum = sum.add(divisor); 
			if (sum.compareTo(n) > 0) return false;
			divisor = nextDivisor(n, divisor, iseven);
		}
		
		return sum.equals(n); 
	}

	private static BigInteger nextDivisor(BigInteger n, BigInteger previous, boolean iseven) {
		BigInteger inc = BigInteger.ONE; 
		if (!iseven) inc = TWO; 
		for (BigInteger divisor =  previous.add(BigInteger.ONE); divisor.compareTo(n) < 0; divisor = divisor.add(inc) ) {
			if (n.mod(divisor).equals(BigInteger.ZERO)) {
				return divisor; 
			}
		}
		return null;
	}
	
	private static boolean isEven(BigInteger n) {
		return n.mod(TWO).equals(BigInteger.ZERO);
	}
}

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.