Tag Archive for 'counting'

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 : Count Of Lychrel Numbers Below 10000

Published on August 26, 2011 in Problems. 0 Comments

Problem 55 of Project Euler explains what Lychrel numbers are and asks one to find the number of those below 10000. The only sticking point in the whole procedure is that after a few iterations the number become so large that BigInteger needs to be used. But otherwise, just follow the wording of the statement and the problem will be solved.

Here’s the outermost loop which does the counting:

    private static final int ARRAY_SIZE = 1000000;
    private static final BigInteger BIG_ARRAY_SIZE = BigInteger.valueOf(ARRAY_SIZE);

    public static int countOfLychrelNumbers(int upperLimit) {
        int count = 0;

        State[] lychrelNumbers = ArrayUtils.createArray(ARRAY_SIZE, State.NOT_VERIFIED, new State[0]);
        for (int i = 0; i <= upperLimit; i++) {
            if (lychrelNumbers[i] == State.NON_LYCHREL) continue;
            if (lychrelNumbers[i] == State.LYCHREL || testForLychrelProperty(lychrelNumbers, i)) {
                count++;
            }
        }

        return count;
    }

    private enum State {
        LYCHREL, NON_LYCHREL, NOT_VERIFIED
    }

It’s in the testForLychrelProperty method that all the caching logic comes in. It makes sense to cache the results. However, I have imposed a cache limit as well. Here’s the messier code with caching logic:

    private static boolean testForLychrelProperty(State[] lychrelNumbers, int number) {
        int iterCount = 1;
        State state = State.NOT_VERIFIED;
        BigInteger num = BigInteger.valueOf(number);
        List<BigInteger> found = new ArrayList<BigInteger>();
        found.add(num);
        while (iterCount < 50) {
            BigInteger reverse = NumberUtil.reverse(num);
            BigInteger sum = reverse.add(num);
            if (!num.remainder(BigInteger.TEN).equals(BigInteger.ZERO)) found.add(reverse);
            state = sum.compareTo(BIG_ARRAY_SIZE) < 0 ? lychrelNumbers[sum.intValue()] : State.NOT_VERIFIED;
            if (state == State.LYCHREL || state == State.NON_LYCHREL) {
                break;
            }
            if (PalindromeUtil.checkIfPalindrome(sum.toString())) {
                state = State.NON_LYCHREL;
                break;
            }
            num = sum;
            found.add(sum);
            iterCount++;
        }

        if (state == State.NOT_VERIFIED) state = State.LYCHREL;

        setState(lychrelNumbers, found, state);
        return state == State.LYCHREL;
    }

The setState method simply updates the cache with the latest result. Here is it’s implementation:

    private static void setState(State[] lychrelNumbers, List<BigInteger> numbers, State state) {
        for (BigInteger number : numbers) {
            if (number.compareTo(BIG_ARRAY_SIZE) > 0) return;
            lychrelNumbers[number.intValue()] = state;
        }
    }

All in all, the code runs in some 180ms on my laptop.

Popularity: 6% [?]

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

Tag Archive for 'counting'

Project Euler : n Digit Integers That Are Also nth Power

Project Euler : Count Of Lychrel Numbers Below 10000

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

Popular Posts

Recent Posts