Sub-string divisibility | Project Euler | Problem #43
URL to the problem page: https://projecteuler.net/problem=43
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 d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:
d2d3d4=406 is divisible by 2
d3d4d5=063 is divisible by 3
d4d5d6=635 is divisible by 5
d5d6d7=357 is divisible by 7
d6d7d8=572 is divisible by 11
d7d8d9=728 is divisible by 13
d8d9d10=289 is divisible by 17
Find the sum of all 0 to 9 pandigital numbers with this property.
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 d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:
d2d3d4=406 is divisible by 2
d3d4d5=063 is divisible by 3
d4d5d6=635 is divisible by 5
d5d6d7=357 is divisible by 7
d6d7d8=572 is divisible by 11
d7d8d9=728 is divisible by 13
d8d9d10=289 is divisible by 17
Find the sum of all 0 to 9 pandigital numbers with this property.
#include <iostream>
using namespace std;
long long power(long long a, long long b) {
long long result = 1;
for (long long i = 0; i < b; i++) {
result *= a;
}
return result;
}
int main()
{
long long i, j, a, b, c, cnt, number, primes[7] = { 2, 3, 5, 7, 11, 13, 17 }, digits[10], result = 0;
for (int m = 1; m < 10; m++) {
digits[9] = m;
for (int n = 0; n < 10; n++) {
if (n == m) {
continue;
}
digits[8] = n;
for (int o = 0; o < 10; o++) {
if (o == n || o == m) {
continue;
}
digits[7] = o;
for (int p = 0; p < 10; p++) {
if (p == o || p == n || p == m) {
continue;
}
digits[6] = p;
for (int r = 0; r < 10; r++) {
if (r == p || r == o || r == n || r == m) {
continue;
}
digits[5] = r;
for (int s = 0; s < 10; s++) {
if (s == r || s == p || s == o || s == n || s == m) {
continue;
}
digits[4] = s;
for (int t = 0; t < 10; t++) {
if (t == s || t == r || t == p || t == o || t == n || t == m) {
continue;
}
digits[3] = t;
for (int u = 0; u < 10; u++) {
if (u == t || u == s || u == r || u == p || u == o || u == n || u == m) {
continue;
}
digits[2] = u;
for (int v = 0; v < 10; v++) {
if (v == u || v == t || v == s || v == r || v == p || v == o || v == n || v == m) {
continue;
}
digits[1] = v;
i = 0;
for (int y = 0; y < 10; y++) {
if (y == v || y == u || y == t || y == s || y == r || y == p || y == o || y == n || y == m) {
continue;
}
i = (m * power(10, 9)) + (n * power(10, 8)) + (o * power(10, 7)) + (p * power(10, 6)) + (r * power(10, 5)) + (s * power(10, 4)) + (t * power(10, 3)) + (u * power(10, 2)) + (v * power(10, 1)) + y;
digits[0] = y;
cnt = 0;
for (a = 6, j = 0; a >= 0, j < 7; a--, j++) {
number = 0;
for (b = a, c = 0; b <= (a + 2), c <= 2; b++, c++) {
number += (digits[b] * power(10, c));
}
if (number % primes[j] != 0) {
cnt++;
break;
}
}
if (cnt == 0) {
result += i;
cout << i << endl;
}
}
}
}
}
}
}
}
}
}
}
cout << endl << "Sum of all 0 to 9 pandigital numbers with this property is = " << result << endl;
return 0;
}
Comments
Post a Comment