Project Euler Problem 43

Problem 43

09 May 2003

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₁ be the 1^st digit, d₂ be the 2^nd digit, and so on. In this way, we note the following:

• d₂d₃d₄=406 is divisible by 2
• d₃d₄d₅=063 is divisible by 3
• d₄d₅d₆=635 is divisible by 5
• d₅d₆d₇=357 is divisible by 7
• d₆d₇d₈=572 is divisible by 11
• d₇d₈d₉=728 is divisible by 13
• d₈d₉d₁₀=289 is divisible by 17

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

Answer: 16695334890

 

 

C#

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace Euler {
    class Program {
        static string arrayToString<T>(T[] array) {
            return array.Select(x => Convert.ToString(x)).Aggregate(string.Concat);
        }

        static long sum = 0;
        static void permute(int[] n, int level = 0) {
            if (level > n.Length - 1) {
                //Console.Write(count + ": ");
                //foreach (var x in n) Console.Write(x);
                //Console.WriteLine();
                //Console.ReadKey();

                string strN = arrayToString(n);
                //Console.WriteLine(strN);
                //Console.ReadKey();
                if (Convert.ToInt64(strN.Substring(7, 3)) % 17== 0 &&
                    Convert.ToInt64(strN.Substring(6, 3)) % 13== 0 &&
                    Convert.ToInt64(strN.Substring(5, 3)) % 11== 0 &&
                    Convert.ToInt64(strN.Substring(4, 3)) % 7 == 0 &&
                    Convert.ToInt64(strN.Substring(3, 3)) % 5== 0 &&
                    Convert.ToInt64(strN.Substring(2, 3)) % 3 == 0 &&
                    Convert.ToInt64(strN.Substring(1, 3)) % 2 == 0) {
                        sum += Convert.ToInt64(strN);
                }
                return;
            }
            for (int i = 0; i <= 9; i++) {
                bool hasDuplicate = false;
                for (int priorLevel = 0; priorLevel < level; priorLevel++) {
                    if (i == n[priorLevel]) {
                        hasDuplicate = true;
                        break;
                    }
                }
                if (!hasDuplicate) {
                    n[level] = i;
                    permute(n, level + 1);
                }
            }
        }

        static void Main(string[] args) {
            permute(new int[10]);
            Console.WriteLine(sum);
        }
    }
}