Sub-string Divisibility

The number, $1406357289$, is a $0$ to $9$ pandigital number because it is made up of each of the digits $0$ to $9$ in some order, but it also has a rather interesting sub-string divisibility property.
Let $d_1$ be the $1$st digit, $d_2$ be the $2$nd digit, and so on. In this way, we note the following:
$d_2d_3d_4=406$ is divisible by $2$
$d_3d_4d_5=063$ is divisible by $3$
$d_4d_5d_6=635$ is divisible by $5$
$d_5d_6d_7=357$ is divisible by $7$
$d_6d_7d_8=572$ is divisible by $11$
$d_7d_8d_9=728$ is divisible by $13$
$d_8d_9d_{10}=289$ is divisible by $17$
Find the sum of all $0$ to $9$ pandigital numbers with this property.

The problem involves finding 0 to 9 pandigital numbers that meet specific divisibility criteria. There’s a handy algorithm called the “divisibility rule” for this problem.

For a number to be divisible by 3, the sum of its digits must be divisible by 3. For 2 and 5, it’s much simpler: a number is divisible by 2 if its last digit is even (0, 2, 4, 6 or 8), and by 5 if its last digit is 0 or 5. For 7, 11, 13, and 17, it’s more complicated, so usually, you’d just do the division.

But in this case, working out all the permutations and checking them wouldn’t be feasible. Instead, we’d use a method called permutation generation in lexicographical order.

It goes like this:

1. Start with the lowest lexicographical permutation – 0123456789
2. Generate all permuted forms, in lexicographically increasing order, until there are no more.
3. For each permutation, check the given divisibility specifications.

Instead of doing this manually, we would typically use a computer program for this. The program would systematically generate permutations and check the conditions. Hence, this turns more into a programming problem, manageable by Python or other languages.

Since the problem asks for the sum of such numbers and not the numbers themselves, we’d make the program keep a running total of numbers that meet the criteria.

This kind of problem is best solved using a programming language. Doing it by hand is not feasible due to the sheer number of permutations. The final answer to this problem, as determined by using an appropriate program, is 16695334890.

As you can see, this problem engages both programming and mathematical knowledge, showing how the two can intertwine within problem-solving contexts.

More Answers: