Tag Archive for 'pandigital'

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 : 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 : Problem 32 – All Round Pandigital

Published on May 27, 2010 in Problems. 0 Comments

The problem requires one to find a product of two numbers such that the multiplicand/multiplier/product can be written as a 1 through 9 pandigital.

An example would be: 39 * 186 = 7254

Working with paper and a pencil, one can discover that the two form of solution are:

a * bbbb = cccc

aa * bbb = cccc

So all that was required to be done was generate all 9 digit permutations of 1-9 and then check if the arrangement satisfies any of the two cases mentioned above.

public class Problem_32<I extends Integer> {
	public static void main(String[] args) {
		System.out.println(new Problem_32<Integer>().computeSum());
	}

	public int computeSum() {
		int sum = 1;
		Set<Integer> products = new HashSet<Integer>();

		Iterator<CombinatoricsVector<I>> permutationIterator = getPermutationGenerator();
		while (!permutationIterator.isDone()) {
			permutationIterator.next();
			CombinatoricsVector<I> permutation = permutationIterator.getCurrentItem();
			products.add(checkCaseA(permutation));
			products.add(checkCaseB(permutation));
		}

		for (Integer i : products)
			sum += i;

		return sum;
	}

	/**
	 * Case A :: a x bbbb = cccc
	 *
	 * @return cccc if above equality holds, -1 otherwise
	 */
	private int checkCaseA(CombinatoricsVector<I> permutation) {
		int a = permutation.getValue(0);
		int b = get4Number(permutation, 1);
		int c = get4Number(permutation, 5);

		return a * b == c ? c : -1;
	}

	/**
	 * Case B :: aa x bbb = cccc
	 *
	 * @return cccc if above equality holds, -1 otherwise
	 */
	private int checkCaseB(CombinatoricsVector<I> permutation) {
		int a = get2Number(permutation, 0);
		int b = get3Number(permutation, 2);
		int c = get4Number(permutation, 5);

		return a * b == c ? c : -1;
	}

	private int get2Number(CombinatoricsVector<I> permutation, int startIdx) {
		return permutation.getValue(startIdx) * 10 + permutation.getValue(startIdx + 1);
	}

	private int get3Number(CombinatoricsVector<I> permutation, int startIdx) {
		return permutation.getValue(startIdx) * 100 + permutation.getValue(startIdx + 1) * 10
		        + permutation.getValue(startIdx + 2);
	}

	private int get4Number(CombinatoricsVector<I> permutation, int startIdx) {
		return permutation.getValue(startIdx) * 1000 + permutation.getValue(startIdx + 1) * 100
		        + permutation.getValue(startIdx + 2) * 10 + permutation.getValue(startIdx + 3);
	}

	private Iterator<CombinatoricsVector<I>> getPermutationGenerator() {
		ArrayList<I> array = new ArrayList<I>();
		for (int i = 1; i < 10; i++)
			array.add((I) new Integer(i));

		Iterator<CombinatoricsVector<I>> permutationIterator = new PermutationGenerator<I>(new CombinatoricsVector<I>(
		        array)).createIterator();
		permutationIterator.first();

		return permutationIterator;
	}
}

Popularity: 13% [?]

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

Tag Archive for 'pandigital'

Project Euler 43: Pandigital Numbers With Unusual Substring Divisibility Property

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

Project Euler : Problem 32 – All Round Pandigital

Project Euler : Largest N Digit Pandigital Prime Number

Amazon Deals!

Popular Posts