Tag Archive for 'polynomial'

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 , with the condition |a| < 1000, |b| < 1000 which produces the longest sequence of primes starting with x = 0.

Let us call

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

, 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.

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