Divisibility | Diabolical or Smart

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

Tag Archive for 'divisibility'

Project Euler 43: Pandigital Numbers With Unusual Substring Divisibility Property

Popular Posts

Recent Posts