[C/C++] Project Euler #43 - Sub-string Divisibility

This problem involves finding pandigital numbers that satisfy a specific property and computing their sum. It is considered a relatively simple problem (difficulty: 5%).

sub-string divisibility

---

Problem Description

A 0-9 pandigital number is a 10-digit number that contains each digit from 0 to 9 exactly once. For example, 1406357289 is a 10-digit 0-9 pandigital number.

 

However, instead of simply generating pandigital numbers, this problem requires checking whether specific substrings of the number are divisible by certain prime numbers. Specifically, a valid 10-digit pandigital number must satisfy the following conditions:

 

Conditions - Sub-string Divisibility Property

 

If the pandigital number is represented as d₀d₁d₂d₃d₄d₅d₆d₇d₈d₉, the following conditions must hold:
• d₁d₂d₃ (digits 2 to 4) must be divisible by 2.
• d₂d₃d₄ (digits 3 to 5) must be divisible by 3.
• d₃d₄d₅ (digits 4 to 6) must be divisible by 5.
• d₄d₅d₆ (digits 5 to 7) must be divisible by 7.
• d₅d₆d₇ (digits 6 to 8) must be divisible by 11.
• d₆d₇d₈ (digits 7 to 9) must be divisible by 13.
• d₇d₈d₉ (digits 8 to 10) must be divisible by 17.

 

In other words, specific substrings must be divisible by predetermined prime numbers.

 

Objective

 

The goal is to find all 10-digit pandigital numbers that satisfy these conditions and compute their sum.

For example, the number 1406357289 satisfies the conditions as follows:
• 406 ÷ 2 = 203 (✔)
• 063 ÷ 3 = 21 (✔)
• 635 ÷ 5 = 127 (✔)
• 357 ÷ 7 = 51 (✔)
• 572 ÷ 11 = 52 (✔)
• 728 ÷ 13 = 56 (✔)
• 289 ÷ 17 = 17 (✔)

 

Now, we need to find all such pandigital numbers and compute their sum.

 

Implementation Approach

 

The problem can be solved by checking if a pandigital number satisfies the substring divisibility rule.

 

The most straightforward way to implement this is by using backtracking.

 

To optimize speed, instead of forming three-digit numbers directly, we can build numbers incrementally by multiplying the existing value by 10 and adding the new digit. (Although this may not result in a significant speed improvement, it simplifies implementation.)

 

A simple recursive function can be used to generate the numbers efficiently.

//------------------------------------------------
//    Project Euler #43 - Sub-string Divisibility
//        - by Aubrey Choi
//        - created at 2015-03-29
//------------------------------------------------
#include <stdio.h>
#include <stdint.h>

uint64_t SumPD(uint64_t n, int mask, int t);

int main()
{
    printf("Ans = %ju\n", SumPD(0, 0, 0));
}

uint64_t SumPD(uint64_t n, int mask, int t)
{
    const int p[] = { 1, 1, 1, 2, 3, 5, 7, 11, 13, 17 };
    if( t == 10 ) { printf("%ju\n", n); return n; }

    uint64_t sum = 0;
    for( int i = 0 ; i < 10 ; i++ )
    {
        if( (mask>>i)&1 ) continue;
        if( ((n*10+i)%1000)%p[t] ) continue;
        sum += SumPD(n*10+i, mask | (1<<i), t+1);
    }
    return sum;
}