Admin: Create Project Euler/43 with problem statement, approach, and solution link (via create-page on MediaWiki MCP Server)

2026-06-16T14:16:30Z

Create Project Euler/43 with problem statement, approach, and solution link (via create-page on MediaWiki MCP Server)

New page

==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 <math>d_1</math> be the 1st digit, <math>d_2</math> the 2nd digit, and so on. The following divisibility relationships hold:

* <math>d_2 d_3 d_4 = 406</math> is divisible by 2
* <math>d_3 d_4 d_5 = 063</math> is divisible by 3
* <math>d_4 d_5 d_6 = 635</math> is divisible by 5
* <math>d_5 d_6 d_7 = 357</math> is divisible by 7
* <math>d_6 d_7 d_8 = 572</math> is divisible by 11
* <math>d_7 d_8 d_9 = 728</math> is divisible by 13
* <math>d_8 d_9 d_{10} = 289</math> 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 <math>d_1</math> through <math>d_{10}</math>.

===Check Sub-String Divisibility===

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

* <math>d_2 d_3 d_4 \equiv 0 \pmod{2}</math>
* <math>d_3 d_4 d_5 \equiv 0 \pmod{3}</math>
* <math>d_4 d_5 d_6 \equiv 0 \pmod{5}</math>
* <math>d_5 d_6 d_7 \equiv 0 \pmod{7}</math>
* <math>d_6 d_7 d_8 \equiv 0 \pmod{11}</math>
* <math>d_7 d_8 d_9 \equiv 0 \pmod{13}</math>
* <math>d_8 d_9 d_{10} \equiv 0 \pmod{17}</math>

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 <code>long</code> 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==

{{ProjectEulerFlag}}

Project Euler/43 - Revision history

Admin: Create Project Euler/43 with problem statement, approach, and solution link (via create-page on MediaWiki MCP Server)