Project Euler/43

Problem Statement

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, and it has an interesting sub-string divisibility property.

Let $$ d_1 $$ be the 1st digit, $$ d_2 $$ the 2nd digit, and so on. The following divisibility relationships hold:

$$ d_2 d_3 d_4 = 406 $$ is divisible by 2
$$ d_3 d_4 d_5 = 063 $$ is divisible by 3
$$ d_4 d_5 d_6 = 635 $$ is divisible by 5
$$ d_5 d_6 d_7 = 357 $$ is divisible by 7
$$ d_6 d_7 d_8 = 572 $$ is divisible by 11
$$ d_7 d_8 d_9 = 728 $$ is divisible by 13
$d_8 d_9 d_{10} = 289$ is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

Approach

Generate Pandigital Permutations

All 0-to-9 pandigital numbers are permutations of the digits {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. The solution uses a recursive backtracking algorithm (Heap's algorithm variant) that generates each permutation in-place by swapping elements. For each permutation, the digit array represents $$ d_1 $$ through $d_{10}$ .

Check Sub-String Divisibility

For each permutation, extract the seven 3-digit substrings and verify each divisibility condition:

$d_2 d_3 d_4 \equiv 0 \pmod{2}$
$d_3 d_4 d_5 \equiv 0 \pmod{3}$
$d_4 d_5 d_6 \equiv 0 \pmod{5}$
$d_5 d_6 d_7 \equiv 0 \pmod{7}$
$d_6 d_7 d_8 \equiv 0 \pmod{11}$
$d_7 d_8 d_9 \equiv 0 \pmod{13}$
$d_8 d_9 d_{10} \equiv 0 \pmod{17}$

All seven conditions must be satisfied for a pandigital number to be counted.

Convert Digits to Number

If a permutation passes all divisibility checks, the 10-digit array is converted to a long integer by iterating through the digits and building the number via repeated multiplication by 10.

Accumulate the Sum

Each valid pandigital number is added to a running total. After all 10! = 3,628,800 permutations have been examined, the accumulated sum is returned.

Solution

Link: https://git.charlesreid1.com/cs/euler/src/branch/main/java/Problem043.java

Flags