Project Euler is awesome, part 2

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

Here is Problem # 12:

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

Here is the Java solution to this problem:

public class Problem012 {
 
 static private long findPrimeFactors(long number, Long[] primelist) {
     int numOfFactors = 1;
     int exponent;
     long remain = number;
  
     for (int i = 0; i < primelist.length; i++) {
         if (primelist[i] * primelist[i] > number) {
             return numOfFactors * 2;
         }
  
         exponent = 1;
         while (remain % primelist[i] == 0) {
             exponent++;
             remain = remain / primelist[i];
         }
         numOfFactors *= exponent;
  
         //If there is no remainder, return the count
         if (remain == 1) {
             return numOfFactors;
         }
     }
     return numOfFactors;
 }
 
 
 public static void findNumber(int count) { 
  
  long startTime = System.nanoTime();
  
  long number = 1;
  long i = 2;
  long cnt = 0;
  long factorCount1 = 2;
  long factorCount2 = 2;
  
  Long[] primes = runEratosthenesSieve(1000);
  
  while (cnt < count) {
   if (i % 2 == 0) {
    factorCount2 = findPrimeFactors(i + 1, primes);
    cnt = factorCount2 * factorCount1;
   } else {
    factorCount1 = findPrimeFactors((i + 1) / 2, primes);
    cnt = factorCount2*factorCount1;
   }
   i++;
  }
  number = i * (i - 1) / 2;
  long elapsedTime = (System.nanoTime() - startTime) / 1000000; // ms
  
  System.out.println("The number with five hundred divisors is " + number + " time took to find it : " + elapsedTime + " ms");
 }
 
 
 public static void findNumberV2(int count) { 
  
  long startTime = System.nanoTime();
  
  long number = 1;
  long i = 2;
  long cnt = 0;
  
  Long[] primes = runEratosthenesSieve(1000);
  
  while (cnt < count) {
   number += i++;
   cnt = findPrimeFactors(number, primes);
  }

  long elapsedTime = (System.nanoTime() - startTime) / 1000000; // ms
  
  System.out.println("The number with five hundred divisors is " + number + " time took to find it : " + elapsedTime + " ms");
 }

 static public Long[] runEratosthenesSieve(int upperBound) {
  ArrayList<Long> listPrim = new ArrayList<Long> ();
  
  int upperBoundSquareRoot = (int) Math.sqrt(upperBound);
  boolean[] isComposite = new boolean[upperBound + 1];
  for (int m = 2; m <= upperBoundSquareRoot; m++) {
   if (!isComposite[m]) {
            //System.out.print(m + " ");
    listPrim.add(new Long(m));
    for (int k = m * m; k <= upperBound; k += m)
             isComposite[k] = true;
   }
  }
     
  for (int m = upperBoundSquareRoot; m <= upperBound; m++) {
   if (!isComposite[m]) {
    listPrim.add(new Long(m));
   }
  }
  return listPrim.toArray(new Long[listPrim.size()]) ;
 }


 

 public static void main(String[] args) { 

  findNumber(500);
  findNumberV2(500);
 }
}

When you run the code, you will find out the method findNumber() is more efficient than findNumberV2()

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.