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

  • 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.

This one was a little tricky only because of the number of loops. My first brute force version technically worked albeit very slowly. So I moved if statements into each loop to filter out unecessary paths. Works now in < one second.

import java.util.*;

public class Euler43
{
    public static void main(String[] args)
    {
        Euler43 e = new Euler43();
        System.out.format(“Problem: %s\n”, e.getClass().getName());
        System.out.format(“Answer = %s\n”, e.Problem());
    }
    public String Problem ()
    {
        ArrayList<String> P = new ArrayList<String>();
        int [] Digits = new int [] {0,1,2,3,4,5,6,7,8,9};
        int [] d = new int [11];
        boolean flag = true;
        for (d[1] = 1; d[1] <= 9; d[1]++)
            for (d[2] = 0; d[2] <= 9; d[2]++)
                for (d[3] = 0; d[3] <= 9; d[3]++)
                    for (d[4] = 0; d[4] <= 9; d[4]++)
                        if ((d[2]*100+d[3]*10+d[4]) % 2 == 0)
                            for (d[5] = 0; d[5] <= 9; d[5]++)
                                if ((d[3]*100+d[4]*10+d[5]) % 3 == 0)
                                    for (d[6] = 0; d[6] <= 9; d[6]++)
                                        if ((d[4]*100+d[5]*10+d[6]) % 5 == 0)
                                            for (d[7] = 0; d[7] <= 9; d[7]++)
                                                if ((d[5]*100+d[6]*10+d[7]) % 7 == 0)
                                                    for (d[8]= 0; d[8] <= 9; d[8]++)
                                                        if ((d[6]*100+d[7]*10+d[8]) % 11 == 0)
                                                            for (d[9] = 0; d[9] <= 9; d[9]++)
                                                                if ((d[7]*100+d[8]*10+d[9]) % 13 == 0)
                                                                    for (d[10] = 0; d[10] <= 9; d[10]++)
                                                                        if ((d[8]*100+d[9]*10+d[10]) % 17 == 0)
                                                                        {
                                                                            flag = true;
                                                                            for (int digit: Digits)
                                                                            {
                                                                                int c = 0;
                                          &
nbsp;                                     for (int i = 1; i <= 10; i++)
                                                                                    if (d[i] == digit)
                                                                                        c++;
                                                                                if (c != 1)
                                                                                {
                                                                                    flag = false;
                                                                                    break;
                                                                                }
                                                                            }
                                                                            if (flag)
                                                                            {
                                                                                String val = “”;
                                                                                for (int i = 1; i <= 10; i++)
                                                                                    val += d[i];
                                                                                System.out.format(“%s\n”, val);
                                                                                P.add(val);
                                                                            }
   &
nbsp;                                                                    }
        long sum = 0;
        for (String i:P)
            sum += Long.valueOf(i);
        return String.valueOf(sum);
    }
}



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s