// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (12 votes, average: 4.67 out of 5)
Loading...

Project Euler Solutions

Project Euler 43 Solution

Project Euler 43 Solution

Project Euler 43: Find the sum of all pandigital numbers with an unusual sub-string divisibility property.


Project Euler 43 Problem Description

Project Euler 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.

Analysis

There are only 9 x 9! (3,265,920) possible 0-9 ten-digit pandigital numbers. Simply generate the possibilities and check each three-digit section to be divisible by the appropriate prime number. But even on a fast computer this method may take too long to run.

We can make some observations to reduce the number of possibilities. Keep in mind we are dealing with 3 digit numbers that must have unique digits in order to qualify as part of a 0-9 pandigital ten-digit number.

Some observations

Observation 1: d4d5d6 must be divisible by 5 then:
d6 = {0, 5}.

Observation 2: d6d7d8 must to be divisible by 11 and, according to Obs. 1, has to start with a {0, 5}. Well, it can’t start with 0 as that would yield non-unique digits, so it has to start with 5, i.e., d6 = 5.
d6d7d8 = {506, 517, 528, 539, 561, 572, 583, 594}

Observation 3: d7d8d9 must be divisible by 13, begin with {06, 17, 28, 39, 61, 72, 83, 94} by Obs. 2, contain no 5s and have only unique digits:
d7d8d9 = {286 390 728 832}

Observation 4: d8d9d10 must be divisible by 17, begin with {28, 32, 86, 90} by Obs. 3, contain no 5s and have only unique digits:
d8d9d10 = {289, 867, 901}

Observation 5: d5d6d7 must be divisible by 7, end with {52, 53, 57, 58} by Obs. 2 & 3 and have only unique digits:
d5d6d7 = {357, 952}

We have reduced our possibilities for the last 6 digits using our 5 observations to:
d5d6d7d8d9d10 = {357289, 952867}

Finishing the problem

Observation 6: d3d4d5 must be divisible by 3, not contain {2, 5, 7, 8} since they have been place, end in {3, 9}, have all unique digits and an even middle number:
d3d4d5 = {063, 309, 603}

This forces d1d2 to {14, 41}

Our final set is: {1406357289, 1430952867, 1460357289, 4106357289, 4130952867, 4160357289}

Afterthoughts

Project Euler 43 Solution last updated

Discussion

6 Responses to “Project Euler 43 Solution”

  1. 2-liner, same code

    from itertools import permutations

    print(sum(int(”.join(x)) for x in permutations(‘0123456789’, 10) if all([not int(”.join(x)[n[0]:n[1]]) % n[2] for n in [(1, 4, 2), (2, 5, 3), (3, 6, 5), (4, 7, 7), (5, 8, 11), (6, 9, 13), (7, 10, 17)][:7]])))

    Posted by Reo | May 12, 2016, 1:46 PM
  2. another rule:
    Since d3d4d5 has to be divisible by 3 and d5 is {3,9}, (d3+d4) have to be divisible by 3.
    When d5d6d7d8d9d10 is 952867,d3d4 can only be 30 ,then we have two numbers with this property.
    when d5d6d7d8d9d10 is 357289,d3d4 can be 06 or 60, then we have four numbers with this property.
    Sum all these six numbers, we get the answer.

    Posted by feliz | July 17, 2015, 11:30 PM
  3. Thanks a lot!!
    only 20 seconds for me, before your beautiful explanation.

    Bye

    Posted by bancaldo | December 6, 2012, 4:34 AM

Post a comment