PyPE solution to PE problem 43
PyPE solution to PE problem 43
Blueprint information
- Status:
- Started
- Approver:
- None
- Priority:
- Undefined
- Drafter:
- None
- Direction:
- Needs approval
- Assignee:
- None
- Definition:
- Approved
- Series goal:
- None
- Implementation:
- Needs Code Review
- Milestone target:
- None
- Started by
- Scott Armitage
- Completed by
Related branches
Related bugs
Sprints
Whiteboard
ProjectEule
===
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 1st digit, d_2 be the 2nd 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.
Solution
--------
Brute-force approach, starting with all <=3 digit multiples of 17, and
working backwards towards the first digits. At each stage, we check to
see if any of the new digits we've created already exist in the candidate
somewhere; if so, we skip it and move on. This avoids having to test wheter
each candidate is a 0-9 pandigital number.
Note that my indexing is reduced by one, to start at d0 being the 0th digit
in the candidate number.
Answer
------
16695334890