Tag Archive for 'maths'

Project Euler 43: Pandigital Numbers With Unusual Substring Divisibility Property

Published on December 2, 2011 in Problems. 0 Comments

Anuvrat Singh Project Euler Badge

This was one of those questions that can be solved using a pen and paper. Problem 53 requires one to find all the 10-digit pandigital numbers which satisfy the following properties:

$d_2d_3d_4$ is divisible by 2

$d_3d_4d_5$ is divisible by 3

$d_4d_5d_6$ is divisible by 5

$d_5d_6d_7$ is divisible by 7

$d_6d_7d_8$ is divisible by 11

$d_7d_8d_9$ is divisible by 13

$d_8d_9d_{10}$ is divisible by 17

Just to reiterate, a pandigital number is one in which each digit occurs only once. This is how we proceed:

$d_4d_5d_6$ is divisible by 5

This implies that $d_6$ is either 0 or 5.

$d_6d_7d_8$ is divisible by 11

This implies that $d_6 + d_8 - d_7$ is a multiple of 11.
If $d_6$ were to be 0, it would mean that $d_8 = d_7$ or $d_8 = d_7 + 11$ , neither of which can be true given that the number we seek is pandigital.
So we can assert that $d_6 = 5$ .
We need all the pairs of $d_7$ and $d_8$ satisfying $d_8 - d_7 = 6$ or $d_8 - d_7 = -5$ .

Possible $(d_7, d_8)$ pairs are (6,1), (7,2), (8,3), (9,4), (1,7), (2,8), (3,9)

$d_5d_6d_7$ is divisible by 7

This essentially means that $10*d_5 + d_6 - 2*d_7$ is a multiple of 7. We already have the value for $d_6$ and have narrowed down the possible values of $d_7$ .

$d_6, d_7 = 5, 6 \Rightarrow d_5 = 7$
$d_6, d_7 = 5, 7 \Rightarrow d_5 = 3$
$d_6, d_7 = 5, 8 \Rightarrow d_5 = 6$
$d_6, d_7 = 5, 9 \Rightarrow d_5 = 2$
$d_6, d_7 = 5, 1 \Rightarrow d_5 = 6$
$d_6, d_7 = 5, 2 \Rightarrow d_5 = 9$
$d_6, d_7 = 5, 3 \Rightarrow d_5 = NA$

Possible $(d5, d6, d7, d8)$ tuples are (7,5,6,1), (3,5,7,2), (6,5,8,3), (2,5,9,4), (6,5,1,7) or (9,5,2,8).

$d_7d_8d_9$ is divisible by 13

This implies that $d_9 + 10*d_8 + 9*d_7$ is a multiple of 13. We have already identified the possible $d_7, d_8$ pairs. We can get the possible $d_9$ values now.

$d_7, d_8 = 6, 1 \Rightarrow d_9 = NA$
$d_7, d_8 = 7, 2 \Rightarrow d_9 = 8$
$d_7, d_8 = 8, 3 \Rightarrow d_9 = 2$
$d_7, d_8 = 9, 4 \Rightarrow d_9 = NA$
$d_7, d_8 = 1, 7 \Rightarrow d_9 = NA$
$d_7, d_8 = 2, 8 \Rightarrow d_9 = 6$

Possible $(d_5, d_6, d_7, d_8, d_9)$ tuples are (3,5,7,2,8), (6,5,8,3,2) or (9,5,2,8,6).

$d_8d_9d_{10}$ is divisible by 17

This implies that $10*d_8 + d_9 - 5*d_{10}$ is a multiple of 17. Again using the possible values of the other two variables, we can narrow down the value of the third one.

$d_8, d_9 = 2, 8 \Rightarrow d_{10} = 9$
$d_8, d_9 = 3, 2 \Rightarrow d_{10} = NA$
$d_8, d_9 = 8, 6 \Rightarrow d_{10} = 7$

So we now have the following tuples for the values of $(d_5, d_6, d_7, d_8, d_9, d_{10})$ : (3,5,7,2,8,9) or (9,5,2,8,6,7).

$d_2d_3d_4$ is divisible by 2 tells us that $d_4$ is even. So in the first case it can take the values 0,4,6 and in the second case the values 0,4.

Finally, using the last condition that $d_3d_4d_5$ is divisible by 3, we conclude that $d_3, d_4$ in the first case can be either of 6,0 or 0,6 and in the second case is 0,9.

Thus we have the six possible numbers as: 1406357289, 1460357289, 4106357289, 4160357289, 1430952867 and 4130952867. And we are done! Sum of these 6 numbers is what the problem asked for.

Popularity: 4% [?]

Project Euler : Expansion Of Continued Fraction For Square Root Of Two

Published on October 4, 2011 in Problems. 0 Comments

Problem 57 of Project Euler is pretty simple forward. It is very easy to see the following relation:

$Numerator = Numerator + 2 * Denominator$

$Denominator = Numerator + Denominator$

Simple code and was done. Here’s that:

    public int getCount(int numberOfExpansions) {
        int count = 0;

        BigInteger numerator = BigInteger.valueOf(3);
        BigInteger denominator = BigInteger.valueOf(2);
        while(--numberOfExpansions > 0) {
            BigInteger a = denominator.multiply(NumberUtil.BIG_TWO).add(numerator);
            BigInteger b = numerator.add(denominator);
            numerator = a;
            denominator = b;
            if(NumberUtil.numberOfDigits(numerator) > NumberUtil.numberOfDigits(denominator)) count++;
        }

        return count;
    }

Popularity: 4% [?]

Project Euler : n Digit Integers That Are Also nth Power

Published on October 3, 2011 in Problems. 0 Comments

Problem number 63 of Project Euler gives the expression $a = b^c$ and imposes the condition that the number of digits in $a$ is equal to $c$ . An example would be $16807 = 7^5$ . $a$ , $b$ and $c$ are all positive integers. The problem asks one to find the number of such possibilities.

Solving this problem made me happy. So, I’ll go into the details.

Given the problem, the first thing that comes to mind is the special relationship between the log of a number and the number of digits. The hint is to use logarithms to simplify the problem.

$a = b^c$

$\Rightarrow \log(a) = c \log(b)$

But $\log(a) = c - f$ , where $f \in (0, 1]$

$\Rightarrow c - f = c \log(b)$

$\Rightarrow c \log(\frac{10}{b}) = f$

$\Rightarrow 0 < \log(\frac{10}{b}) \leq \frac{1}{c}$ , dividing by $c \in Z^+$

That’s it! Our problem has been solved. I hope you have already noted that $b \in [1, 9]$ . This means that we can precompute the values of $\log(\frac{10}{b})$ and store the results in an array. Then for all $c \geq 1$ , just count how many of the precomputed values are smaller than or equal to $\frac{1}{c}$ . The iteration completes when the smallest precomputed value is greater than $\frac{1}{c}$ .

Below is the piece of code I wrote in Java to solve the task.

    public int getCount() {
        m_precomputedValues = new double[9];
        for(int i = 1; i < 10; i++) {
            m_precomputedValues[i-1] = Math.log10(10.0 / i);
        }

        int count = 0;

        int numberOfDigits = 1;
        double val = 1.0 / numberOfDigits;
        while (val > m_precomputedValues[8]) {
            for(int idx = 8; idx >= 0 &amp;amp;&amp;amp; m_precomputedValues[idx] <= val; idx--) count++;
            val = 1.0 / ++numberOfDigits;
        }

        return count;
    }

Popularity: 4% [?]

Project Euler : Finding Minimal Sum Path In A Matrix

Published on January 26, 2011 in Problems. 0 Comments

The problem 81 of Project Euler gives a square matrix and requires one to find the minimal sum path. Specifically, it only required the sum of the numbers on the path. The question immediately reminded me of problem 67 and I set out solving with the same logic.

The logic has been explained in the following post of mine: Project Euler : Maximum Sum Traversing Top To Bottom In A Triangle.

The following lines of code did the work for me:

    public static int getMinimalSumPath(int[][] numbers) {
        int dimension = numbers.length - 1;
        for (int x = dimension; x >= 0; x--)
            for (int y = dimension; y >= 0; y--) {
                if (x == dimension &amp;amp;&amp;amp; y == dimension) continue;
                int val1 = x < dimension ? numbers[x + 1][y] : Integer.MAX_VALUE;
                int val2 = y < dimension ? numbers[x][y + 1] : Integer.MAX_VALUE;
                numbers[x][y] += val1 < val2 ? val1 : val2;
            }

        return numbers[0][0];
    }

Popularity: 13% [?]

Project Euler : Counting The Number Of Right Triangles In A Grid

Published on January 19, 2011 in Problems. 0 Comments

The problem 91 of Project Euler was a bit tricky. It requires one to find the number of right angled triangles in a n X n grid, with one point $(0,0)$ fixed. For example, as shown on the problem page, a 3 X 3 grid contains 14 triangles. The problem required the answer for a 51 X 51 grid.

Well, at first I started with a pencil-paper approach. I listed down all the cases I could think of and checked my calculation for the 3 X 3 grid. Got the answer right. But applied the same to the larger 51 X 51 grid I realized that there were cases I had not enumerated all the cases. I am still not sure if the problem can be solved using just a pencil and a paper.

I did not want to do a brute force way of picking up two arbitrary points and checking if they form a right angled triangle. In my solution I have never tried to determine the actual triangles. As you shall see, all I do is to find the number of possible triangles by using a parameter and bounding it within an interval. The range of the interval is my solution for that particular point.

I went the mathematics way. One of the points is fixed at $(0,0)$ . Select one point as $(a,b)$ . The slope of the line joining these two points is $\frac{b}{a}$ . So the equation of a line perpendicular to this one and passing through the point $(a,b)$ would be :

$y = -\frac{a}{b}(x - a) + b$

Now points which lie on the above line will all form right angled triangles with the points $(0,0)$ and $(a,b)$ . The following conditions need to be satisfied in our particular problem:

The solutions to the above equation are integers.
The points lie within a grid of n X n. So $0 \leq x \leq n$ and $0 \leq y \leq n$ .

There are two cases we need to consider. One where $a$ is a multiple of $b$ and the other where it is not.

Let us first consider the case where $a$ is not a multiple of $b$ . We rewrite the equation as follows:

$y = -\frac{c}{d}(x - fc) + fd$

where $f$ is the gcd of $a$ and $b$ . Now since $y$ is an integer, we can impose the following condition on $x$ :

$x = fc + kd$

where k is some parameter, in which case the value of $y$ becomes:

$y = fd - kc$

And now imposing the second criteria, we can limit the values of the parameter $k$ as thus:

$0 \leq x \leq n$

$\Rightarrow -\frac{fc}{d} \leq k \leq \frac{n - fc}{d}$

Similarly, imposing the same conditions for $y$ , we get

$\frac{fd - n}{c} \leq k \leq \frac{fd}{c}$

The intersection of the two intervals gives us the eligible values for the parameter $k$ as :

$max ( -\frac{fc}{d}, \frac{fd - n}{c} ) \leq k \leq min ( \frac{n - fc}{d}, \frac{fd}{c} )$

For $k = 0$ we get the point $(a,b)$ . For all other values of $k$ we get the points which complete the right angled triangle. So the number of right angled triangles in this case will be the range of k – 1.

Now the other case. Let $a = pb$ . The equation then becomes :

$y = -p (x - a) + b$

Let $q = x - a$ . Then we have

$y = -pq + b$

Once again the applying the boundary conditions we get:

$\frac{b - n}{p} \leq q \leq \frac{b}{p}$

$-a \leq q \leq n - a$

Once again taking the intersection of the intervals gives us:

$max ( \frac{b - n}{p}, -a ) \leq q \leq min ( \frac{b}{p}, n - a )$

Add to this the trivial case of $3n^{2}$ right angled triangles formed when one of the points lie on the axis. It is easy to see these if you sit with a pencil and a paper.

I went ahead to code the above conditions. The code is given below. On my laptop I was able to run this code for a grid of 4000 X 4000 in 1 second.

In the code given below, I have used $(xIdx, yIdx)$ as the point $(a,b)$ . $f$ and $p$ are as described above.

    public int getCount(int n) {
        int count = 0;

        for (int xIdx = 1; xIdx <= n; xIdx++)
            for (int yIdx = xIdx; yIdx <= n; yIdx++) {
                int tempCount = xIdx % yIdx == 0 ? countForXMultipleOfY(xIdx, yIdx, n) : countForXNotMultipleOfY(xIdx,
                        yIdx, n);
                count += xIdx != yIdx ? 2 * tempCount : tempCount;
            }

        return (int) (count + 3 * Math.pow(n, 2));
    }

    private int countForXMultipleOfY(int xIdx, int yIdx, int n) {
        int p = xIdx / yIdx;

        int lowerBoundary = NumberUtil.larger((yIdx - n) / p, xIdx * -1);
        int upperBoundary = NumberUtil.smaller(yIdx / p, n - xIdx);

        return upperBoundary > lowerBoundary ? upperBoundary - lowerBoundary : 0;
    }

    private int countForXNotMultipleOfY(int xIdx, int yIdx, int n) {
        int f = MathUtils.gcd(yIdx, xIdx);

        int lowerLimit = NumberUtil.larger(-1 * xIdx / (yIdx / f), (yIdx - n) / (xIdx / f));
        int upperLimit = NumberUtil.smaller(yIdx / (xIdx / f), (n - xIdx) / (yIdx / f));

        return upperLimit > lowerLimit ? upperLimit - lowerLimit : 0;
    }

Popularity: 15% [?]

Project Euler : Finding Largest 9-Pandigital Number Formed As A Concatenated Product

Published on January 10, 2011 in Problems. 0 Comments

Problem 38 of Project Euler states the problem of finding the largest 1-9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1, 2, .. ,n) where n > 1. As an example, take the number 192 and its products with 1, 2 and 3.

192 * 1 = 192

192 * 2 = 384

192 * 3 = 576

The concatenated number 192384576 is a 9-digit pandigital number. Another example is that of multiplying 9 with (1, 2, 3, 4, 5) to yield the number 918273645.

The above serves as a hint. We now know that the required answer is at least greater than 918273645. Let us try to eliminate a few options.

Consider all 2 digit numbers in the interval [91, 98]. Their multiplication with 1, 2 and 3 will yield 2, 3 and 3 digit numbers respectively. Concatenating these numbers will result in a 8 digit number. But we need a 9-digit number. So we can rule out this case.

Consider all 3 digit numbers in the interval [918, 987]. Their multiplication with 1 and 2 will yield 3 and 4 digit numbers respectively. With the same logic as the previous case, we can rule out these numbers.

Consider all 4 digit numbers in the interval [9182, 9876]. Their multiplication with 1 and 2 will yield 4 and 5 digit numbers respectively. This is the range we are looking for.

After reducing the search space to 694 numbers, a simple java code did the work. It makes a call to NumberUtil.isNPandigital(int) which returns true if the number is pandigital and false otherwise.

public class Problem_38 {
    public static int getValue() {
        for (int i = 9876; i > 9183; i--) {
            int val = i * 100002;
            if (NumberUtil.isNPandigital(val)) return val;
        }

        return -1;
    }
}

Popularity: 9% [?]

Project Euler : Compute ( p * a^b + q ) mod c

Published on December 8, 2010 in Problems. 0 Comments

The problem 97 of Project Euler required one to find the value of:

284332^7830457+1.

Anshumali Srivastava and I spent a lot of time on time, trying to factor the expression into smaller numbers which could make the computation easier. We tried a few things but got stuck every time.

Finally giving up on it, I decided to brute force it using the BigInteger class of Java. Amazingly, it took just a few seconds to get the answer. Looking at the solutions posted in the forum I realized that everyone had done the same and even the Project Euler admin called this one as a freebie. There was one suggestion to improve the solution. You can read about it here:

http://www.osix.net/modules/article/?id=696

The Java implementation for the same would be:

    public static final BigInteger TWO = BigInteger.valueOf(2);

    /**
     * Computes the value of a^b mod c
     *
     * @param a The base
     * @param b The exponent
     * @param c The mod number
     * @return The value of a^b mod c
     */
    public static final BigInteger aPowbModc(BigInteger a, BigInteger b, BigInteger c) {
        long longValue = b.longValue();
        if (longValue < 0) throw new IllegalArgumentException("Exponent should be non negative");
        if (longValue == 0) return BigInteger.ONE;
        if (a.longValue() == 0) return BigInteger.ZERO;

        BigInteger v = NumberUtil.aPowbModc(a, b.divide(NumberUtil.TWO), c).modPow(NumberUtil.TWO, c);

        return longValue % 2 == 1 ? v.multiply(a).mod(c) : v;
    }

The recursive exponentiation function:

    public static BigInteger getVal() {
        BigInteger mod = new BigInteger("10").pow(10);
        BigInteger val = NumberUtil.aPowbModc(new BigInteger("2"), new BigInteger("7830457"), mod)
                .multiply(new BigInteger("28433")).add(BigInteger.ONE);
        return val.mod(mod);
    }

Popularity: 5% [?]

Project Euler : Fractions With Unorthodox Cancelling Method

Published on August 10, 2010 in Problems. 0 Comments

Problem 33 in Project Euler says there are 4 non-trivial curious fractions which satisfy the following properties:

$\frac{ax}{xb} = \frac{a}{b}$

where a, b and x are all single digit numbers and a < b

The solution was pretty simple.

$\frac{ax}{xb} = \frac{a}{b}$

$\Rightarrow b [10a + x] = a [10x + b]$

$\Rightarrow x = \frac{9ab}{10a - b}$

Similarly solving for the other form $\frac{xa}{bx} = \frac{a}{b}$ gives the answer $x = \frac{9ab}{10b - a}$ .

Implementing this solution in java:

public class Problem_33 {
	/**
	 * @return All the proper non-trivial curious fractions having numerator, denominator < 100
	 */
	public static List<Fraction> getCuriousFractions() {
		List<Fraction> curiousFractions = new ArrayList<Fraction>();

		for (int a = 1; a < 10; a++)
			for (int b = a + 1; b < 10; b++)
				if (Problem_33.checkCondition(a, b))
					curiousFractions.add(new Fraction(a, b));

		return curiousFractions;
	}

	/**
	 * Checks if the number is of the form xa/bx = a/b or ax/xb = a/b
	 *
	 * @param a The numerator of the fraction
	 * @param b The denominator of the fraction
	 * @return true if it can be formed into a curious fraction, false otherwise
	 */
	private static boolean checkCondition(int a, int b) {
		int numerator = 9 * a * b;
		int denominatorA = 10 * b - a;
		int denominatorB = 10 * a - b;
		return numerator % denominatorA == 0 && numerator / denominatorA < 10 || numerator % denominatorB == 0
		        && numerator / denominatorB < 10 ? true : false;
	}
}

Popularity: 9% [?]

Project Euler : Find Hexagonal Pentagonal Number

Published on August 9, 2010 in Problems. 0 Comments

Problem 45 of Project Euler required one to find numbers which are triangular, pentagonal and hexagonal together. Checking for triangularity is redundancy as all hexagonal numbers are also triangular. So it boils down to solving the equation:

n(3n – 1) / 2 = m(2m – 1)

Using the Diophantine Equation solver at http://www.alpertron.com.ar/QUAD.HTM, we get the solution as

$n_{i+1} = 97 \times n_i + 112 \times m_i - 44$

$m_{i+1} = 84 \times n_i + 97 \times m_i - 38$

The solution comes very easily from here.

public class Problem_45 {
	/**
	 * Find a number which is Pentagonal and also Hexagonal
	 *
	 * @param index The nth number which is required
	 * @return The nth number which is both Pentagonal and Hexagonal
	 */
	public static int findPentaHexaNumber(int index) {
		int p = 1;
		int h = 1;
		do {
			// This is the solution to the Diophantine Equation
			// p(3p-1)/2 = h(2h-1)
			int p2 = 97 * p + 112 * h - 44;
			h = 84 * p + 97 * h - 38;
			p = p2;
			index--;
		} while (index != 0);

		return h * (2 * h - 1);
	}
}

Popularity: 8% [?]

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

Tag Archive for 'maths'

Project Euler 43: Pandigital Numbers With Unusual Substring Divisibility Property

Project Euler : Expansion Of Continued Fraction For Square Root Of Two

Project Euler : n Digit Integers That Are Also nth Power

Project Euler : Finding Minimal Sum Path In A Matrix

Project Euler : Counting The Number Of Right Triangles In A Grid

Project Euler : Finding Largest 9-Pandigital Number Formed As A Concatenated Product

Project Euler : Compute ( p * a^b + q ) mod c

Project Euler : Fractions With Unorthodox Cancelling Method

Project Euler : Find Hexagonal Pentagonal Number

Project Euler : Quadratic Producing Longest Prime Sequence

Amazon Deals!

Popular Posts