Tag Archive for 'prime'

Project Euler : Quadratic Producing Longest Prime Sequence

Published on August 5, 2010 in Problems. 0 Comments

Problem 27 done! Ah well, nothing spectacular as such, but solved none the less. It’s a happy feeling.

The problem required one to find a quadratic of the form $x^2 + a \times x + b$ , with the condition |a| < 1000, |b| < 1000 which produces the longest sequence of primes starting with x = 0.

Let us call $f(x) = x^2 + a \times x + b$

The first thing you notice is that the values of b must belong to the set of primes and they must always be positive.

$f(0) = b$ , and hence b has to be a prime

The next thing to notice is that the values of a are influenced by that of b.

$f(1) = 1 + a + b$ is a prime $\Rightarrow$ a = [prime] – (1+b)

So all I did was to generate primes. Set b as one of the primes. Let a iterate over the other primes and form a polynomial function for each combination. This polynomial function was evaluated for ascending values of x and the longest sequence of primes recorded in each case. I used the commons-math-2.1 library by Apache commons to evaluate the quadratic function.

I did one additional thing. The problem mentions that the quadratic function $n^2 + n + 41$ generates a sequence of 40 primes. You must have noted that these polynomials cannot produce a sequence longer than the value of the constant term, which is b in our case (to see this, evaluate the expression with x = b). So for $0 < b < 41$ the above is the best quadratic there is. Thus we need to begin at 41.

Below is my solution which runs in 1600ms on my laptop. Not good enough though .

public class Problem_27 {
	public static UnivariateRealFunction getPrimeNumberFunction() throws FunctionEvaluationException {
		PrimeNumbers primeGenerator = new PrimeNumbers(100000);
		List<Integer> primes = primeGenerator.getPrimeNumbers();
		int upperLimit = primeGenerator.getPrimeIndex(997);
		int lowerLimit = primeGenerator.getPrimeIndex(41);

		double[] coefficients = new double[3];
		coefficients[2] = 1;
		MaxObject<UnivariateRealFunction> maxLength = MaxObject.init();

		Stopwatch sw = new Stopwatch();
		sw.start();
		for (int i = upperLimit; i >= lowerLimit; i--) {
			coefficients[0] = primes.get(i);
			for (int j = 0; j < upperLimit; j++) {
				coefficients[1] = primes.get(j) - coefficients[0] - 1;
				UnivariateRealFunction quadratic = new PolynomialFunction(coefficients);
				maxLength.compare(quadratic, Problem_27.getSeriesLength(quadratic, primes));
			}
		}
		sw.stop();
		System.out.println(sw);

		return maxLength.getMaxObject();
	}

	private static int getSeriesLength(UnivariateRealFunction function, List<Integer> primes)
	        throws FunctionEvaluationException {
		for (int i = 0; true; i++) {
			int value = (int) function.value(i);
			if (value < 0 || !primes.contains(value))
				return i;
		}
	}
}

Popularity: 8% [?]

Project Euler : d For Which 1/d Has Longest Recurring Cycle

Published on August 4, 2010 in Problems. 0 Comments

Problem 26 in Project Euler is a very simple question. There are two options – check the periodicity of numbers in quotient, or check the periodicity of remainders. Yup! The periodicity of remainders implies periodicity in quotient.

Here is my Java solution. It runs in 125ms on my Latitude D630 laptop.

public class Problem_26 {
	/**
	 * @return The number which has the highest recurring decimal periodicity
	 */
	public int getLargestPeriodicityNumber() {
		PrimeNumbersIterator primes = new PrimeNumbersIterator(1000);
		primes.reverseOrder();
		MaxObject<Integer> maxNumber = MaxObject.init();

		Stopwatch sw = new Stopwatch();
		sw.start();
		while (primes.hasNext()) {
			int i = primes.next();
			maxNumber.compare(i, getPeriodicity(i));
		}
		sw.stop();
		System.out.println(sw);

		return maxNumber.getMaxObject();
	}

	/**
	 * Get the periodicity of recurring decimals by checking the remainders
	 *
	 * @param number The number for which the periodicity is required
	 * @return The periodicity of recurring decimal
	 */
	private int getPeriodicity(int number) {
		List<Integer> remainders = new ArrayList<Integer>();

		int remainder = 10;
		remainders.add(remainder);
		while (true) {
			remainder = remainder % number * 10;
			if (remainders.contains(remainder))
				return remainders.size() - remainders.indexOf(remainder);
			remainders.add(remainder);
		}
	}

	public static void main(String[] args) {
		System.out.println(new Problem_26().getLargestPeriodicityNumber());
	}
}

Popularity: 8% [?]

Project Euler : Largest N Digit Pandigital Prime Number

Published on May 26, 2010 in Problems. 1 Comment

Well, I did a brute force for problem 41 for Project Euler. There’s a smarter way of course, but I still haven’t implemented a Permutation Generator. That later.

I already have a good enough prime number generator. So all I did was to generate all the prime number till 7 digits long. Why did I not go any further?

8 digit pandigital numbers will sum up to 36, and the 9 digit numbers will sum up to 45. So all the pandigital 8 and 9 digit numbers will be non-prime. So we need to check till atmost the 7 digit prime numbers.

Now apart from a prime generator, I also have a prime number iterator, which can iterate forwards as well as backwards. So all I had to do was to ask my iterator to iterate backwards and check if the prime number is pandigital or not.

Obviously, my prime number iterator internally calls my sieve of Eratosthenes to generate prime numbers using java.util.BitSet.

Surprisingly, the code runs in just a few seconds! I was expecting it to take atleast a minute.

Here is my prime number iterator:


public class PrimeNumbersIterator implements Iterator<Integer> {
	private PrimeNumbers m_pNumber;
	private int m_currentIndex;
	private boolean m_reverse;

	public PrimeNumbersIterator(int upperLimit) {
		m_pNumber = new PrimeNumbers(upperLimit);
		m_reverse = false;
	}

	public boolean hasNext() {
		if (!m_reverse)
			return m_currentIndex < m_pNumber.getNumberOfPrimes() ? true : false;
		else
			return m_currentIndex >= 0 ? true : false;
	}

	public Integer next() {
		Integer prime = hasNext() ? m_pNumber.getPrime(m_currentIndex) : null;
		if (m_reverse)
			m_currentIndex--;
		else
			m_currentIndex++;

		return prime;
	}

	public void remove() {
		throw new UnsupportedOperationException();
	}

	public void reverseOrder() {
		m_reverse = !m_reverse;
		m_currentIndex = m_pNumber.getNumberOfPrimes() - 1;
	}
}

And here is a small unoptimized method to check if the number is pandigital or not:


	public static boolean isNPandigital(int number) {
		int numberOfDigits = NumberUtil.numberOfDigits(number);
		int[] digits = new int[numberOfDigits];
		Arrays.fill(digits, 0);

		while (number > 0) {
			int digit = number % 10;
			if (digit == 0 || digit > numberOfDigits || digits[digit - 1]++ == 1)
				return false;
			number /= 10;
		}

		return true;
	}

Popularity: 30% [?]

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% [?]

Project Euler : Sum Of Primes Below Two Million

Published on December 12, 2009 in Problems. 1 Comment

Another simple straight forward question from Project Euler. The idea was to re-use the prime number generator that I had written for the problem number 7. It was a simple thing of letting my array grow till the last prime found was greater than 2 million, and then sum up all the elements in the array. Not much to write about. Here’s the code that ran in 3468ms on my machine:

public class Problem_10 {
    public long getSumOfPrimes(int maxPrime) {
        List<Long> primes = new ArrayList<Long>();
        primes.add(2L);
        long sum = 2L;
        long lastPrime = 2L;
        long num = 3L;

        // Start the stopwatch
        Stopwatch stopwatch = new Stopwatch();
        stopwatch.start();

        // Search for primes by dividing num with all the known prime numbers
        while (lastPrime < maxPrime) {
            boolean isComposite = false;
            double sqrt = Math.sqrt(num);
            for (long p : primes) {
                if (p > sqrt)
                    break;
                if (num % p == 0) {
                    isComposite = true;
                    break;
                }
            }
            if (!isComposite) {
                primes.add(num);
                lastPrime = num;
                if (num < maxPrime)
                    sum += num;
            }
            num++;
        }

        stopwatch.stop();
        System.out.println("The reading for operation is: " + stopwatch);

        return sum;
    }

    public static void main(String[] args) {
        System.out.println((new Problem_10()).getSumOfPrimes(2000000));
    }
}

Here since the upper bound was already known to me, using the Sieve of Eratosthenes would be the better way to go about things. Further optimization ignores all the even numbers as 2 is the only even prime. In this case, the ith element represents the number 2i + 1

Popularity: 14% [?]

Project Euler : Find the nth Prime

Published on December 11, 2009 in Problems. 0 Comments

The seventh problem in Project Euler is stated thus:

Find the 10001st prime number.

Well, there are two ways that I knew of to find the prime numbers. One is by checking if it has any factors below sqrt(n) and the second method is the Sieve of Eratosthenes. I checked online to search for a better method, but could not find any. So I decided to go ahead implementing the factor thing.

I created an array to hold all the discovered primes. Now given a number, I check if it already is in the list or not. If yes, it is a prime. If not, I check if any of the primes in the list, less than square root of the number, is a factor of this number or not. My code was able to all these computations and throw the answer in 94ms.

The solution proposed by the Project Euler authors improvised on this. They used an additional fact that any prime greater than 3 is of the form 6k+/-1.

Also, another thing that I read was that if you know the upper bound of the prime number, then the Sieve of Eratosthenes gives the answer much quickly. To estimate the upper bound Wikipedia has a topic called Prime Number Theorem, which could be looked up.

I am pasting below the piece of code I wrote to generate the 10001st prime number:

public class Problem_7 {
    public Long getPrimeByIndex(int index) {
        if (index == 1)
            return 2L;

        // An array of all the discovered primes
        List<Long> primes = new ArrayList<Long>();
        primes.add(2L);

        Long num = 3L;

        // Start the stopwatch
        Stopwatch stopwatch = new Stopwatch();
        stopwatch.start();

        // Search for primes by dividing num with all the known prime numbers
        while (primes.size() != index) {
            boolean isComposite = false;
            double sqrt = Math.sqrt(num);
            for (Long p : primes) {
                if (p > sqrt)
                    break;
                if (num % p == 0) {
                    isComposite = true;
                    break;
                }
            }
            if (!isComposite)
                primes.add(num);
            num++;
        }

        stopwatch.stop();
        System.out.println("The reading for operation is: " + stopwatch);

        return primes.get(index - 1);
    }

    public static void main(String[] args) {
        System.out.println((new Problem_7()).getPrimeByIndex(10001));
    }
}

Popularity: 25% [?]

Project Euler : Finding The Largest Prime Factor Of A Given Number

Published on August 31, 2009 in Problems. 0 Comments

The problem is this: Find the largest prime factor of a given number. One brute force way is to find a factor of the given number and then perform primality testing on the number. But the test to check if the number is prime or not is a costly operation if one does not have a set of all primes.

So there was a need for me to avoid the testing of a number for primality.

One interesting thing to be noticed is that the smallest factor of a number has to be prime. Suppose if it were not, then it implies that it can be written as a product of two smaller numbers which contradicts the hypothesis that the factor is the smallest factor.

So we can avoid the testing of primality by taking the smallest factor. But the problem requires us to determine the largest prime factor. The lergest prime factor can be recursively obtained by using the following:

public static long largestPrimeFactor(long n) {
    long prime = smallestPrimeFactor(n);
    return Math.max(prime, largestPrimeFactor(n/prime));
}

Where the smallest prime factor method returns the smallest factor of n.

One of the interesting things that I read while solving this problem was that after 3, all the prime numbers satisfy the general formula 6n-1, 6n+1. So the primes will be in the series :

6(1) – 1 = 5

6(1) + 1 = 7

6(2) – 1 = 11

6(2) + 1 = 13 …

In fact, primes after the number p belong to the series p# n + m, where p# is called the primorial. Look up the wiki entry to learn more.

Popularity: 4% [?]