Project Euler is cool, awesome

Project Euler is cool,  awesome. Solutions to the problems force me to come with efficient algorithms.

Here is one example:

The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form 269725931; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2p1, have been found which contain more digits.

However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: 28433*2^7830457+1.

Find the last ten digits of this prime number.

Here is the code:

  public static void main(String[] args) {
   long start = System.nanoTime() ;
   long value = 1;
   long LIMIT = 10000000000l;
   for (int i = 1 ; i <=7830457 ; i++) {
    value = value * 2;
    value =value%LIMIT;
   }
   value = value * 28433;
   value =value%LIMIT;
   value = value + 1 ;
   value =value%LIMIT;
   
   long end = System.nanoTime() ;
   System.out.println("result = " + value);
   System.out.println("computation time = " + ( (end - start) / 1000 ) + " ms");
  }

See, the solution is short and very efficient.

Here is another one:

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

Triangle T(n)=n(n+1)/2 1, 3, 6, 10, 15, ...

Pentagonal P(n)=n(3n-1)/2 1, 5, 12, 22, 35, ...

Hexagonal H(n)=n(2n-1) 1, 6, 15, 28, 45, ...

It can be verified that T(285) = P(165) = H(143) = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

/**

http://projecteuler.net/problem=45
 
Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

Triangle   T(n)=n(n+1)/2   1, 3, 6, 10, 15, ...
Pentagonal   P(n)=n(3n-1)/2 1, 5, 12, 22, 35, ...
Hexagonal   H(n)=n(2n-1)   1, 6, 15, 28, 45, ...

It can be verified that T(285) = P(165) = H(143) = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

 * 
 * @author lei zou
 *
 */
public class Problem045 {
 
 private static final BigInteger TWO = new BigInteger("2");

 static public BigInteger[] setTriangleArray(int base, BigInteger[] triangles) {
  for (int i=1; i<=triangles.length; i++) {
   BigInteger n = new BigInteger( Integer.toString(i+base) );
   BigInteger n2 = new BigInteger( Integer.toString( (i+base)+1) ) ;
   triangles[i-1] = n.multiply(n2);
   triangles[i-1] = triangles[i-1].divide(TWO);
  }
  //System.out.println("Triangle is " + Triangle[Triangle.length-1] );
  return triangles;
 }

 static public BigInteger[] setPentagonalArray(int base, BigInteger[] pentagonals) {
  for (int i=1; i<=pentagonals.length; i++) {
   BigInteger n = new BigInteger( Integer.toString(i+base) );
   BigInteger n2 = new BigInteger( Integer.toString( ( 3* (i+base) -1 ) )  ) ;
   pentagonals[i-1] = n.multiply(n2);
   pentagonals[i-1] = pentagonals[i-1].divide(TWO);
  }
  //System.out.println("Pentagonal is " + pentagonals[pentagonals.length-1] );
  return pentagonals;
 }

 static public BigInteger[] setHexagonalArray(int base, BigInteger[] hexagonals) {
  for (int i=1; i<=hexagonals.length; i++) {
   BigInteger n = new BigInteger( Integer.toString(i+base) );
   BigInteger n2 = new BigInteger( Integer.toString( ( 2* (i+base) -1 ) )  ) ;
   hexagonals[i-1] = n.multiply(n2);
   
  }
  return hexagonals;
 }

 
 public static void main(String[] args) {
  int limit = 1000;
  BigInteger[] Triangle = new BigInteger[limit];
  BigInteger[] Pentagonal = new BigInteger[limit];
  BigInteger[] Hexagonal = new BigInteger[limit];
  
  setTriangleArray(0, Triangle);
  setPentagonalArray(0, Pentagonal);
  setHexagonalArray(0, Hexagonal);

  int cnt=0;
  int upperTriangle=limit, upperPentagonal=limit, upperHexagonal=limit;
  int lowTriangle=0, lowPentagonal=0, lowHexagonal=0;
  int i=0, j=0, k=0;
  BigInteger max = new BigInteger("0");
  while (cnt<3) {
   while (i<upperTriangle && j<upperPentagonal && k<upperHexagonal) {
    if (Triangle[i-lowTriangle].equals(Pentagonal[j-lowPentagonal]) 
      && Pentagonal[j-lowPentagonal].equals(Hexagonal[k-lowHexagonal]) ) {
    
     System.out.print( (cnt+1) + "th" + " number is " + Triangle[i-lowTriangle] );
     System.out.println(" Triangle index: " + (++i) + " Pentagonal index: " + (++j) + " Hexagonal index: " + (++k) );
     cnt++;
    
    }
    max = Triangle[i-lowTriangle].compareTo( Pentagonal[j-lowPentagonal] ) > 0  ? Triangle[i-lowTriangle] : Pentagonal[j-lowPentagonal]; 
    max = Hexagonal[k-lowHexagonal].compareTo(max) > 0  ? Hexagonal[k-lowHexagonal] : max;
    // 
    while (i<upperTriangle && Triangle[i-lowTriangle].compareTo(max) <0  ) i++;
    while (j<upperPentagonal && Pentagonal[j-lowPentagonal].compareTo(max)<0  ) j++;
    while (k<upperHexagonal && Hexagonal[k-lowHexagonal].compareTo(max)<0  ) k++;
   }
   //System.out.println("Triangle: " + (i) + " Pentagonal: " + (j) + " Hexagonal: " + (k) + " max " + max );
   if (i==upperTriangle) { 
    lowTriangle = i;
    setTriangleArray(i, Triangle);
    upperTriangle+=Triangle.length;
   }
   if (j==upperPentagonal) {
    lowPentagonal = j;
    setPentagonalArray(j, Pentagonal);
    upperPentagonal += Pentagonal.length;
   }
   if (k==upperHexagonal) {
    lowHexagonal = k;
    setHexagonalArray(k, Hexagonal);
    upperHexagonal += Hexagonal.length;
   }
  }
 }
}

Not sure that is the best solution. But it does solve the problem.