Tag Archive for 'factor'

Project Euler : First Triangle Number To Have Over Five Hundred Divisors

Published on January 27, 2010 in Problems. 0 Comments

This was solved by brute force. I implemented a method to find the number of factors of a number by its prime factorization. Having already built up a sieve method to quickly get primes, the number of factors can be found faster this way.

PrimeNumber class:

package pba.common.number;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;

public class PrimeNumbers {
	private List<Integer> m_primeNumbers;

	/**
	 * @param sizeOfSieve The upper bound to the determination of prime numbers.
	 */
	public PrimeNumbers(int sizeOfSieve) {
		m_primeNumbers = new ArrayList<Integer>();
		sieveOfEratosthenes(sizeOfSieve);
	}

	/**
	 * Calculates the number of factors for a given number by prime factorization. For example, <br>
	 * 28 = 2^2 * 7 <br>
	 * Thus the number of factors of 28 are (2+1)*(1+1) = 6.
	 *
	 * @param number The number whose number of factors are required
	 * @return The number of factors the given number has
	 */
	public int getNumberOfFactors(int number) {
		int numberOfFactors = 1;
		for (int prime : m_primeNumbers) {
			int exponent = 0;
			while (number % prime == 0) {
				exponent++;
				number /= prime;
			}
			numberOfFactors *= exponent + 1;
		}

		return numberOfFactors;
	}

	/**
	 * Finds the primes using the SieveOfEratosthenes method
	 *
	 * @param sizeOfSieve The upper bound till which the primes are to be calculated
	 */
	private void sieveOfEratosthenes(int sizeOfSieve) {
		m_primeNumbers.add(2);
		BitSet primeBits = new BitSet(sizeOfSieve / 2);
		int primeNumberIndex = primeBits.nextClearBit(0);
		int primeNumber = 2 * primeNumberIndex + 3;
		while (primeNumber < sizeOfSieve) {
			m_primeNumbers.add(primeNumber);
			for (int i = primeNumberIndex; i < sizeOfSieve / 2; i += primeNumber)
				primeBits.set(i);
			primeNumberIndex = primeBits.nextClearBit(primeNumberIndex);
			primeNumber = 2 * primeNumberIndex + 3;
		}
	}
}

Main class:

package problems_11_20;

import pba.common.number.PrimeNumbers;

public class Problem_12 {
	public static void mainAnuvrat(String[] args) {
		PrimeNumbers p = new PrimeNumbers(1000000);

		int triangleNumber = 1;
		int step = 1;
		while (p.getNumberOfFactors(triangleNumber) < 500)
			triangleNumber += ++step;

		System.out.println(triangleNumber);
	}

	public static void mainProjectEuler(String[] args) {
		PrimeNumbers p = new PrimeNumbers(1000000);

		boolean odd = true;
		int n = 1;
		int numberOfFactors = 0;
		int memoization = 1;
		do {
			if (odd) {
				int temp = p.getNumberOfFactors((n + 1) / 2);
				numberOfFactors = memoization * temp;
				memoization = temp;
			} else {
				int temp = p.getNumberOfFactors(n + 1);
				numberOfFactors = memoization * temp;
				memoization = temp;
			}
			odd = !odd;
			n++;
		} while (numberOfFactors < 500);
		n--;

		System.out.println(n * (n + 1) / 2);
	}
}

Project Euler did suggest an improvement on this. It says that since

t = \frac{n \times (n+1)}{2}

and n, n+1 being co-primes, the number of divisors can be found as

D(t) = D(n) \times D(\frac{n+1}{2}) if n is odd

D(t) = D(\frac{n}{2}) \times D(n+1) if n is even

This provides a lot of advantage over the previous implementation. The first being that we are now looking to find the number of factors for a smaller numbers. Secondly, the value for the n+1 can be used in the next triangle number, thus saving more computations.

Popularity: 41% [?]

Sum Of Divisors

Published on January 20, 2010 in Problems. 0 Comments

Let n be an integer factorized as following:

n = {p_1}^{e_1} \times {p_2}^{e_2} \times \ldots \times {p_k}^{e_k}

The sum of divisors of n is:

\sigma(n) = a_1 \times a_2 \times \ldots \times a_k

where,

a_k = \frac{{p_k}^{e_k + 1} - 1}{p_k - 1} = {p_k}^{e_k} \times \ldots \times {p_k}^{2} \times {p_k}^{1}

In the simpler case of n = p^e, the sum is

\sigma(n) = p^e \times \ldots \times p^2 \times p

This I learned from the article written by Hisanori Mishima found here. The idea translates into a nice little loop to find the sum of divisors. The Java implementation of it has been done by me and is thus:

package pba.common.number;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;

public class PrimeNumber {
	private List<Integer> m_primeNumbers;

	/**
	 * @param sizeOfSieve The upper bound to the determination of prime numbers.
	 */
	public PrimeNumber(int sizeOfSieve) {
		m_primeNumbers = new ArrayList<Integer>();
		sieveOfEratosthenes(sizeOfSieve);
	}

	/**
	 * @param number The number whose sum of divisors is required
	 * @return The sum of divisors of the given number
	 */
	public int getSumOfDivisors(int number) {
		int sum = 1;
		while (number > 1) {
			int temp = 1;
			int primeFactor = getSmallestPrimeFactor(number);
			while (number % primeFactor == 0) {
				temp = temp * primeFactor + 1;
				number /= primeFactor;
			}
			sum *= temp;
		}

		return sum;
	}

	/**
	 * @param number The number whose smallest prime factor is required
	 * @return The smallest rpime factor for the given number
	 */
	public int getSmallestPrimeFactor(int number) {
		for (int prime : m_primeNumbers)
			if (number % prime == 0)
				return prime;

		return Integer.MIN_VALUE;
	}
}

Note that the list of prime numbers can be quickly found by using the Sieve of Eratosthenes.

Popularity: 12% [?]